刷穿力扣（61~90）
liyusendesu
|
Q&A
|
|
729
|
0

3393 字
|
45 分钟
本文最后更新于 50 天前，其中的信息可能已经有所发展或是发生改变。

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

  • 乱拳打死老师傅，还用得上 DFA 🤣👉🤡？

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 {
            // 有进位说明只可能是 ⑨⑨⑨⑨⑨⑨⑨⑨⑨ 这种的，加一后必然是 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 顶层的目录出栈
                st.pop();
            } else if (!vis.contains(op)) {
                // 不是特殊目录符，将其加入栈中
                st.push(op);
            }
        }
        StringBuilder ans = new StringBuilder();
        // 依次对 st 中的目录添加 '/'
        for (String op : st) {
            ans.insert(0, "/" + op);
        }
        return ans.length() > 0 ? ans.toString() : "/";
    }
}

72. 编辑距离

  • dp
  • 对于 word1，我们默认或者长度
  • 那么，可以考虑从 $0$ 开始构建 word2
  • 状态表示：
    • dp[i][j] 表示从 word1[i] 转换到 word2[j] 需要的最少操作
    • 注意初始化阶段，以两种极端方案来看，全部添加或全部删除
    • 全部添加即将 word1 视作长度为 $0$ 的一个空字符串，则从 $0$ 开始构建需要的操作次数为 dp[i][0] = dp[i - 1][0] + 1
    • 全部删除即将 word1 一直删除直到和 word2 相同为止，即需要的操作次数为 dp[0][j] = dp[0][j - 1] + 1
  • 状态计算：
    • 先判断 word1.charAt(i - 1) 和 word2.char(j - 1) 是否相同，若相同则不需要转换
    • 否则在替换、增加、删除之间取最小操作值更新到 dp[i][j]，即 dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, 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();
        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] == 1:
    • 说明需要将其加入到 r 右边的区间
    • 故将 nums[i] 和 nums[r] 的值交换，且 r 边界向左移
  • 对于 i 的移动，若 nums[i] == 2 不需要后移，因为不确定由 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];  // 存储已经走过的位置 {i, j} 标记为 true 说明已经走过
                    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 = new ListNode(0);
        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]) * heigths[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 的最大长度，用 vis 暂存
  • 遍历 matrix，对于 matrix[i][j]：
    • 设 cnt 为连续 1 的长度，res 为 vis[i][j] 的最小值
    • 则 ans = max(ans, max(cnt, cnt * res))
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{2}{i} \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;

    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);  // 回溯
        }
    }

    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;
    }
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
1346. 回文平方(进制转换模板)

							
							

							
AtCoder Beginner Contest 261 (A·B·C·D)

							
							

							
Educational Codeforces Round 137 (Rated for Div. 2)（A~D）

							
							

							
ABC的整除问题

							
							

							
剪绳子

							
							

							
Codeforces Round #808 (Div 2.) A·B·C