本文最后更新于 7 天前,其中的信息可能已经有所发展或是发生改变。
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))
- 设 cnt 为连续 1 的长度,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;
}
}