刷穿力扣（6190）

61. 旋转链表

---

• 模拟

• 结合代码如下列过程所示：

• 1 -> 2 -> 3 -> 4 -> 5 -> null // 遍历第一次，len = 5，res -> 5

• 1 -> 2 -> 3 -> 4 -> 5 -> null // 遍历第二次，当 k = 3 时，需要找到 len - k 的下一个节点，此时 cnt -> 3，ans -> 4

• 1 -> 2 -> 3 -> null 4 -> 5 -> null // 断开 cnt

    |       |          |    |
    head     cnt        ans  res

• 4 -> 5 -> 1 -> 2 -> 3 -> null // 将 res -> head

    |    |    |         |
    ans res  head      cnt

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 特判
        if (head == null || head.next == null || k == 0) return head;
        int len = 1;  // 计算链表长度
        ListNode res = head;
        while (res.next != null) {
            len++;
            res = res.next;
        }
        // 如果恰好为 len 整数倍则不需要旋转
        if ((k %= len) == 0) return head;
        ListNode cnt = head;  // 找到需要旋转的位置
        for (int i = 1; i < len - k; i++) cnt = cnt.next;
        ListNode ans = cnt.next;           // ans 指向旋转节点的下一个节点
        cnt.next = null; res.next = head;  // cnt 为新的尾节点，res 拼接到原来的头节点
        return ans;
    }
}

---

62. 不同路径

---

• dp
  • 状态表示：
    • dp[i][j] 表示到达第 i 行 第 j 列的方案数量
    • 初始化 dp[i][0] = dp[0][j] = 1
  • 状态计算：
    • dp[i][j] 为从上面下来和从左边过来的方案数之和
    • 即：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

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 i = 0; i < n; i++) dp[0][i] = 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];
    }
}

优化：

• 由于计算时只使用到了 dp[i - 1][j] 和 dp[i][j - 1]，利用滚动数组优化
  • 状态表示：
    • dp[j] 表示当前层 j 列的方案数
    • 初始化 dp[j] = 1
  • 状态计算：
    • dp[j] 为上层下来和左边列转移过来的方案数之和
    • 即 dp[j] = dp[j] + dp[j - 1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

---

63. 不同路径 II

---

• dp
  • 状态表示：
    • dp[i][j] 到达 i 层 j 列的方案数量
    • 初始化，当 obstacleGrid[0][i] != 1 和 obstacleGrid[0][j] != 1 时即能走到
    • 初始化能走到的点 dp[i][0] = dp[0][j] = 1，一旦遇到墙则后面的都走不到，直接退出
  • 状态计算：
    • 当 obstacleGrid[i][j] != 1 时，dp[i][j] 为上层下来和左边列转移过来的方案数之和
    • 否则 dp[i][j] = 0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break;
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) break;
            dp[0][i] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) return 0; 
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
            else break;
        }
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[0][i] == 0) dp[0][i] = 1;
            else break;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][m - 1];
    }
}

优化：

• 同理，计算只用到了 dp[i][j - 1] 和 dp[i - 1][j]，利用滚动数组优化
  • 状态表示：
    • dp[j] 表示当前层 j 列的方案数
    • 初始化 dp[0] = 1，因为只有从起点开始的才算做路径
  • 状态计算：
    • 当 obstacleGrid[i][j] != 1 时 dp[j] = dp[j] + dp[j - 1]
    • 否则 dp[j] = 0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) return 0; 
        int[] dp = new int[m];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j] == 1) dp[j] = 0;  // 当前位置有障碍物，路径数设为 0
                else if (j > 0) {
                    dp[j] += dp[j - 1];  // 更新路径数为左边和上边路径数之和
                }
            }
        }
        return dp[m - 1];
    }
}

---

64. 最小路径和

---

• dp
  • 和上面的题目思路一样，不过是取最小
  • 状态表示：
    • dp[i][j] 到达 i 行 j 列的最小步数
    • 初始化：dp[i][0] = dp[i - 1][0] + grid[i][0]，dp[0][j] = dp[0][j - 1] + grid[0][j]
  • 状态计算：
    • dp[i][j] 为上边和左边转移过来的最小步数加上 grid[i][j] 的步数之和
    • 即：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + grid[0][i];
        for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }
}

优化：

• 同理，计算只用到了 dp[i][j - 1] 和 dp[i - 1][j]，利用滚动数组优化
  • 状态表示：
    • dp[j] 表示当前层 j 列的最小步数
    • 初始化 dp[0] = grid[0][0]，因为只有从起点开始的才算，且每层都要更新 dp[0] += grid[i][0]
  • 状态计算：
    • dp[j] 为上层下来和左边列转移过来的最小步数和 grid[i][j] 之和
    • 即：dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid[0].length;
        int[] dp = new int[m];
        dp[0] = grid[0][0];
        for (int i = 1; i < m; i++) dp[i] = dp[i - 1] + grid[0][i];
        for (int i = 1; i < grid.length; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < m; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1];
    }
}

---

65. 有效数字

---

• 模拟

• 设 flag1 flag2 flag3 来记录数字、小数点和指数的出现情况

• 如果字符是数字：

  • 则 flag2 = 1，表示数字已经出现
  • 如果字符是小数点，则检查小数点之前是否已经出现小数点或指数：
    • 如果是，直接返回 false
    • 否则 flag1 = 1，表示小数点已经出现
  • 如果字符是 e、E，则检查指数符号之前是否已经出现指数或数字：
    • 如果是，直接返回 false
    • 否则 flag3 = 1，表示指数符号已经出现，且 flag2 = 0，指数后面需要出现整数
  • 如果字符是 -、+，检查该符号字符出现的位置：
    • 出现在字符串的开头
    • 或者出现在 'e' 或 'E' 的后面
    • 如果不满足上述条件，直接返回 false
  • 如果字符不是数字、小数点、指数符号或符号字符，直接 false

• 遍历完字符串后，如果数字已经出现过（即 flag2 == 1），则返回 true；否则返回 false

class Solution {
    public boolean isNumber(String s) {
        int flag1 = 0, flag2 = 0, flag3 = 0;
        if (s.length() == 0) return false;
        for (int i = 0; i < s.length(); i++) {
            char op = s.charAt(i);
            if (op >= '0' && op <= '9') {
                flag2 = 1;
            } else if (op == '.') {
                if (flag1 == 1 || flag3 == 1) return false;
                flag1 = 1;
            } else if (op == 'e' || op == 'E') {
                if (flag3 == 1 || flag2 == 0) return false;
                flag3 = 1;
                flag2 = 0;
            } else if (op == '-' || op == '+') {
                if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
            } else {
                return false;
            }
        }
        return flag2 == 1;
    }
}

---

66. 加一

---

• 模拟
  • 原理就是大整数的加法过程
  • 用 base 存储进位，每次加法时要加上进位
  • 对于每一位的值为 (digits[i] + base) % 10，更新进位为 (digits[i] + base) / 10
  • 由于只在最后一位加一，因此最初的 base = (digits[digits.length - 1] + 1) / 10

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int base = (digits[n - 1] + 1) / 10;
        digits[n - 1] = (digits[n - 1] + 1) % 10;
        for (int i = n - 2; i >= 0; i--) {
            int sum = digits[i] + base;
            digits[i] = sum % 10;
            base = sum / 10;
        }
        if (base == 0) return digits; // 进位为0，直接返回原数组
        else {
            // 有进位说明只可能是 999999999 这种的，加一后必然是 1 后面跟 n 个 0
            int[] ans = new int[n + 1];
            ans[0] = 1;
            return ans;
        }
    }
}

---

67. 二进制求和

---

• 模拟
  • 本质也是大整数加法过程
  • 先对 a, b 翻转，便于计算
  • 利用 base 记录进位，每次计算 (a + b + base) % 2，更新 base = (a + b + base) / 2 即可

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder C = new StringBuilder();             // 存储答案
        StringBuilder A = new StringBuilder(a).reverse();  // 翻转后的 a
        StringBuilder B = new StringBuilder(b).reverse();
        int base = 0, i = 0;
        while (i < A.length() || i < B.length()) {
            int x = (i < A.length()) ? A.charAt(i) - '0' : 0;
            int y = (i < B.length()) ? B.charAt(i) - '0' : 0;
            int sum = x + y + base;
            C.append(sum % 2); base = sum / 2; 
            i++;
        }
        if (base != 0) C.append(base);  // 追加最后一位进位
        return C.reverse().toString();
    }
}

---

68. 文本左右对齐

---

• 贪心
  • 遍历 words 数组，确定每行可以放置哪些单词
  • 对于每行单词，计算插入多少空格，并根据需求分配空格
  • 用 len 存储当前行的总长度，每次将 words[i].length 加入并计算间隔数量
  • 当间隔数不足时，将当前位置之前到开始记录位置的所有单词进行分配
  • 特别处理最后一行，左对齐并用空格填充到 maxWidth
  • 将每行处理好的字符串添加到结果列表 ans 中

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int len = 0, idx = 0;
        for (int i = 0; i < words.length; i++) {
            if (len + words[i].length() + i - idx > maxWidth) {
                int need = maxWidth - len;
                int res = i - idx - 1; // 每行的单词之间的间隔数量
                StringBuilder sb = new StringBuilder();
                if (res > 0) {
                    int use = need / res;
                    int vis = need % res;
                    for (int j = idx; j < i; j++) {
                        sb.append(words[j]);
                        if (j < i - 1) { // 不是最后一个单词
                            for (int s = 0; s < use + (j - idx < vis ? 1 : 0); s++) {
                                sb.append(" ");
                            }
                        }
                    }
                } else { // 如果这行只有一个单词
                    sb.append(words[idx]);
                    for (int j = 0; j < need; j++) sb.append(" ");
                }
                ans.add(sb.toString());
                len = 0; idx = i;
            }
            if (i < words.length) len += words[i].length();
        }
        // 处理最后一行
        StringBuilder lastLine = new StringBuilder();
        for (int i = idx; i < words.length; i++) {
            lastLine.append(words[i]);
            if (i < words.length - 1) lastLine.append(" ");
        }
        while (lastLine.length() < maxWidth) lastLine.append(" ");
        ans.add(lastLine.toString());
        return ans;
    }
}

---

69. x 的平方根

---

• 二分
  • 板子题
  • 二分期间不断判断 mid == x，找到直接返回
  • 否则返回第一个大于 x 的平方根 mid - 1

class Solution {
    public int mySqrt(int x) {
        long l = 0, r = x;
        while (l <= r) {
            long mid = (l + r) >> 1;   
            if (mid * mid == x) return (int)mid;  // 找到直接返回
            if (mid * mid > x) r = mid - 1;       // 找到第一个大于 x 的平方根 mid
            else l = mid + 1;
        }
        return (int)l - 1;
    }
}

---

70. 爬楼梯

---

• dp
  • 板子题
  • 状态表示：dp[i] 表示到达第 i 阶的方案数
  • 状态计算：第 i 层方案数为 i - 1 和 i - 2 层方案数之和，即 dp[i] = dp[i - 1] + dp[i - 2]
  • 优化：由于只需要记录 dp[i - 1] 和 dp[i - 2]，故只需要两个变量即可，不需要数组来存所有的

class Solution {
    public int climbStairs(int n) {
        int l = 1, r = 1, cnt;
        for (int i = 0; i < n - 1; i++) {
            cnt = l + r;
            l = r; r = cnt;
        }
        return r;
    }
}

---

71. 简化路径

---

• 栈
  • 首先将原来的路径以 '/' 进行分割，对每个分割后的路径进行判断：
    • 如果是 "." 说明是当前目录保持不变，无需处理
    • 如果是 "" 说明这是 "//" 分割的结果，也无需处理
    • 如果是 ".." 则说明要返回上一级目录
  • 因此我们需要一个栈 st 来维护目前有效的目录
  • 当遇到 ".." 时将 st 最顶层的目录出栈
  • 最后对留在 st 中的目录统一添加 '/' 即可

class Solution {
    public String simplifyPath(String path) {
        Deque<String> st = new LinkedList<>();
        Set<String> vis = new HashSet<>(Arrays.asList(".", "..", ""));
        // 将路径按 '/' 分割
        String[] res = path.split("/");
        for (String op : res) {
            if (op.equals("..") && !st.isEmpty()) {
                // 返回上一级
                st.pop();
            } else if (!vis.contains(op)) {
                // 有效目录名，入栈
                st.push(op);
            }
        }
        StringBuilder ans = new StringBuilder();
        // 从栈底到栈顶构建路径
        for (String op : st) {
            ans.insert(0, "/" + op);
        }
        return ans.length() > 0 ? ans.toString() : "/";
    }
}

---

72. 编辑距离

---

• dp思路
  • 对于 word1，我们默认其长度为 m，word2 长度为 n
  • 可以考虑从空字符串开始，逐步构建 word2
  • 状态表示：
    • dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
    • 初始化：
      • 当 word1 为空，即 i=0 时，将空字符串转换为 word2 的前 j 个字符需要 j 次插入操作：dp[0][j] = j
      • 当 word2 为空，即 j=0 时，将 word1 的前 i 个字符转换为空字符串需要 i 次删除操作：dp[i][0] = i
  • 状态计算：
    • 首先判断 word1 的第 i 个字符 (word1.charAt(i-1)) 和 word2 的第 j 个字符 (word2.charAt(j-1)) 是否相同
    • 若相同，则无需额外操作：dp[i][j] = dp[i-1][j-1]
    • 否则，取以下三种操作中的最小值，并加 1（代表执行了一次操作）：
      • 替换： dp[i-1][j-1] + 1
      • 删除 (word1 的字符)： dp[i-1][j] + 1
      • 插入 (word2 的字符)： dp[i][j-1] + 1
      • 即 dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + 1;
        for (int j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
        return dp[n][m];
    }
}

---

73. 矩阵置零

---

• 模拟
  • 用 List<int[]> vis 存储需要进行处理的点的坐标
  • 遍历 vis 对每个坐标用循环置零即可

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        List<int[]> vis = new ArrayList<int[]>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) vis.add(new int[]{i, j});
            }
        }
        for (int[] p : vis) {
            for (int i = 0; i < n; i++) matrix[i][p[1]] = 0;  // 列置零
            for (int j = 0; j < m; j++) matrix[p[0]][j] = 0;  // 行置零
        }
    }
}

---

74. 搜索二维矩阵

---

• 二分
  • 第一次二分，根据每一行的最大值确定在哪一行
  • 第二次二分，在对应行中确定是否存在

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int ml = 0, mr = matrix.length - 1;
        int l = 0, r = matrix[0].length - 1;
        int pos = 0;
        while (ml <= mr) {
            int mid = (ml + mr) >> 1;
            if (matrix[mid][r] == target) return true;
            if (matrix[mid][r] < target) ml = mid + 1;
            else mr = mid - 1;
        }
        if (ml > matrix.length - 1) return false;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (matrix[ml][mid] == target) return true;
            if (matrix[ml][mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return false;
    }
}

---

75. 颜色分类

---

• 双指针
  • l 及其之前的区间内都为 0，l 到 r 之间的区间内都为 1，r 右边的区间都为 2
  • 初始化 l = 0, r = nums.length - 1，l 视为最后一个 0 的边界，r 视为第一个 2 的边界
  • 利用 i = 0 开始直到 r，期间不断和指针边界交换即可
  • 对于 nums[i] == 0：
    • 说明需要将其加入到 l 左边的区间
    • 故将 nums[i] 和 nums[l] 的值交换，且 l 边界向右移
  • 对于 nums[i] == 2：
    • 说明需要将其加入到 r 右边的区间
    • 故将 nums[i] 和 nums[r] 的值交换，且 r 边界向左移
  • 对于 i 的移动，若 nums[i] == 1 不需要交换，直接移动 i；若 nums[i] == 2 在交换后不移动 i，因为不确定由 nums[r] 交换得来的大小，留作后续处理即可

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        int i = 0;
        while (i <= r) {
            if (nums[i] == 0) {
                int t = nums[l];
                nums[l++] = 0;
                nums[i++] = t;
            } else if (nums[i] == 2) {
                int t = nums[r];
                nums[r--] = 2;
                nums[i] = t;
            } else {
                i++;
            }
        }
    }
}

---

76. 最小覆盖子串

---

• 滑动窗口
  • 利用 HashMap<Character, Integer> st 标记需要匹配的字符及其数量
  • 另有 int[] vis 记录窗口内已有字符的数量
  • 当窗口内已匹配的字符数量满足要求时，尝试收缩左边界以维护窗口的最小长度

class Solution {
    public String minWindow(String s, String t) {
        int l = 0, n = s.length(), m = t.length();
        HashMap<Character, Integer> st = new HashMap<>();
        for (int i = 0; i < m; i++) st.put(t.charAt(i), st.getOrDefault(t.charAt(i), 0) + 1);
        int[] vis = new int[200];     // 记录当前窗口内的字符
        int res = 0;                  // 记录匹配的字符数量
        int cnt = Integer.MAX_VALUE;  // 记录最小窗口长度
        int idx = 0;                  // 记录最小窗口起始位置
        for (int i = 0; i < n; i++) {
            char p = s.charAt(i);
            if (st.containsKey(p)) {
                if (vis[p] < st.get(p)) res++;
                vis[p]++;
                // 如果当前窗口包含了所有 t 中的字符
                if (res == m) {
                    // 缩小窗口左边界
                    while (!st.containsKey(s.charAt(l)) || vis[s.charAt(l)] > st.get(s.charAt(l))) {
                        if (st.containsKey(s.charAt(l))) vis[s.charAt(l)]--;
                        l++;  // 左边界向右收缩
                    }
                    // 更新最小窗口长度和起始位置
                    if (i - l + 1 < cnt) {
                        cnt = i - l + 1; idx = l;
                    }
                }
            }
        }
        return cnt == Integer.MAX_VALUE ? "" : s.substring(idx, idx + cnt);
    }
}

---

77. 组合

---

• DFS
  • 经典小组合

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();  // 存储答案
        List<Integer> res = new ArrayList<>();        // 记录当前组合
        dfs(1, k, n, res, ans);
        return ans;
    }

    private void dfs(int u, int k, int n, List<Integer> res, List<List<Integer>> ans) {
        if (res.size() == k) {
            ans.add(new ArrayList<>(res));
            return;
        }
        for (int i = u; i <= n; i++) {
            res.add(i);
            dfs(i + 1, k, n, res, ans);  // 递归的每一层将该层 i 加入，后续不断递归
            res.remove(res.size() - 1);
        }
    }
}

---

78. 子集

---

• DFS
  • 上一题的 PRO 版本
  • 在上一题的基础上，传入 nums 进行选择
  • 同时外层循环 i = 0 到 i = nums.length 作为选择的最大个数

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            List<Integer> res = new ArrayList<>();
            dfs(0, i, nums, res, ans);
        }
        return ans;
    }

    private void dfs(int u, int k, int[] nums, List<Integer> res, List<List<Integer>> ans) {
        if (res.size() == k) {
            ans.add(new ArrayList<>(res));
            return;
        }
        for (int i = u; i < nums.length; i++) {
            res.add(nums[i]);
            dfs(i + 1, k, nums, res, ans);
            res.remove(res.size() - 1);
        }
    }
}

---

79. 单词搜索

---

• DFS
  • 首先循环遍历 board 找到第一个匹配 word 的位置 {x, y} 开始搜索
  • 递归的每一层，从上下左右四个方向进行遍历，因此需要构建偏移量数组
  • 判断进入下一层的条件为：
    • 加上偏移量后的坐标在 board 范围内
    • 该位置没有走过（需要用 vis 记录）
    • 该位置的字符和 word.charAt(idx) 相同
  • 递归的结束标志为 idx 到达 word 的结尾

class Solution {
    // 偏移量数组，遍历四个方向
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

    public boolean exist(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean[][] vis = new boolean[n][m];
                    vis[i][j] = true;
                    if (dfs(i, j, vis, 1, board, word)) return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, boolean[][] vis, int idx, char[][] board, String word) {
        if (idx >= word.length()) return true;
        for (int i = 0; i < 4; i++) {
            int l = x + dx[i], r = y + dy[i];
            // 判断进入下一层递归的条件
            if (l < board.length && l >= 0 && r < board[0].length && r >= 0 && !vis[l][r] && board[l][r] == word.charAt(idx)) {
                vis[l][r] = true;
                if (dfs(l, r, vis, idx + 1, board, word)) return true;  // 将每层递归的结果依次返回
                vis[l][r] = false;  // 恢复现场
            }
        }
        return false;
    }
}

---

80. 删除有序数组中的重复项 II

---

• 双指针
  • 由于数组有序，显然存在重复的数可以由区间边界来替换
  • i 表示某数字重复两次之后的右边界，j 用于遍历找到第一个和 nums[i - 2] 不同的位置
  • 此时，说明 j 为第一个不重复的数字的左边界，那么更新 nums[i] = nums[j] 即可

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) return n;
        int i = 2, j = 2;
        for (; j < n; j++) {
            if (nums[i - 2] != nums[j]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

---

81. 搜索旋转排序数组 II

---

• 模拟，遍历数组查找目标值

class Solution {
    public boolean search(int[] nums, int target) {
        for (int p : nums) {
            if (p == target) return true;
        }
        return false;
    }
}

---

82. 删除排序链表中的重复元素 II

---

• 模拟
  • 对于当前的指针，需要遍历判断后面是否存在相同值的节点
  • 如果存在相同元素，则继续向后遍历，直到不存在相同值的节点
  • 之后更新指针指向最后一个没有相同值节点即可

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode ans = res;
        while (res.next != null) {
            // res 是上一轮找过的，因此默认为 res.next 是当前指针
            ListNode st = res.next;
            boolean flag = false;
            while (st.next != null && st.val == st.next.val) {
                st = st.next;
                flag = true;
            }
            if (flag) {
                res.next = st.next;
            } else {
                res = res.next;
            }
        }
        return ans.next;
    }
}

---

83. 删除排序链表中的重复元素

---

• 思路和 82 一致
  • 只不过这次只需要留一个

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode res = head;
        ListNode ans = res;
        while (res != null) {
            ListNode st = res.next;
            while (st != null && st.val == res.val) {
                st = st.next;
            }
            res.next = st;
            res = res.next;
        }
        return ans;
    }
}

---

84. 柱状图中最大的矩形

---

• 单调栈
  • 对于 heights[i]，需要快速判断出其左边第一个小于它的位置 l[i] 和右边第一个小于它的位置 r[i]
  • 那么最高的矩形即为所有 (r[i] - l[i]) * heights[i] 的最大值

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stl = new Stack<>();
        Stack<Integer> str = new Stack<>();
        int[] l = new int[heights.length];
        int[] r = new int[heights.length];
        for (int i = 0; i < heights.length; i++) {
            while (!stl.isEmpty() && heights[stl.peek()] >= heights[i]) {
                stl.pop();
            }
            if (stl.isEmpty()) {
                l[i] = -1;
            } else {
                l[i] = stl.peek();
            }
            stl.push(i);
        }
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!str.isEmpty() && heights[str.peek()] >= heights[i]) {
                str.pop();
            }
            if (str.isEmpty()) {
                r[i] = heights.length;
            } else {
                r[i] = str.peek();
            }
            str.push(i);
        }
        int ans = heights[0];
        for (int i = 0; i < heights.length; i++) {
            ans = Math.max(ans, (r[i] - l[i] - 1) * heights[i]);
        } 
        return ans;
    }
}

---

85. 最大矩形

---

• 解法一：暴力枚举（模拟）
  • 通过预处理，计算出 matrix[i][j] 下方（包括自身）连续 1 的最大高度，并用一个辅助数组 heights 暂存
  • 遍历矩阵的每一行，将每一行都看作一个柱状图的基底，利用 heights 数组计算以该行为底的最大矩形面积

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] vis = new int[n][m];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                for (int k = i; k < n; k++) {
                    if (matrix[k][j] == '1') {
                        cnt++;
                    } else {
                        break;
                    }
                }
                vis[i][j] = cnt;
                ans = Math.max(ans, cnt);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    int cnt = 1;
                    int res = vis[i][j];
                    int k = j + 1;
                    for (; k < m; k++) {
                        if (matrix[i][k] == '1') {
                            cnt++;
                            res = Math.min(res, vis[i][k]);
                        } else {
                            break;
                        }
                        ans = Math.max(ans, Math.max(cnt, cnt * res));
                    }
                    ans = Math.max(ans, Math.max(cnt, cnt * res));
                }
            }
        }

        return ans;
    }
}

---

86. 分隔链表

---

• 模拟
  • 创建两个虚拟头节点 l 和 r，分别用于存储小于 x 和大于等于 x 的节点
  • 遍历链表，根据每个节点的值将其连接到相应的部分
  • 最后，将两个部分连接在一起，并返回新的链表头

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode l = new ListNode(0);
        ListNode r = new ListNode(0);
        ListNode lh = l;
        ListNode rh = r;
        for (ListNode i = head; i != null; i = i.next) {
            if (i.val < x) {
                l.next = new ListNode(i.val);
                l = l.next;
            } else {
                r.next = new ListNode(i.val);
                r = r.next;
            }
        }
        l.next = rh.next;
        return lh.next;
    }
}

---

87. 扰乱字符串

---

• 区间 dp

class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        boolean[][][] dp = new boolean[n][n][n + 1];
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
}

---

88. 合并两个有序数组

---

• 模拟
  • 本质是归并过程
  • 倒序合并即可

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

---

89. 格雷编码

---

• 数学
  • 第 i 个格雷码为 \(i \oplus \left\lfloor \frac{i}{2} \right\rfloor\)
  • 参照公式生成即可

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < 1 << n; i++) {
            ans.add((i >> 1) ^ i);
        }
        return ans;
    }
}

---

90. 子集 II

---

• DFS
  • 由于存在重复元素，子集遇到重复元素直接跳过即可
  • 先对数组排序，防止跳过不该跳的元素

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        dfs(nums, 0);
        return ans;
    }

    private void dfs(int[] nums, int startIndex) {
        ans.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> ans;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans = new ArrayList<>();
        Arrays.sort(nums);  // 排序数组，确保可以正确跳过重复元素
        for (int i = 0; i <= nums.length; i++) {
            List<Integer> res = new ArrayList<>();
            dfs(0, i, nums, res);
        }
        return ans;
    }

    private void dfs(int u, int k, int[] nums, List<Integer> res) {
        if (res.size() == k) {
            ans.add(new ArrayList<>(res));
            return;
        }
        for (int i = u; i < nums.length; i++) {
            if (i > u && nums[i] == nums[i - 1]) continue;  // 跳过重复元素
            res.add(nums[i]);
            dfs(i + 1, k, nums, res);
            res.remove(res.size() - 1);  // 回溯
        }
    }
}