本文最后更新于 132 天前,其中的信息可能已经有所发展或是发生改变。
-
模拟
-
结合代码如下列过程所示:
-
| 1 -> 2 -> 3 -> 4 -> 5 -> null |
-
| 1 -> 2 -> 3 -> 4 -> 5 -> null |
-
| 1 -> 2 -> 3 -> null 4 -> 5 -> null |
| | | | | |
| head cnt ans res |
-
| 4 -> 5 -> 1 -> 2 -> 3 -> null |
| | | | | |
| 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; |
| } |
| |
| if ((k %= len) == 0) return head; |
| ListNode cnt = head; |
| for (int i = 1; i < len - k; i ++) cnt = cnt.next; |
| ListNode ans = cnt.next; |
| cnt.next = null; res.next = head; |
| return ans; |
| } |
| } |
- 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]; |
| } |
| } |
- 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; |
| else if (j > 0) { |
| dp[j] += dp[j - 1]; |
| } |
| } |
| } |
| return dp[m - 1]; |
| } |
| } |
- 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]; |
| } |
| } |
-
模拟
-
设 flag1 flag2 flag3
来记录数字、小数点和指数的出现情况
-
如果字符是数字:
-
如果字符是小数点,则检查小数点之前是否已经出现小数点或指数
- 如果是,直接返回
false
- 否则
flag1 = 1
,表示小数点已经出现
-
如果字符是 e
、E
,则检查指数符号之前是否已经出现指数或数字:
- 如果是,直返回
false
- 否则
flag3 = 1
,表示指数符号已经出现,且 flag2 = 0
,指数后面需要出现整数
-
如果字符是 -
、+
,检查该符号字符出现的位置:
- 出现在字符串的开头,
- 或者出现在
'e'
或 'E'
的后面
- 如果不满足上述条件这,直接返回
false
-
如果字符不是数字、小数点、指数符号或符号字符,直接 false
-
遍历完字符串后,如果数字已经出现过(即 flag2 == 1
),则返回 true
;否则返回 false
-
乱拳打死老师傅,还用得上 DFA ![🤣](https://s.w.org/images/core/emoji/15.0.3/svg/1f923.svg)
![👉](https://s.w.org/images/core/emoji/15.0.3/svg/1f449.svg)
?
| 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; |
| } |
| } |
- 模拟
- 原理就是大整数的加和过程
- 用
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; |
| else { |
| |
| int[] ans = new int[n + 1]; ans[0] = 1; |
| return ans; |
| } |
| } |
| } |
- 模拟
- 本质也是大整数加和过程
- 先对
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(); |
| 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(); |
| } |
| } |
- 贪心
- 遍历
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; |
| } |
| } |
- 二分
- 板子题
- 二分期间不断判断
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; |
| else l = mid + 1; |
| } |
| return (int)l - 1; |
| } |
| } |
- dp
- 板子题
- 状态表示:
- 状态计算:
- 第
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; |
| } |
| } |
- 栈
- 首先将原来的路径以
'/'
进行分割,对每个分割后的路径进行判断:
- 如果是
"."
说明是当前目录保持不变,无需处理
- 如果是
""
说明这是 "//"
分割的结果,也无需处理
- 如果是
".."
则说明要返回上一级目录
- 因此我们需要一个栈
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() : "/"; |
| } |
| } |
- 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]; |
| } |
| } |
- 模拟
- 用
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; |
| } |
| } |
| } |
- 二分
- 第一次二分,根据每一行的最大值确定在哪一行
- 第二次二分,在对应行中确定是否存在
| 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; |
| } |
| } |
- 双指针
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 ++; |
| } |
| } |
| } |
- 滑动窗口
- 利用
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] ++; |
| |
| 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); |
| } |
| } |
| 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); |
| res.remove(res.size() - 1); |
| } |
| } |
| } |
- 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); |
| } |
| } |
| } |
- 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; |
| } |
| } |
- 双指针
- 由于数组有序,显然存在重复的数可以由区间边界来替换
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; |
| } |
| } |
| class Solution { |
| public boolean search(int[] nums, int target) { |
| for (int p : nums) { |
| if (p == target) return true; |
| } |
| return false; |
| } |
| } |
- 模拟
- 对于当前的指针,需要遍历判断后面是否存在相同值的节点
- 如果存在相同元素,则继续向后遍历,直到不存在相同值的节点
- 之后更新指针指向最后一个没有相同值节点即可
| 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) { |
| |
| 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; |
| } |
| } |
| 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; |
| } |
| } |
- 单调栈
- 对于
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; |
| } |
| } |
- 模拟
- 力大砖飞,预处理一下
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; |
| } |
| } |
- 模拟
- 创建两个虚拟头节点
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; |
| } |
| } |
| 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]; |
| } |
| } |
| 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 --]; |
| } |
| } |
| } |
- 数学
- 第 i 个格雷码为 i⊕⌊i2⌋
- 参照公式生成即可
| 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; |
| } |
| } |
- 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; |
| } |
| } |