刷穿力扣(61~90)
本文最后更新于 132 天前,其中的信息可能已经有所发展或是发生改变。

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] 表示到达 ij 列的方案数量
    • 初始化 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] 到达 ij 列的方案数量
    • 初始化,当 obstacleGrid[0][i] != 1obstacleGrid[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] != 1dp[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] 到达 ij 列的最小步数
    • 初始化,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,表示小数点已经出现
  • 如果字符是 eE,则检查指数符号之前是否已经出现指数或数字:

    • 如果是,直返回 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 - 1i - 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,我们默认或者长度
  • 那么,可以考虑从 00 开始构建 word2
  • 状态表示:
    • dp[i][j] 表示从 word1[i] 转换到 word2[j] 需要的最少操作
    • 注意初始化阶段,以两种极端方案来看,全部添加或全部删除
    • 全部添加即将 word1 视作长度为 00 的一个空字符串,则从 00 开始构建需要的操作次数为 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 及其之前的区间内都为 0lr 之间的区间内都为 1r 右边的区间都为 2
  • 初始化 l = 0, r = nums.length - 1l 视为最后一个 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 = 0i = 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. 分隔链表


  • 模拟
  • 创建两个虚拟头节点 lr,分别用于存储小于 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 个格雷码为 i2ii \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
小恐龙
花!
上一篇
下一篇