❓ -> 虽然做出了但有更妙的解法
Array
57. 插入区间 [❌]
这道题主要是两个考点
分类讨论：
设newInterval 为 [L,R]
Intervals[i] 为 [cL, cR]
完全不重叠的情况：
cR < L 即 intervals[i] 在 [L,R]左方
R < cL 即 intervals[i] 在 [L,R]右方
那么其他的情况即为可能出现重叠的情况
什么时候加入答案
如果每次更新都加入答案就会重复加入，因此我们只需要在碰到不重叠的时候加入一次即可。
由于按照左端点排序，因此第一个不重叠的位置就是R < cL
最后对于空数组的处理我们可以用一个flag，如果更新过的答案之前加入过，那么就可以跳过。如果没有加入过说明是第一次加入，那么就加入答案数组，避免数组为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int cur = 0;
int length = intervals.length;
List<int[]> res = new ArrayList<>();
int newLeft = newInterval[0], newRight = newInterval[1];
boolean insearted = false;
for (; cur < length; cur++) {
int curLeft = intervals[cur][0], curRight = intervals[cur][1];
if (curLeft > newRight) {
if (!insearted) {
res.add(new int[] {newLeft, newRight});
insearted = true;
}
res.add(new int[]{curLeft, curRight});
} else if (curRight < newLeft) {
res.add(new int[]{curLeft, curRight});
} else {
newLeft = Math.min(curLeft, newLeft);
newRight = Math.max(curRight, newRight);
}
}
if (!insearted) {
res.add(new int[] {newLeft, newRight});
}
int[][] ret = new int[res.size()][2];
for (int i = 0; i < res.size(); i++) {
ret[i] = res.get(i);
}
return ret;
}
}
|
15. 三数之和 [✅]
相向双指针应用题
本题主要考察两个：
- 循环不变量
- 两数之和的相向双指针
（其实挺简单的就是不要迷）
固定左边，那么中间的和右边的指针就是两数之和问题，然后为了解决重复的数组问题，那么需要在检查到和之前数相同时直接跳过就好了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int i = 0;
List<List<Integer>> ret = new ArrayList<>();
for (;i < n - 2; ) {
if (i != 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
int j = i + 1;
int k = n - 1;
while (j < k) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
j++;
continue;
}
if (nums[i] + nums[j] + nums[k] < 0) {
j++;
} else {
if (k != n - 1 && nums[k] == nums[k + 1]) {
k--;
continue;
}
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ret.add(list);
}
k--;
}
}
i++;
}
return ret;
}
}
|
238. 除自身以外数组的乘积 [✅]
前缀和思想： 额外空间 O(N) 做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] prefixMulti = new int[n];
int[] suffixMulti = new int[n];
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
prefixMulti[i] = 1;
suffixMulti[n - i - 1] = 1;
continue;
}
prefixMulti[i] = nums[i - 1] * prefixMulti[i - 1];
suffixMulti[n - i - 1] = nums[n - i] * suffixMulti[n - i];
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = prefixMulti[i] * suffixMulti[i];
}
return res;
}
}
|
为了省去额外的空间，我们可以采取使用res数组作为中间的用于计算前缀积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int suffixCur = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= suffixCur;
suffixCur *= nums[i];
}
return res;
}
}
|
39. 组合总和 [✅]
回溯题，这是一个选或不选的问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> selected = new LinkedList<>();
int[] candidates;
int n;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
n = candidates.length;
dfs(0, target);
return res;
}
private void dfs(int curIdx, int target) {
if (curIdx == n || target < 0) return;
if (target == 0) {
res.add(new ArrayList<>(selected));
return;
}
for (int i = curIdx; i < n; i++) {
selected.addLast(candidates[i]);
dfs(i, target - candidates[i]);
selected.removeLast();
}
}
}
|
56. 合并区间 [✅]
和插入区间异曲同工，需要注意边界的处理
自己的方法：
对左端点排序，「延迟」（即到下一个不可以合并的区间时候）加入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new Comparator<>(){
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
List<int[]> ls = new ArrayList<>();
int n = intervals.length;
int pStart = intervals[0][0], pEnd = intervals[0][1];
if (n == 1) {
return new int[][]{{pStart, pEnd}};
}
for (int i = 1; i < n; i++) {
int[] interval = intervals[i];
int start = interval[0], end = interval[1];
if (pEnd >= start) {
pStart = Math.min(pStart, start);
pEnd = Math.max(pEnd, end);
} else {
ls.add(new int[]{pStart, pEnd});
pStart = start;
pEnd = end;
}
}
ls.add(new int[]{pStart, pEnd});
int[][] ret = new int[ls.size()][2];
for (int i = 0; i < ls.size(); i++) {
ret[i] = ls.get(i);
}
return ret;
}
}
|
方法2:
用一个list merged 来表示已经处理好的部分，如果碰到不重叠的区间或者merged为空时，直接加入merged即可，其他时候可以查看merged的右端点并且不断更新其右端点
这个方法更好地利用了排序的性质
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new Comparator<>(){
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
List<int[]> merged = new ArrayList<>();
int n = intervals.length;
for (int i = 0; i < n; i++) {
int size = merged.size();
if (size == 0 || merged.get(size - 1)[1] < intervals[i][0]) {
merged.add(new int[]{intervals[i][0], intervals[i][1]});
} else {
merged.get(size - 1)[1] = Math.max(merged.get(size - 1)[1], intervals[i][1]);
}
}
int[][] ret = new int[merged.size()][2];
for (int i = 0; i < merged.size(); i++) {
ret[i] = merged.get(i);
}
return ret;
}
}
|
75. 颜色分类[❓]
这是一个考察循环不变量以及荷兰国旗的经典问题
- 循环不变：
Bilibili - 循环不变量
- 荷兰国旗
荷兰国旗的本质是要我们将数分成三段。
因此除了使用一个变量 cur 代指处理到哪一个 nums[cur] 以外，至少还需要两个变量来代指三段的边界：
- 变量
l 为下一个填入 0 的位置（因此范围 [0,l−1] 均为 0，初始化 l=0，代表空集）
- 变量
r 为下一个填入 2 的位置（因此范围 [r+1,n−1] 均为 2，初始化 r=n−1，代表空集)
- 由于 [0,cur−1] 均为处理过的数值（即 0 和 2 必然都被分到了两端），同时 l−1 又是 0 的右边界，因此 [l,cur−1] 为 1 的区间，而 [cur,r] 为未处理的数值。
分情况讨论：
- nums[cur]=0：此时将其与位置 l 进行互换（ l 为下一个待填入 0 的位置，同时 [l,cur−1] 为 1 的区间），本质是将nums[cur] 的 0 和 nums[l] 的 1 进行互换，因此互换后将 l 和 cur 进行右移；
- nums[cur]=1：由于[l,cur−1] 本身就是 1 的区间，直接将 cur 进行右移即可；
- nums[cur]=2：此时将其与位置 r 进行互换（r 为下一个待填入 2 的位置，但 [cur,r] 为未处理区间），也就是我们互换后，只能明确换到位置 nums[r] 的位置为 2，可以对 r 进行左移，但不确定新 nums[cur] 为何值，因此保持 cur 不变再入循环判断。
- 最后当 cur>r（含义为未处理区间为空集），整个分三段过程结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
for (int cur = 0; cur <= r;) {
System.out.println(l + " " + cur + " " + r);
if (nums[cur] == 0) {
swap(nums, l, cur);
l++;
cur++;
} else if (nums[cur] == 1) {
cur++;
} else {
swap(nums, cur, r);
r--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
|
11. 盛最多水的容器
双指针应用题：
- 主要证明一点，我们应该固定长板，每一次都移动短板，因为只有移动短板才有可能会有更大的面积，而这是因为每一次收紧左右端点时候其都会变小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxArea(int[] height) {
int n = height.length;
int l = 0, r = n - 1;
int result = Integer.MIN_VALUE;
while (l < r) {
int curArea = calculateArea(l, r, height[l], height[r]);
result = Math.max(curArea, result);
if (height[l] < height[r]) l++;
else r--;
}
return result;
}
private int calculateArea(int i, int j, int hi, int hj) {
return Math.min(hi, hj) * (j - i);
}
}
|
Stack
20. 有效的括号[✅]
栈就是括号问题的代名词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public boolean isValid(String s) {
Deque<Character> dq = new ArrayDeque<>();
char[] sChar = s.toCharArray();
int n = s.length();
for (int i = 0; i < n; i++) {
if (sChar[i] == '(' || sChar[i] == '{' || sChar[i] == '[') {
dq.addLast(sChar[i]);
} else {
if (dq.isEmpty()) return false;
char curLast = dq.peekLast();
if (sChar[i] == ')') {
if (curLast != '(') return false;
else dq.pollLast();
} else if (sChar[i] == ']') {
if (curLast != '[') return false;
else dq.pollLast();
} else if (sChar[i] == '}') {
if (curLast != '{') return false;
else dq.pollLast();
}
}
}
return dq.isEmpty();
}
}
|
42. 接雨水
三种解法：
第一类：纵向和
这种方法是在 i 上进行计算，即算当前的高，一列一列的加
前后缀分解 ：
前后缀分解比较好理解，有两个备忘录一个记录
height[0, i] 的最大值 lMax
height[i, n - 1] 的最大值 rMax
那么当前 i 的雨水就是 min(lMax, rMax) - height[i]
优化后的相向双指针：
但是可以省略这两个备忘录即使用相向双指针
但是这里不同的是
height[0, left] 的最大值 lMax
height[right, n - 1] 的最大值 rMax
不再是当前i而是left 和 right， 那么为什么可以保证这样是对的呢，这是因为当前i能接的雨水只看两遍的短的一边然后减去高度，也就是说重要的是 height[i] 能够装的水只和**Math.min(lMax, rMax)**相关（差）
第二类：横向和
这种方法类似于横向填充水泥。一行一行的加
单调栈
单调栈已经尝试多次
总结一下：
在需要更新栈中内容时，我们pop掉所有不符合要求的直至新加入的元素符合要求从而满足栈内元素单调。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| class Solution {
int[] height;
public int trap(int[] height) {
this.height = height;
return twoPointers();
}
private int twoPointers() {
int n = height.length;
int left = 0, right = n - 1;
int lMax = 0, rMax = 0;
int tot = 0;
while (left < right) {
lMax = Math.max(lMax, height[left]);
rMax = Math.max(rMax, height[right]);
if (lMax < rMax) {
tot += lMax - height[left];
left++;
} else {
tot += rMax - height[right];
right--;
}
}
return tot;
}
private int monoStack() {
Deque<Integer> stk = new ArrayDeque<>();
int n = height.length;
int tot = 0;
for (int i = 0; i < n; i++) {
while (!stk.isEmpty() && height[stk.peek()] <= height[i]) {
int bottomColIdx = stk.pop();
if (stk.isEmpty()) break;
int left = stk.peek();
int width = i - left - 1;
int minHeight = Math.min(height[left], height[i]) - height[bottomColIdx];
tot += width * minHeight;
}
stk.push(i);
}
return tot;
}
private int detachPrefixSuffix() {
int n = height.length;
int[] prefix = new int[n];
prefix[0] = height[0];
for (int i = 1; i < n; i++) {
prefix[i] = Math.max(prefix[i - 1], height[i]);
}
int[] suffix = new int[n];
suffix[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix[i] = Math.max(suffix[i + 1], height[i]);
}
int tot = 0;
for (int i = 0; i < n; i++) {
tot += calculateTrappedWater(prefix, suffix, i);
}
return tot;
}
private int calculateTrappedWater(int[] prefix, int[] suffix, int i) {
return Math.min(prefix[i], suffix[i]) - this.height[i];
}
}
|
Binary Tree
236. 二叉树的最近公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root, p, q);
}
private TreeNode dfs(TreeNode cur, TreeNode p, TreeNode q) {
if (cur == null) return null;
if (cur == p || cur == q) return cur;
TreeNode left = dfs(cur.left, p, q);
TreeNode right = dfs(cur.right, p, q);
if (left == null && right == null) {
return null;
}
if (left != null && right != null) return cur;
if (left == null) return right;
else return left;
}
}
|
102. 二叉树的层序遍历
简单的BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
Deque<TreeNode> dq = new LinkedList<>();
dq.addLast(root);
List<List<Integer>> res = new ArrayList<>();
while (!dq.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = dq.size();
while (size > 0) {
TreeNode cur = dq.pollFirst();
level.add(cur.val);
if (cur.left != null) {
dq.addLast(cur.left);
}
if (cur.right != null) {
dq.addLast(cur.right);
}
size--;
}
res.add(level);
}
return res;
}
}
|
199. 二叉树的右视图
BFS很简单每一层最右边的加入
DFS就是先右子树，后左子树。然后有一个track来看这一层最右边的被加进来过没有。如果有之后就都不加了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
LinkedList<Integer> res = new LinkedList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode root, int depthTrack) {
if (root == null) return;
if (depthTrack == res.size()) {
res.add(root.val);
}
dfs(root.right, depthTrack + 1);
dfs(root.left, depthTrack + 1);
}
}
|
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
这两题均属于构造类题目，具体可以看：
二叉树之构造类问题 中包含构造类问题的习题以及思路
核心思想都是通过构造左子树 + 右子树 连接根节点，只不过「细节和边界」略有不同，在尝试过后，使用左闭右开区间会稍微好处理一些
其实核心就是 子树 也是 树，所以递归的处理问题只要把大问题处理好小问题就可以很简单的处理了
105: 前序按照 中左右的顺序，所以可以先碰到的作为root节点然后递归的构造左右子树：
灵神 - 105
106: 后序按照 左右中的顺序，所以可以从右开始碰到的作为root节点然后递归的构造左右子树：
但是注意这里的区间略有不同
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
class Solution {
int[] preorder;
int[] inorder;
Map<Integer, Integer> num2Idx = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
for (int i = 0; i < inorder.length; i++) {
num2Idx.put(inorder[i], i);
}
TreeNode root = building(0, preorder.length - 1, 0, inorder.length - 1);
return root;
}
private TreeNode building(int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) return null;
if (inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int idxInorder = findNodeThruInorder(preorder[preStart]);
int leftSize = idxInorder - inStart;
root.left = building(preStart + 1, preStart + leftSize, inStart, idxInorder);
root.right = building(preStart + leftSize + 1, preEnd, idxInorder + 1, inEnd);
return root;
}
private int findNodeThruInorder(int val) {
return num2Idx.get(val);
}
}
class Solution {
int[] inorder, postorder;
Map<Integer, Integer> num2Idx = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
for (int i = 0; i < inorder.length; i++) {
num2Idx.put(inorder[i], i);
}
TreeNode root = building(0, inorder.length, 0, postorder.length);
return root;
}
private TreeNode building(int postStart, int postEnd, int inStart, int inEnd) {
if (postStart >= postEnd || inStart >= inEnd) return null;
int val = postorder[postEnd - 1];
TreeNode root = new TreeNode(val);
int idx = num2Idx.get(val);
int leftSize = idx - inStart;
root.left = building(postStart, postStart + leftSize, inStart, idx);
root.right = building(postStart + leftSize, postEnd - 1, idx + 1, inEnd);
return root;
}
}
|
