Leetcode面试经典150题

数组字符串

合并两个有序数组

思路

类似于归并排序，对两个有序数组进行合并即可，但是空间复杂度是O(n+m);

代码

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] ans = new int[n + m];int i = 0, j = 0;int cnt = 0;while (i < m && j < n) {if (nums1[i] < nums2[j]) {ans[cnt++] = nums1[i++];} else {ans[cnt++] = nums2[j++];}}while(i < m) ans[cnt++] = nums1[i++];while(j < n) ans[cnt++] = nums2[j++];for (int k = 0; k < cnt; ++k) {nums1[k] = ans[k];}}
}

优化：有一点小优化吧，可以从后往前合并装入nums1的后面，这样不会影响nums1的元素，同样也节省了n+m的空间（本题的数据量小，所以看不出）。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1;int j = n - 1;int cnt = n + m - 1;while(i >= 0 && j >= 0) {if (nums1[i] < nums2[j]) {nums1[cnt--] = nums2[j--];} else {nums1[cnt--] = nums1[i--];}}while(i >= 0) nums1[cnt--] = nums1[i--];while(j >= 0) nums1[cnt--] = nums2[j--];}
}

双指针

验证回文串

思路

用头指针和尾指针，每次比较的时候必须满足两个指针指向的是数字或字符，其他的符号都跳过。

代码

class Solution {public boolean isPalindrome(String s) {s = s.toLowerCase();int len = s.length();int i = 0, j = len - 1;char[] ch = s.toCharArray();while(i < j) {while(i < len && !check(ch[i])) ++i;while(j >= 0 && !check(ch[j])) --j;//前面两句是过滤非字符或数字if (i > j) {break;}if (ch[i] >= 'a') {ch[i] -= 32;}if (ch[j] >= 'a') {ch[j] -= 32;}// 如果是字符，则统一转为小写if (ch[i] != ch[j]) {return false;}++i;--j;}return true;}private boolean check(char ch) {if (ch <= 'z' && ch >= 'a') {return true;}if (ch <= 'Z' && ch >= 'z') {return true;}if (ch <= '9' && ch >= '0') {return true;}return false;}
}

滑动窗口

长度最小的子数组

思路

由滑动窗口思想：设两个指针，尾指针一直走，当满足某个条件时，头指针也跟着走。
条件：当子数组和大于target时，不断缩小窗口，找到最小的窗口。

代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int ans = nums.length;int ind = 0;int sum = 0;for (int i = 0; i < nums.length; ++i) {sum += nums[i];while (sum >= target) {sum -= nums[ind];ans = Math.min(ans, i - ind + 1);ind++;}}if (ind == 0) { // sum>=target没有执行，不存在子数组return 0;} return ans;}
}

矩阵

有效的数独

思路

创建三个set数组，分别是对存“行”，“列”，“区域”的数字，如果对应的set中有值，那么就不是有效的。否则就添加
这里最主要的是怎样判断是否为同一个区域。
可以先对9x9的表格通过i/3,j/3划分为9个3x3区域然后每个区域的值都是
(0, 0), (0, 1), (0, 2)
(1, 0), (1, 1)…
再通过将二维数组变为一维数组的计算公式i * row + j。就是9个区域。

代码

class Solution {public boolean isValidSudoku(char[][] board) {Set<Character>[] rows = new HashSet[9];Set<Character>[] cols = new HashSet[9];Set<Character>[] area = new HashSet[9];for (int i = 0; i < 9; ++i) {rows[i] = new HashSet<>();cols[i] = new HashSet<>();area[i] = new HashSet<>();}for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {if (board[i][j] > '9' || board[i][j] < '0') continue;if (rows[i].contains(board[i][j])) {return false;} else {rows[i].add(board[i][j]);}if (cols[j].contains(board[i][j])) {return false;} else {cols[j].add(board[i][j]);}int t= i / 3 * 3 + j / 3;//System.out.println(i + " " + j + " " + t);if (area[t].contains(board[i][j])) {return false;} else {area[t].add(board[i][j]);}}}return true;}
}

哈希表

赎金信

思路

比较r和m的26个字符个数，如果r的某个字符个数大于m的某个字符个数，则r不能由m的字符组成。

代码

class Solution {public boolean canConstruct(String r, String m) {int[] rCnt = new int[26];int[] mCnt = new int[26];for (int i = 0; i < r.length(); ++i) {rCnt[r.charAt(i) - 'a']++;}for (int i = 0; i < m.length(); ++i) {mCnt[m.charAt(i) - 'a']++;}for (int i = 0; i < 26; ++i) {if (rCnt[i] > mCnt[i]) {return false;}}return true;}
}

区间

汇总区间

思路

简单模拟

代码

class Solution {public List<String> summaryRanges(int[] nums) {List<String> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < n;) {int j = i;while(j < n -1 && nums[j] + 1 == nums[j + 1]) j++;if (j == i) {ans.add("" + nums[i]);++i;} else {ans.add(nums[i] + "->" + nums[j]);i = j + 1;}}return ans;}
}

栈

有效括号

思路

如果能够匹配则删除栈顶元素，如果不能匹配就进栈，最后判断是否为空。

代码

class Solution {static final Map<Character, Character> map = new HashMap<>() {{put('(',')');put('{','}');put('[',']');}};public boolean isValid(String s) {char[] ch = s.toCharArray();Stack<Character> stack = new Stack<>();for (char c : ch) {if (stack.isEmpty()) {stack.push(c);continue;}Character peek = stack.peek();if (map.containsKey(peek) && map.get(peek) == c) {stack.pop();} else {stack.push(c);}}return stack.isEmpty();}
}

链表

环形链表

思路

链表长度最长1e4，头结点一直往后走，如果次数超过链表长度，必定有环（投机取巧了）

代码

public class Solution {public boolean hasCycle(ListNode head) {int cnt = 0;while(head != null) {head = head.next;cnt++;if (cnt > 10005) {return true;}}return false;}
}

正解：快慢指针，根据Floyd判圈法，又称为龟兔赛跑算法，乌龟每次走一格，兔子每次走两格，如果有环，兔子提前进入环并且一直在环内运动，而当乌龟进入环时，兔子一定会追到乌龟。

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next ==null) {return false;}ListNode slow = head;ListNode fast = head.next;while(slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}
}

二叉树

二叉树的最大深度

思路

模拟走一遍二叉树同时记录层数。

代码

class Solution {int ans = 0;public int maxDepth(TreeNode root) {dfs(root, 0);return ans;}public void dfs(TreeNode root, int level) {if (root == null) {ans = Math.max(ans, level);return;}dfs(root.left, level + 1);dfs(root.right, level + 1);}
}

二叉树的遍历

二叉树的右视图

思路

二叉树的层序遍历，取每层的最后一个节点即可。

代码

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> ans = new ArrayList<>();if (root == null) {return ans;}int cnt = 0, lastVal = 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {cnt = queue.size();// 每层有多少个节点while(cnt-- > 0) {TreeNode curNode = queue.poll();if (curNode.left != null) queue.add(curNode.left);if (curNode.right != null) queue.add(curNode.right);lastVal = curNode.val;}ans.add(lastVal);//每层的最后一个节点}return ans;}}

二叉搜索树

二叉搜索树的最小绝对差

思路

二叉搜索树的中序遍历是升序，而升序的相邻节点可以得到一个最小值，即答案所求。

代码

class Solution {int ans = Integer.MAX_VALUE;int pre = -1; // 记录中序遍历的前一个节点,初始化为-1，是还没找到中序遍历的第一个节点public int getMinimumDifference(TreeNode root) {dfs(root);return ans;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (pre == -1) {pre = root.val;} else {ans = Math.min(ans, root.val - pre);pre = root.val;}dfs(root.right);}
}

图

岛屿数量

思路

dfs没走过的为1的格子

代码

class Solution {int N = 305;static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};boolean[][] vis = new boolean[N][N];int n, m, ans;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (vis[i][j] || grid[i][j] == '0') continue;dfs(grid, i, j);//System.out.println(i + "<->" + j);ans++;}}return ans;}private void dfs(char[][] g, int x, int y) {vis[x][y] = true;for (int i = 0; i < 4; ++i) {int curX = x + dir[i][0];int curY = y + dir[i][1];if (curX < 0 || curY < 0 || curX >= m || curY >= n || g[curX][curY] == '0' || vis[curX][curY]) continue;dfs(g, curX, curY);}}
}

图广度优先搜索

蛇梯棋

思路

题实在没读懂，参考解析。
利用广度优先搜索，先走格子，如果遇到梯子或蛇就直接传送（传送不花时间）。

代码

class Solution {int n;int[] g;public int snakesAndLadders(int[][] board) {n = board.length;boolean isR = true;g = new int[n * n + 1];int ind = 0;for (int i = n - 1; i >= 0; --i) {for (int j = (isR ? 0 : n - 1); isR ? j < n : j >= 0; j += isR ? 1 : -1) { // 经典的神龙摆尾g[++ind] = board[i][j];}isR = !isR;}int ans = bfs();return ans;}private int bfs()  {Queue<Integer> queue = new LinkedList<>(); // 当前到的点Map<Integer, Integer> m = new HashMap<>(); // 用于存当前点和步数m.put(1, 0);queue.add(1);while(!queue.isEmpty()) {int cur = queue.poll();int step = m.get(cur);if (cur == n * n) return step;for (int i = 1; i <= 6; ++i) {int nxt = cur + i;if (nxt > n * n) continue;if (g[nxt] != -1) nxt = g[nxt]; //直接传送if (m.containsKey(nxt)) continue; // 已经走过m.put(nxt, step + 1);queue.add(nxt);}}return -1;}
}

字典树

实现 Trie (前缀树)

思路

字典树模版题

代码

class Trie {static final int N = (int) 1e5 + 9;static int[] cnt = new int[N];static int[][] tree = new int[N][26];static int ind = 0;public Trie() {for (int i = ind; i >= 0; --i) {Arrays.fill(tree[i], 0);}Arrays.fill(cnt, 0);ind = 0;}public void insert(String word) {int p = 0;for (int i = 0; i < word.length(); ++i) {int u = word.charAt(i) - 'a';if (tree[p][u] == 0) tree[p][u] = ++ind;p = tree[p][u];}cnt[p]++;}public boolean search(String word) {int p = 0;for (int i = 0; i < word.length(); ++i) {int u = word.charAt(i) - 'a';if (tree[p][u] == 0) return false;p = tree[p][u];}return cnt[p] != 0;}public boolean startsWith(String prefix) {int p = 0;for (int i = 0; i < prefix.length(); ++i) {int u = prefix.charAt(i) - 'a';if (tree[p][u] == 0) return false;p = tree[p][u];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

回溯

电话号码的字母组合

思路

将每个键对应的字母存到String里，然后dfs变量每一个键，遍历到的键存到一个数组里，指导存了digits.size()个。

代码

class Solution {private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};private final List<String> ans = new ArrayList<>();private char[] digits, path;public List<String> letterCombinations(String digits) {int n = digits.length();if (n == 0) return List.of();this.digits = digits.toCharArray();path = new char[n];dfs(0);return ans;}private void dfs(int i) {if (i ==digits.length) { // 如果已经按完ans.add(new String(path));return;}for (char c : MAPPING[digits[i] - '0'].toCharArray()) { // 枚举按每一个键path[i] = c; // 考虑先后顺序，先出现的和后出现的做匹配dfs(i + 1);}}
}