面经整理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);}}
}

Decode Ways - LeetCode

这题被面过好几次，但拿到题还是没啥思路，最好的情况和斐波那契数列是一样的（这个也面过好几次）

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;}
}

其他的有几题做过，有几题没有做过

Merge Intervals - LeetCode

后面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()][]);}
}

Unique Paths - LeetCode

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];}
}

Convex Polygon - LeetCode

纯几何题，要记住公式

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;}
}

Predict the Winner - LeetCode

找到一个比较好理解的递归的解法，但估计面试会要求用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));}
}

Cat and Mouse - LeetCode

这道题据说当年周赛的时候国服没有一个人做出来，好不容易找到个视频看懂了，跟着把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原题的

这么几道题竟然弄了一个星期！！！效率实在太低了。今天在地理发现了一份非常完整的面经，感觉自己真的是弱爆了，我要去刷那份面经了。