面经整理1
感觉好几个都是backtracking
Letter Combinations of a Phone Number - LeetCode
典型的backtracking,注意String的处理
class Solution {
String[] keyboard = new String[]{"", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
if (digits.isEmpty()) return res;
dfs(res, sb, digits, 0);
return res;
}
private void dfs(List<String> res, StringBuilder sb, String digits, int idx) {
if (idx == digits.length()) {
res.add(sb.toString());
return;
}
String str = keyboard[digits.charAt(idx) - '0'];
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i));
dfs(res, sb, digits, idx + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
这题被面过好几次,但拿到题还是没啥思路,最好的情况和斐波那契数列是一样的(这个也面过好几次)
1. Recursion with memoization,,看了花花的视频
time: O(n^2)->O(n)
space:O(n^2)->O(n)
class Solution {
Map<String, Integer> map = new HashMap<>();
public int numDecodings(String s) {
if (s == null || s.length() == 0) return 0;
map.put("", 1);
return dfs(s);
}
private int dfs(String s) {
if (map.containsKey(s)) return map.get(s);
if (s.charAt(0) == '0') return 0;
if (s.length() == 1) return 1;
int ways = dfs(s.substring(1));
String sub = s.substring(0, 2);
int prefix = Integer.parseInt(sub);
if (prefix >= 10 && prefix <= 26) {
ways += dfs(s.substring(2));
}
map.put(s, ways);
return ways;
}
}
OpenAi 给了一个我能理解的dp解法
class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
char first = s.charAt(i - 1);
char second = s.charAt(i - 2);
if (first != '0') {
dp[i] += dp[i - 1];
}
int twoDigit = (second - '0') * 10 + (first - '0');
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
Restore IP Addresses - LeetCode
正确的ip是被3个'.'分割成了4部分,所以当点的个数到3的时候要判断是否valid,valid的区间范围是【idx, i]
判断valid的条件就是当前数字的第一个数不能为0,在有效的区间内,当前的数字不能大于9或者小于0,数字记得进位num = num * 10 + digit. 如果num的范围是【0,255】
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder(s);
dfs(res, sb, 0, 0);
return res;
}
private void dfs(List<String> res, StringBuilder sb, int idx, int points) {
if (points == 3) {
if (isValid(sb, idx, sb.length() - 1)) {
res.add(sb.toString());
}
return;
}
for (int i = idx; i < sb.length(); i++) {
if (isValid(sb, idx, i)) {
points += 1;
sb.insert(i + 1, '.');
dfs(res, sb, i + 2, points);
sb.deleteCharAt(i + 1);
points -= 1;
}
}
}
private boolean isValid(StringBuilder s, int left, int right) {
if (left > right) return false;
if (s.charAt(left) == '0' && left != right) return false;
int num = 0;
for (int i = left; i <= right; i++) {
if (s.charAt(i) >'9' || s.charAt(i) < '0') return false;
int digit = s.charAt(i) - '0';
num = num * 10 + digit;
if (num > 255) return false;
}
return true;
}
}
Validate IP Address - LeetCode
模拟实现题
class Solution {
public String validIPAddress(String queryIP) {
if (queryIP.indexOf('.') >= 0) {
return isIpV4(queryIP) ? "IPv4" : "Neither";
} else {
return isIpV6(queryIP) ? "IPv6" : "Neither";
}
}
public boolean isIpV4(String queryIP) {
String[] split = queryIP.split("\\.", -1);
if (split.length != 4) {
return false;
}
for (String s : split) {
if (s.length() > 3 || s.length() == 0) {
return false;
}
if (s.charAt(0) == '0' && s.length() != 1) {
return false;
}
int num = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (!Character.isDigit(c)) return false;
num = num * 10 + c - '0';
}
if (num > 255) return false;
}
return true;
}
private boolean isIpV6(String queryIP) {
String[] split = queryIP.split(":", -1);
if (split.length != 8) return false;
for (String s : split) {
if (s.length() > 4 || s.length() == 0) return false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!Character.isDigit(c) && !(Character.toLowerCase(c) >= 'a') || !(Character.toLowerCase(c) <= 'f')) {
return false;
}
}
}
return true;
}
}
其他的有几题做过,有几题没有做过
后面toArray的要再熟悉一下,有点忘记了
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> list = new ArrayList<>();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
list.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = list.get(list.size() - 1);
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(intervals[i][1], last[1]);
} else {
list.add(intervals[i]);
}
}
return list.toArray(new int[list.size()][]);
}
}
dp解法
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
纯几何题,要记住公式
class Solution {
public boolean isConvex(List<List<Integer>> points) {
int n = points.size();
long pre = 0;
for (int i = 0; i < n; i++) {
int x1 = points.get((i + 1) % n).get(0) - points.get(i).get(0);
int x2 = points.get((i + 2) % n).get(0) - points.get(i).get(0);
int y1 = points.get((i + 1) % n).get(1) - points.get(i).get(1);
int y2 = points.get((i + 2) % n).get(1) - points.get(i).get(1);
long cur = x1 * y2 - x2 * y1;
if (cur != 0) {
if (cur * pre < 0) {
return false;
}
pre = cur;
}
}
return true;
}
}
找到一个比较好理解的递归的解法,但估计面试会要求用dp来解
class Solution {
public boolean predictTheWinner(int[] nums) {
return first(nums, 0, nums.length - 1) >= second(nums, 0, nums.length - 1);
}
private int first(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
return Math.max(nums[left] + second(nums, left + 1, right), nums[right] + second(nums, left, right - 1));
}
private int second(int[] nums, int left, int right) {
if (left == right) {
return 0;
}
return Math.min(first(nums, left + 1, right), first(nums, left, right - 1));
}
}
这道题据说当年周赛的时候国服没有一个人做出来,好不容易找到个视频看懂了,跟着把C++代码改成了Java,竟然越界了。。。这题好像最好的解法是拓扑排序。这个解法是三维DP,我觉得逻辑很清晰呀。
class Solution {
int[][] graph;
int n;
public int catMouseGame(int[][] graph) {
this.graph = graph;
this.n = graph.length;
int[][][] dp = new int[n][n][2 * n * n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2 * n * n; k++) {
dp[i][j][k] = -1;
}
}
}
return helper(1, 2, 0, dp);
}
private int helper(int mouse, int cat, int step, int[][][] dp) {
if (dp[mouse][cat][step] == -1) {
//打平
if (step >= 2 * n * n) {
dp[mouse][cat][step] = 0;
return 0;
//老鼠赢
} else if (mouse == 0) {
dp[mouse][cat][step] = 1;
return 1;
//猫赢
} else if (mouse == cat) {
dp[mouse][cat][step] = 2;
return 2;
//搜索
} else {
int res;
//老鼠先走
if (step % 2 == 0) {
//最坏结果是猫赢
res = 2;
for (int e : graph[mouse]) {
if (e == 0) continue;
int risk = helper(e, cat, step + 1, dp);
if (risk == 2) {
continue;
} else {
//平局
res = risk;
//赢
if (risk == 1) {
res = 1;
break;
}
}
}
dp[mouse][cat][step] = res;
} else {
res = 1;
for (int e : graph[cat]) {
int risk = helper(mouse, e, step + 1, dp);
if (risk == 1) {
continue;
} else {
//平局
res = risk;
//赢
if (risk == 2) {
res = 2;
break;
}
}
}
dp[mouse][cat][step] = res;
}
}
}
return dp[mouse][cat][step];
}
}
Shortest Path in Binary Matrix - LeetCode
经典BFS题,最短距离,也可以用A*来做
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] == 1) return -1;
int m = grid.length;
int n = grid[0].length;
if (grid[m - 1][n - 1] == 1) return -1;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0, 1});
grid[0][0] = 1;
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
if (cur[0] == m - 1 && cur[1] == n - 1) return cur[2];
for (int[] dir : dirs) {
int x = cur[0] + dir[0];
int y = cur[1] + dir[1];
if (x >= 0 && y >= 0 && x < m && y < m && grid[x][y] == 0) {
queue.add(new int[]{x, y, cur[2] + 1});
grid[x][y] = 1;
}
}
}
}
return -1;
}
}
还有一些没有Leetcode原题的
这么几道题竟然弄了一个星期!!!效率实在太低了。今天在地理发现了一份非常完整的面经,感觉自己真的是弱爆了,我要去刷那份面经了。
原文地址:https://blog.csdn.net/2301_78266314/article/details/137612100
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!