- 2. 两数相加
- 3. 无重复字符的最长子串
- 5. 最长回文子串
- 25. K 个一组翻转链
- 42. 接雨水
- 56. 合并区间
- 22. 括号生成
- 15. 三数之和
- 103. 二叉树的锯齿形层序遍历
- 143. 重排链表
- 46. 全排列
- 31. 下一个排列
- 200. 岛屿数量
- 128. 最长连续序列
- 135. 分发糖果
- 33. 搜索旋转排序数组
- 215. 数组中的第K个最大元素
- 300. 最长递增子序列
- 41. 缺失的第一个正数
- 76. 最小覆盖子串
- 11. 盛最多水的容器
- 32. 最长有效括号
- 55. 跳跃游戏
- 124. 二叉树中的最大路径和
- 43. 字符串相乘
- 54. 螺旋矩阵
- 72. 编辑距离
- 105. 从前序与中序遍历序列构造二叉树
- 34. 在排序数组中查找元素的第一个和最后一个位置
- BD: 寻找数组中和为 K 的 N 倍的最短连续子序列
2. 两数相加
中等 链表、哨兵 原题链接：https://leetcode-cn.com/problems/add-two-numbers/
⚠️：千万不要忘记进位
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode sentry = new ListNode(-1);ListNode prev = sentry;ListNode p1 = l1, p2 = l2;int accNext = 0;while(p1 != null || p2 != null || accNext != 0) {int sum = accNext;if (p1 != null) {sum += p1.val;p1 = p1.next;}if (p2 != null) {sum += p2.val;p2 = p2.next;}ListNode node = new ListNode(sum % 10);accNext = sum / 10;prev.next = node;prev = node;}return sentry.next;}}
3. 无重复字符的最长子串
中等 双指针、哈希 原题链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
class Solution {public int lengthOfLongestSubstring(String s) {int i =0, j = 0, ans = 0, n = s.length();Set<Character> set = new HashSet<>();while(j < n) {if (!set.contains(s.charAt(j))) {set.add(s.charAt(j));ans = Math.max(j - i + 1, ans);j++;} else {set.remove(s.charAt(i));i++;}}return ans;}}
5. 最长回文子串
中等 DP 原题链接：https://leetcode-cn.com/problems/longest-palindromic-substring
class Solution {public String longestPalindrome(String s) {int n = s.length();if (n <= 0) {return "";}boolean[][] dp = new boolean[n][n];for(int i = 0; i < n; i++) {Arrays.fill(dp[i], true);}int max = 1, s0 = 0, s1 = 0;for(int j = 0; j < n; j++) {for(int i = 0; i < j; i++) {dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);if (dp[i][j]) {int len = j - i + 1;if (len > max) {max = len;s0 = i;s1 = j;}}}}return s.substring(s0, s1 + 1);}}
25. K 个一组翻转链
HARD 👹在细节 原题链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/ 2021-11-03 21:37:37 第一次练习耗时 60 分钟完成 OJ，需要返场复习
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 哨兵模式ListNode sentry = new ListNode(-1);ListNode cur = head;ListNode phaseStart = cur, curPhaseLeft = sentry, curPhaseRight = null;int count = 0;while (cur != null) {// 计数count++;// 存储 next 快照，防止接下来的操作改变 cur 的 next 指针ListNode next = cur.next;// 进行翻转if (count % k == 0) {// 反转开始前，设置当前段 phaseRightcurPhaseRight = cur.next;// 开始翻转reverseList(phaseStart, curPhaseRight, curPhaseLeft);// 反转完成后，需要设置下一段 curPhaseLeft 和 phaseStartcurPhaseLeft = phaseStart;phaseStart = curPhaseRight;}cur = next;}return sentry.next;}// 反转列表public void reverseList(ListNode head, ListNode right, ListNode left) {ListNode prev = right;ListNode cur = head;ListNode next;while(true) {next = cur.next;cur.next = prev;prev = cur;// cur 需要保留在翻转列表范围内，后续的 left 需要用到if (next == right) {break;}cur = next;}if (left != null) {left.next = cur;}}}
42. 接雨水
HARD DP 原题链接：https://leetcode-cn.com/problems/trapping-rain-water/
双指针版本也是从 DP 演化过来的，具体看原题图解。
DP 版本
class Solution {
public int trap(int[] height) {
if (height.length < 2) {
return 0;
}
int n = height.length;
// DP 做法
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for(int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
rightMax[n-1] = height[n - 1];
for(int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// 按列扫描，累加雨水，其中边界柱是无法储蓄雨水的
int sum = 0;
for(int i = 1; i < n - 1; i++) {
sum += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return sum;
}
}
自己想到了按行扫描，复杂度为 O(n2)，但好在 30min 内做了出来。
56. 合并区间
中等 排序、reduce 原题链接：https://leetcode-cn.com/problems/merge-intervals/
使用函数库排序的情况下，可以在 25min 内完成答题
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length < 1) {
return new int[0][0];
}
int n = intervals.length;
// 首先需要通过区间左边界，对数据进行升序排序，可以自己实现快排
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
// 两两进行合并操作
List<int[]> result = new ArrayList<>();
// 当前处理游标
int[] curRange = intervals[0];
for(int i = 1; i < n; i++) {
int[] interval = intervals[i];
if (curRange[1] >= interval[0] && curRange[1] < interval[1]) {
curRange[1] = interval[1];
} else if (curRange[1] < interval[0]) {
// 添加到合并区间
result.add(curRange);
curRange = interval;
}
}
// 补充末尾范围数组
result.add(curRange);
// 返回结果集
return result.toArray(new int[result.size()][]);
}
}
22. 括号生成
中等 回溯 原题链接：https://leetcode-cn.com/problems/generate-parentheses/
class Solution {
private List<String> rtn = new ArrayList();
public List<String> generateParenthesis(int n) {
// 尝试回溯法填充
travel("", n, n);
return rtn;
}
public void travel(String cur, int left, int right) {
// 任何时刻，左括号剩余 <= 右括号剩余
// 终止条件：非法括号对
if (left > right || left < 0 || right < 0) {
return;
}
// 终止条件：合法括号对
if (left == 0 && right == 0) {
rtn.add(cur);
return;
}
// 函数入参不要轻易用自增自减，变量之间容易相互干扰，请慎重
travel(cur + "(", left - 1, right);
travel(cur + ")", left, right - 1);
}
}
15. 三数之和
中等 双指针、排序 原题链接：https://leetcode-cn.com/problems/3sum/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> rtnList = new ArrayList<>();
int n = nums.length;
if (n < 3) {
return rtnList;
}
// 先进行排序
Arrays.sort(nums);
// 三重循环，去重 需要保证三个位置的值 a <= b <= c，且同一层级不能有重复值
for(int first = 0; first < n; first++) {
// 双指针，可以降低 1 维的复杂度
int third = n - 1;
// 去重过滤
if (first != 0 && nums[first] == nums[first -1]) {
continue;
}
// 进入下一层的条件
for (int second = first + 1; second < n; second++) {
// 进入下一层的条件
if (second != first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while(second < third) {
// third 的重复值判断，其实通过 second 的双指针已经传递过来了
// 大于 0 则 左移，缩小总值
if (nums[second] + nums[third] + nums[first] > 0) {
third--;
continue;
}
// 找到满足条件的记录，终止查询
if (nums[second] + nums[third] + nums[first] == 0) {
// 添加条件
rtnList.add(
Arrays.asList(
nums[first],
nums[second],
nums[third]
)
);
third--;
}
// 总值小于 0 的情况下，依旧没有匹配的话，也可以终止
break;
}
}
}
return rtnList;
}
}
103. 二叉树的锯齿形层序遍历
中等 BFS、队列 原题链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> rtnList = new ArrayList();
if (root == null) {
return rtnList;
}
int count = 0;
Deque<TreeNode> deque = new LinkedList();
deque.offerLast(root);
while(!deque.isEmpty()) {
int len = deque.size();
// 必要时候可以直接使用实现类，这在编程中是允许的
LinkedList<Integer> list = new LinkedList();
for(int i = 0; i < len; i++) {
TreeNode node = deque.pollFirst();
if (node.left != null) {
deque.offerLast(node.left);
}
if (node.right != null) {
deque.offerLast(node.right);
}
// 通过状态位实现 zigzag
if (count % 2 == 0) {
// 正序
list.offerLast(node.val);
} else {
// 倒序
list.offerFirst(node.val);
}
}
rtnList.add(list);
// 下一轮
count++;
}
return rtnList;
}
}
143. 重排链表
中等 链表、双指针 原题链接：https://leetcode-cn.com/problems/reorder-list/
线性列表解，空间复杂度为 O(n)
方案 1: 使用数组容器进行节点存储，再通过双指针取首尾节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
// 1 更好实现
// 方案 1: 使用数组容器进行节点存储，再通过双指针取首尾节点
List<ListNode> list = new ArrayList();
ListNode cur = head;
while( cur != null) {
list.add(cur);
cur = cur.next;
}
// 进行新链表生成
ListNode sentry = new ListNode(-1);
cur = sentry;
int i = 0, j = list.size() - 1;
while (i <= j) {
if (i == j) {
cur.next = list.get(i);
cur = cur.next;
} else {
cur.next = list.get(i);
cur.next.next = list.get(j);
cur = cur.next.next;
}
// 指针收缩
i++;
j--;
}
// 防止形成环
cur.next = null;
head = sentry.next;
}
}
方案 2: 先遍历列表，拆分前后两个列表，再进行编织，空间复杂度为 O(1)
class Solution {
public void reorderList(ListNode head) {
ListNode mid = middleNode(head);
// l1.length >= l2.length, mid 节点属于 l1
ListNode l1 = head;
ListNode l2 = reverseList(mid.next);
// 防止回环，同时设定 l1 边界条件
mid.next = null;
// 合并列表
ListNode sentry = new ListNode(0);
ListNode cur = sentry;
while(l1 != null) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
if (l2 != null) {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
head = sentry.next;
}
// 寻找中间点，快慢指针
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null) {
fast = fast.next;
// 注意快慢指针的判定条件
if (fast != null && fast.next != null) {
fast = fast.next;
} else {
break;
}
slow = slow.next;
}
return slow;
}
// 反转列表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
46. 全排列
中等 回溯、DFS 原题链接：https://leetcode-cn.com/problems/permutations/
class Solution {
private List<List<Integer>> rtnList = new ArrayList<>();
private List<Integer> ans = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
// 方便元素增删
List<Integer> bucket = new ArrayList<>();
for(int i = 0; i < nums.length; i++) {
bucket.add(nums[i]);
}
dfs(bucket);
return rtnList;
}
// 回溯，也可以叫做 backtrack
public void dfs(List<Integer> bucket) {
if (bucket.isEmpty()) {
rtnList.add(new ArrayList(ans));
}
// 得做拷贝
List<Integer> cloneArr = new ArrayList(bucket);
// 注意本题的大背景，元素唯一不重复，这为这里的元素增删带来了极大的方便
for(Integer num : cloneArr) {
// 下钻
ans.add(num);
bucket.remove(num);
dfs(bucket);
// 还原
bucket.add(num);
ans.remove(num);
}
}
}
31. 下一个排列
中等 双指针、排序 原题链接：https://leetcode-cn.com/problems/next-permutation/
自己的做法，虽然不是最优解，但有点意思，平均复杂度接近 O(nlogn)，最差复杂度 O(n2)，OJ 时间在 1ms
class Solution {
public void nextPermutation(int[] nums) {
// 下一个更大：低位数字往高位数字，做最小的移动
// 1 3 2 => 2 移动到 1 的位置，右侧数升序排列 2 1 3
// 2 1 3 => 2 3 1
// 2 3 1 => 3 1 2
// 寻找可能的换位 + 换位右侧数字升序排列
int bestI = -1, bestJ = -1;
int n = nums.length;
// 右指针
for(int j = n - 1; j >= 0; j--) {
// 不可能找到更好的了，可以剪枝
if (j <= bestI) {
break;
}
// 左指针
for(int i = j - 1; i >= 0; i--) {
// 针对这类数据 [4,2,0,2,3,2,0] 的处理逻辑
if (nums[i] < nums[j]) {
// 必须是 >，由于进制问题，之后发现相同的 i 一定大于先前发现的 i
if (i > bestI) {
bestI = i;
bestJ = j;
}
}
}
}
if (bestI > -1) {
// 交换逻辑
swap(nums, bestI, bestJ);
// 换位右侧数字升序排列
Arrays.sort(nums, bestI + 1, n);
} else {
// 还原：升序排序
reverse(nums);
}
}
// 反转逻辑，涨知识了
public void reverse(int[] nums) {
// 1 2 3 4 5
// 5 4 3 2 1
int left = 0, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
// 交换逻辑
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
官方做法，好家伙，直接干到了 O(n)，也非常好理解：
class Solution {
public void nextPermutation(int[] nums) {
// 寻找第一个降序数（右->左视角）
int i = nums.length - 2;
while(i >= 0 && nums[i] >= nums[i+1]) {
i--;
}
// 寻找右侧最小的比降序数大的数
int j = nums.length - 1;
while(i > -1 && nums[j] <= nums[i]) {
j--;
}
// 交换位置
if (i > -1) {
swap(nums, i, j);
}
// 这个有个数据特性，不太容易想到
// i 右侧的所有数字，一定是降序排列的（左->右视角）
reverse(nums, i + 1);
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while(left < right) {
swap(nums, left, right);
left++;
right--;
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
200. 岛屿数量
中等 回溯、标记 原题链接：https://leetcode-cn.com/problems/number-of-islands
10 分钟完成，确实有进步了。
class Solution {
private int m,n;
public int numIslands(char[][] grid) {
// 回溯 + 标记（防止重复访问）
m = grid.length;
// 1 <= m, n <= 300，所以是安全的
n = grid[0].length;
int count = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
// 约定 x 为访问过的陆地，不需要重复访问
if (grid[i][j] == '1') {
backtrack(grid, i, j);
count++;
}
}
}
return count;
}
public void backtrack(char[][] grid, int i, int j) {
// 越界终止搜索
if (i < 0 || i >=m || j < 0 || j >=n) {
return;
}
if (grid[i][j] == '1') {
grid[i][j] = 'x';
} else {
// 不匹配终止搜索
return;
}
// 四方向搜索
// 上
backtrack(grid, i - 1, j);
// 右
backtrack(grid, i, j + 1);
// 下
backtrack(grid, i + 1, j);
// 左
backtrack(grid, i, j - 1);
}
}
128. 最长连续序列
中等 哈希、双指针 原题链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/
自己在 25 分钟内实现，击败 100% 提交的代码，利用 排序 + 双指针实现，OJ 时间在 10ms
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length < 1) {
return 0;
}
// O(nlogn) 做法，排序 + 双指针
Arrays.sort(nums);
int n = nums.length, max = 1;
int i = 0, j = 1;
while (j < n) {
if (nums[j - 1] + 1 == nums[j]) {
max = Math.max(j - i + 1, max);
j++;
} else if (nums[j - 1] == nums[j]) {
// 去重处理，整体滑动
// 1 2 2 3 4
i++;
j++;
} else {
i = j;
j++;
}
}
return max;
}
}
官方的做法：哈希表 + 寻找非连续值作为起始节点，OJ 时间在 250ms，理论时间复杂度在 O(n)，目测额外时间消耗在哈希表内部。
但这个算法很好理解，但遇到重复元素也要计数的话，处理起来会很棘手。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
for(int i = 0; i < n; i++) {
set.add(nums[i]);
}
int max = 0;
for(int i = 0; i < n; i++) {
int num = nums[i];
// 寻找非连续值作为起始节点
if (set.contains(num - 1)) {
continue;
}
int count = 1;
while(set.contains(++num)) {
count++;
}
max = Math.max(count, max);
}
return max;
}
}
135. 分发糖果
困难 边界控制很多，记得写注释，提醒自己 原题链接：https://leetcode-cn.com/problems/candy/
自己的解法，接近 45 min 内完成，可以鼓励下，OJ 时间在 3ms
class Solution {
public int candy(int[] ratings) {
// [1, 2, 8, 4, 3, 2, 1]
// 其中 8 位交叉点（山峰）= Math.max(left, right)
// 我们遍历的时候，只需要记住交叉点，然后进行填值即可
int joint = -1, n = ratings.length;
int[] candies = new int[n];
for(int i = 0; i < n; i++) {
if (i + 1 < n && ratings[i] >= ratings[i+1]) {
// 找到并记录山峰
if (joint == -1) {
joint = i;
}
} else {
if (joint != -1) {
int count = 1;
for(int j = i; j > joint; j--) {
candies[j] = count;
if (ratings[j] < ratings[j-1]) {
count++;
} else {
// 注意在此题中，分数相同的情况下，我可以比你分到的糖果少
// [1,3,2,2,1] 可以降啊
// [1,2,1,2,1]
count = 1;
}
}
// 交叉点（山峰）= Math.max(left, right)
int leftPeek = joint - 1 < 0 ? 1 :
(ratings[joint] > ratings[joint-1] ? candies[joint-1] + 1 : candies[joint-1]);
candies[joint] = Math.max(count, leftPeek);
// 重置山峰
joint = -1;
} else {
candies[i] = i - 1 < 0 ? 1 : candies[i-1] + 1;
}
}
}
return sum(candies);
}
// 求和函数
public int sum(int[] candies) {
int ans = 0;
for(int i = 0; i < candies.length; i++) {
ans += candies[i];
}
return ans;
}
}
官方的魔性解法，两遍遍历，山峰思想的极致，OJ 时间也在 3ms：
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
// 采用左右扫描的方式
int[] left = new int[n];
int[] right = new int[n];
int ans = 0;
// 1 0 2
// L 1 1 2
// R 2 1 1
// M 2 1 2
for(int i = 0; i < n; i++) {
if (i - 1 < 0 || ratings[i] <= ratings[i-1]) {
left[i] = 1;
} else {
left[i] = left[i-1] + 1;
}
}
for(int j = n - 1; j >=0; j--) {
if (j + 1 >= n || ratings[j] <= ratings[j+1]) {
right[j] = 1;
} else {
right[j] = right[j+1] + 1;
}
ans += Math.max(right[j], left[j]);
}
return ans;
}
}
33. 搜索旋转排序数组
中等 二分、边界 原题链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
自己 25 min 内实现的版本，惟一有理解难度的是“右侧的越界检查”，OJ 0ms，超过 100%
class Solution {
public int search(int[] nums, int target) {
// 值互不相同、有序数组
// O(log n) -> 二分？，特殊边界的处理
// 0 1 2 3 4 5 6 - 下标
// 4 5 6 7 0 1 2 - 值
// 查找 1
// 任何一次二分之后，有一段是正常升序的，如果不在正常序内，则尝试另一侧
// 1: mid = 7(3) > 1 4(0) > 1 选择右侧
// 0 1 2
// 翻转示例 2
// 0 1 2 3 4 5 6 - 下标
// 2 4 5 6 7 0 1 - 值
return binarySearch(nums, target, 0, nums.length - 1);
// O(n) 遍历，很简单
}
public int binarySearch(int[] nums, int target, int i, int j) {
// 非法未找到
if (i > j) {
return -1;
}
// 终止-找到
int mid = (i + j) / 2;
if (nums[mid] == target) {
return mid;
}
// 分成两段 [i, mid], [mid + 1, j]
// 左侧正常
if(nums[i] < nums[mid]) {
if (target >= nums[i] && target < nums[mid]) {
return binarySearch(nums, target, i, mid -1);
} else {
return binarySearch(nums, target, mid + 1, j);
}
} else {
// 判断边界条件，防止越界
if (mid + 1 >= nums.length) {
return -1;
}
// 右侧正常
if (target >= nums[mid + 1] && target <= nums[j]) {
return binarySearch(nums, target, mid + 1, j);
} else {
return binarySearch(nums, target, i, mid -1);
}
}
}
}
215. 数组中的第K个最大元素
中等 快排、堆 原题链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/submissions/
快排做法：
class Solution {
public int findKthLargest(int[] nums, int k) {
// 快排（倒序） + topK 问题
// 这里有坑：下标 + 1 = k
return quickSort(nums, 0, nums.length - 1, k - 1);
}
// 快排
public int quickSort(int[] nums, int i, int j, int index) {
if (i > j) {
return - 1;
}
int p = partition(nums, i, j);
if (p == index) {
return nums[p];
}
if (p < index) {
return quickSort(nums, p + 1, j, index);
} else {
return quickSort(nums, i, p - 1, index);
}
}
// 分区，返回分区点
public int partition(int[] nums, int p, int q) {
int pivot = nums[q];
// 1 4 2 3
// i (4, 2) 换位，i++
int i = p, j = p;
for(; j < q; j++) {
if (nums[j] >= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, q);
return i;
}
public void swap(int[] nums, int i, int j) {
if (i == j) {
return;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
300. 最长递增子序列
中等 dp 原题链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
动态规划，时间复杂度在 O(n2)，空间复杂度 O(n)，代码不难，不太容易想到。
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length < 1) {
return 0;
}
// 其中 dp[i] 必须被选取，这是本题的题眼。
// dp[i] = dp[j] + 1 其中 0 <= j < i，nums[j] < nums[i]
int n = nums.length;
int[] dp = new int[n];
int maxAns = 1;
for(int i = 0; i < n; i++) {
dp[i] = 1;
for(int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxAns = Math.max(dp[i], maxAns);
}
return maxAns;
}
}
41. 缺失的第一个正数
困难 原地标记处理 原题链接：https://leetcode-cn.com/problems/first-missing-positive/
class Solution {
public int firstMissingPositive(int[] nums) {
// 一个长度为 N 的数组，最多存储 N 个正整数，所以缺失的最大正整数为 N + 1
int n = nums.length;
// 首次遍历，先清空数组中的负数，后续负数将作为标记位
for(int i = 0; i < n; i++) {
if (nums[i] <= 0 ) {
nums[i] = n + 1;
}
}
// 存在数 |x| 在 [1, N] 范围内，则标记 nums[|x| -1] = -|nums[|x| -1]|，
for(int i = 0; i < n; i++) {
int absVal = Math.abs(nums[i]);
if (absVal > n) {
continue;
}
nums[absVal - 1] = -Math.abs(nums[absVal - 1]);
}
// 寻找第一个非负数的下标，下标 + 1，即为缺失的正数
for(int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
76. 最小覆盖子串
困难 滑动窗口，哈希 原题链接：https://leetcode-cn.com/problems/minimum-window-substring/
class Solution {
public String minWindow(String s, String t) {
// 一定找不到的情况
if (s.length() < t.length()) {
return "";
}
// 建立一个 HashMap，存储该滑动指针内，目标字符数量，保证所有元素 >=目标数
Map<Character, Integer> curTimes = new HashMap<>();
Map<Character, Integer> minTimes = new HashMap<>();
for(int i = 0; i < t.length(); i++) {
Character chr = t.charAt(i);
Integer val = minTimes.computeIfAbsent(chr, (key) -> {
return 0;
});
minTimes.put(chr, val + 1);
}
// 最小连续子串
int minI = -1, minJ = -1, minLen = Integer.MAX_VALUE;
// 左右指针
int i = 0, j = 0;
while(j < s.length()) {
// ABC
// |
// ADOBECODEBANC
// |
Character chrj = s.charAt(j);
// 无效计数
if (minTimes.get(chrj) == null) {
j++;
continue;
}
// 新增计数
int val = curTimes.computeIfAbsent(chrj, (key) -> {
return 0;
});
curTimes.put(chrj, val + 1);
// 如果完全匹配
if (check(curTimes, minTimes)) {
// 则尝试收缩 左边界，直到刚刚好不是完全匹配
// 因为如果每次都是完全匹配的话，本段逻辑会无意义的执行，会超时，算是一个优化点
while(true) {
Character chri = s.charAt(i);
i++;
if (minTimes.get(chri) == null) {
continue;
}
// 先减
curTimes.put(chri, curTimes.get(chri) - 1);
if (curTimes.get(chri) < minTimes.get(chri)) {
break;
}
}
// 设置最短下标，此时 i 是在完全匹配下标的后一位，所以要 i - 1
int actualI = i - 1;
if (j - actualI + 1 < minLen) {
minLen = j - actualI + 1;
minI = actualI;
minJ = j;
}
}
// 继续探索
j++;
}
if(minI >= 0) {
return s.substring(minI, minJ + 1);
}
return "";
}
// 检查是否完全匹配
public boolean check(Map<Character, Integer> curTimes, Map<Character, Integer> minTimes) {
for(Character chr : minTimes.keySet()) {
if (curTimes.get(chr) == null
|| curTimes.get(chr) < minTimes.get(chr) ) {
return false;
}
}
return true;
}
}
11. 盛最多水的容器
中等 双指针 原题链接：https://leetcode-cn.com/problems/container-with-most-water/
class Solution {
public int maxArea(int[] height) {
// 双指针
// |
// [1,8,6,2,5,4,8,3,7]
// |
int n = height.length;
// 每次移动低矮的指针，直到指针重合
int i = 0, j = n - 1;
int max = 0;
while(i < j) {
max = Math.max(
max,
(j - i) * Math.min(height[i], height[j])
);
if (height[i] <= height[j]) {
i++;
} else {
j--;
}
}
return max;
}
}
32. 最长有效括号
困难 栈 原题链接：https://leetcode-cn.com/problems/longest-valid-parentheses/
题眼：
- 栈里存的字符串下标
阻断元素是底部元素，且只保留 1 个
class Solution { public int longestValidParentheses(String s) { // -1 0 2 // ( ) ) ( ( ) // | | <= 底部元素，同时也是阻断元素 Stack<Integer> stack = new Stack<>(); // 栈底：最后一个不匹配的右括号位置下标 stack.push(-1); int max = 0; int n = s.length(); for(int i = 0; i < n; i++) { Character chr = s.charAt(i); if (chr == '(') { stack.push(i); } else { // 先弹一个，阻断元素是孤独的 stack.pop(); if (stack.isEmpty()) { // 如果栈为空，说明当前的右括号为没有被匹配的左括号， // 我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 stack.push(i); } else { // 计算与栈顶元素的下标距离，即为当前下标下的最长合法括号长度 int len = i - stack.peek(); max = Math.max(len, max); } } } return max; } }
55. 跳跃游戏
中等 dp 原题链接：https://leetcode-cn.com/problems/jump-game/
自己实现的，基于可达数组的做法，非常好理解，时间复杂度 O(n)，OJ 时间为 78ms。
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
// 是否可达
boolean[] arrive = new boolean[n];
// 首位必达
arrive[0] = true;
for(int i = 0; i < n; i++) {
// 不可达可以直接终止
if (!arrive[i]) {
break;
}
// 超过或等于边界，直接返回成功
if (i + nums[i] >= n - 1) {
return true;
}
// 继续开拓地图
for(int j = i + 1; j <= i + nums[i]; j++) {
arrive[j] = true;
}
}
// 返回终点结果
return arrive[n - 1];
}
}
也可以把可达数组变成最远距离，空间复杂度就变成了 O(1)
虽然思路差不多，但 OJ 时间变成了 3ms，单次循环计算量确实小了很多。
class Solution {
public boolean canJump(int[] nums) {
int remotestIndex = 0;
int lastIndex = nums.length - 1;
for (int i = 0; i <= remotestIndex; i++) {
remotestIndex = Math.max(remotestIndex, i + nums[i]);
if (remotestIndex >= lastIndex) {
return true;
}
}
return false;
}
}
124. 二叉树中的最大路径和
困难 dp、dfs 原题链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
自答耗时 20 分钟，思路非常清晰：
class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
// 作为非根节点 = max(leftValue, rightValue, 0) + curValue
// 作为子根节点 = curValue + max(leftValue, 0) + max(rightValue, 0)
dfs(root);
return max;
}
// 后序
public int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
// 备份值，防止相互影响
int curValue = root.val;
// 作为非根节点
root.val = Math.max(
Math.max(left, right),
0
) + curValue;
// 作为根节点
int ans = curValue + Math.max(left, 0) + Math.max(right, 0);
max = Math.max(ans, max);
return root.val;
}
}
43. 字符串相乘
中等 细节 原题链接：https://leetcode-cn.com/problems/multiply-strings/
关键点：
- char - ‘0’ = 实际数值
补零操作
class Solution { public String multiply(String num1, String num2) { // 假如 0 后续处理成本很高，就在入口处拦截了 if ("0".equals(num1) || "0".equals(num2)) { return "0"; } // 12 // 12 // ---- // 24 // 120 <- 需要进行补零操作 // 144 = // 以短数为底，减少累加次数 if (num1.length() < num2.length()) { return multiply(num2, num1); } // 执行累进逻辑 int n = num2.length(); String total = "0"; for(int i = n - 1; i >= 0; i--) { StringBuilder sb = new StringBuilder(); sb.append(multiplySingle(num1, num2.substring(i, i+1))); // 进行补零操作 for(int j = i + 1; j < n; j++) { sb.append('0'); } total = add(total, sb.toString()); } return total; } // 单数相乘，num2 是单位 public String multiplySingle(String num1, String num2) { StringBuilder sb = new StringBuilder(); int intNum2 = Integer.parseInt(num2); int n = num1.length(); int i = n - 1, acc = 0; while(i >=0 || acc > 0) { int num1Val = i >= 0 ? num1.charAt(i--) - '0' : 0; int sum = num1Val * intNum2 + acc; sb.append(sum % 10); acc = sum / 10; } // 注意反转 return sb.reverse().toString(); } // 相加 public String add(String num1, String num2) { StringBuilder sb = new StringBuilder(); int m = num1.length(), n = num2.length(); int i = m - 1, j = n - 1, acc = 0; // 注意处理进位 while(i >= 0 || j >= 0 || acc > 0) { int num1Val = i >= 0 ? num1.charAt(i--) - '0' : 0; int num2Val = j >= 0 ? num2.charAt(j--) - '0' : 0; int sum = num1Val + num2Val + acc; sb.append(sum % 10 ); acc = sum / 10; } // 注意反转 return sb.reverse().toString(); } }
54. 螺旋矩阵
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
// 输入限制：1 <= m, n <= 10
int m = matrix.length;
int n = matrix[0].length;
int total = m * n;
// 移动方向
int[][] directions = new int[][]{
// 右
{0, 1},
// 下
{1, 0},
// 左
{0, -1},
// 上
{-1, 0}
};
// 是否访问过
boolean[][] visited = new boolean[m][n];
// 返回结果
List<Integer> rtnList = new ArrayList<>();
int i = 0, j = 0, directionInx = 0;
for(int count = 0; count < total; count++) {
rtnList.add(matrix[i][j]);
visited[i][j] = true;
// 判定下一个元素：转向条件：越界 || 遇到访问过的元素
int[] direction = directions[directionInx % 4];
int nextI = i + direction[0];
int nextJ = j + direction[1];
if (nextI >= m || nextJ >= n || nextJ < 0 || visited[nextI][nextJ]) {
direction = directions[++directionInx % 4];
nextI = i + direction[0];
nextJ = j + direction[1];
}
i = nextI;
j = nextJ;
}
return rtnList;
}
}
72. 编辑距离
多看几遍罢了
class Solution {
public int minDistance(String word1, String word2) {
/**
j = n
|
d 3 3 2 2
o 2 2 1 2
h 1 1 2 3
# 0 1 2 3
# r o s - i = m
dp[i-1][j-1] = 替换操作
dp[i][j-1] = j 新增字符
dp[i-1][j] = i 新增字符
if (word1[i] == word2[j]) {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
}
编码的时候，按照人类直觉去编写，让程序去适配。
内存结构 => 逆时针旋转 90 度
--o o o o
--o => | | |
--o | | |
*/
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 行首初始化
for(int i = 0; i <= m; i++) {
dp[i][0] = i;
}
// 列首初始化
for(int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// 按行进行填充
for(int j = 1; j <= n; j++) {
for(int i = 1; i <=m; i++) {
// 注意这里的下标需要 - 1，因为我们之前对 dp 数组 + 1 了
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(
dp[i-1][j-1],
Math.min(dp[i-1][j], dp[i][j-1])
);
}
}
}
return dp[m][n];
}
}
105. 从前序与中序遍历序列构造二叉树
中等 二叉树特性 原题链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution {
private Map<Integer, Integer> inorderMap = new HashMap();
private int[] preorder;
private int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 记住关键特性：
// 先序列遍历：[根节点，[左子树节点]，[右子树节点]]
// 中序列遍历：[[左子树节点]，根节点，[右子树节点]]
// 相同范围内，不同遍历顺序下，左右子树节点的长度是一样的，
// 利用这个特性，我们可以进行快速构建
this.preorder = preorder;
this.inorder = inorder;
for(int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return myBuildTree(0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode myBuildTree(int preLeft, int preRight, int inorderLeft, int inorderRight) {
if (preLeft > preRight) {
return null;
}
TreeNode root = new TreeNode(preorder[preLeft]);
int inorderMid = inorderMap.get(root.val);
// 构建左子树
int inorderLeftLen = inorderMid - inorderLeft;
root.left = myBuildTree(preLeft + 1, preLeft + inorderLeftLen, inorderLeft, inorderMid - 1);
// 当下标理不清楚的时候，可以写个示例模拟下
// 1 2 3 4
// 构建右子树
int inorderRightLen = inorderRight - inorderMid;
root.right = myBuildTree(
preLeft + 1 + inorderLeftLen,
preLeft + inorderLeftLen + inorderRightLen,
inorderMid + 1,
inorderRight
);
return root;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
中等 二分查找 原题链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
该改造版本应当是优于官方版本的：
class Solution {
public int[] searchRange(int[] nums, int target) {
/**
index 0 1 2 3 4 5
|
5,7,7,8,8,9
m !
|
*/
int n = nums.length;
int leftIndex = binarySearch(nums, 0, n - 1, target, true);
if (leftIndex != -1) {
int rightIndex = binarySearch(nums, leftIndex, n - 1, target, false);
return new int[]{leftIndex, rightIndex};
} else {
return new int[]{-1, -1};
}
}
// 改造版本, lower 为 true 代表寻找最左符合要求的值，反之亦然。
public int binarySearch(int[] nums, int i, int j, int target, boolean lower) {
int retPos = -1;
while(i <= j) {
int mid = (i + j) / 2;
if (nums[mid] == target) {
retPos = mid;
if (lower) {
j = mid - 1;
} else {
i = mid + 1;
}
continue;
}
if (nums[mid] > target) {
j = mid - 1;
} else {
i = mid + 1;
}
}
return retPos;
}
}
BD: 寻找数组中和为 K 的 N 倍的最短连续子序列
字节真实面试经历 建议大家在面试中做算法题的时候，不要一下子就想着最优解，可以先写出普通解，再一步步优化，这样和面试官也会有一个良性的互动，不至于人家干等着你干想
有时候，实在没思路了，可以让面试官给几个测试用例，这里往往暗藏玄机。
public class Solution {
/**
* S=[1,5,4,2,3] 正整数数组，无序，可能有重复元素,
* K=9 在数组S中找到长度大于等于 1 的连续子数组，使得子数组的和为给定数字K的整数倍，找出长度最短的解
*/
public int[] resolve(int[] s, int K) {
// 典型测试用例
// [1, 5, 4, 2, 3] 9 => {1, 2}
// [1, 2, 4, 2, 3] 3 => {4, 4}
// [1, 5, 8, 6, 2] 3 => {3, 3}
/**
* 题眼是正整数
* K * 1
* i
* 1,5,4,2,3 正整数 所以可以使用双指针，因为累加和是单调递增的
* j
* K * x ? x <= sum(s) / K
* 时间复杂度为：O(sum(s) * n / K)
* 空间复杂度：O(1)
*/
// 求和
int n = s.length;
int sum = 0;
for(int i = 0; i < n; i++) {
sum += s[i];
}
int minI = -1, minJ = -1, minGap = Integer.MAX_VALUE;
int xMax = sum / K;
for(int x = 1; x <= xMax; x++) {
int target = K * x;
int i = 0, j = 0, ans = 0;
while (j < n ) {
ans += s[j];
if (ans == target) {
if (j - i < minGap) {
minGap = j - i;
minI = i;
minJ = j;
}
}
while (ans > target) {
ans -= s[i++];
if (ans == target) {
if (j - i < minGap) {
minGap = j - i;
minI = i;
minJ = j;
}
}
}
j++;
}
if (minGap == 0) {
break;
}
}
return new int[]{minI, minJ};
}
}
若有收获，就点个赞吧
0 人点赞
