Skip to content

Commit 1ccebf6

Browse files
bigablecatbigablecat
authored
Merge pull request hollischuang#40 from bigablecat/master
update 689, 847
2 parents 92a311e + 29cb2bb commit 1ccebf6

3 files changed

Lines changed: 219 additions & 2 deletions

File tree

‎leetcode/689-MaximumSumOf3Non-OverlappingSubarrays/bigablecat.md‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
**689. 三个无重叠子数组的最大和**
2+
---
3+
[https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/](https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/)
4+
5+
```java
6+
7+
public int[] maxSumOfThreeSubarrays(int[] nums, int K) {
8+
// W是由数组nums中每K个元素的和组成的整数数组
9+
// 把间隔K看成滑动窗口的长度
10+
// 窗口在nums数组上从第1个元素开始滑动
11+
// 窗口每滑动一次，就计算一次窗口内所有元素的和，放入数组W
12+
// 滑动窗口到nums的第nums.length - K个元素时，共计算了nums.length - K次
13+
// 此时nums数组中还剩K个元素，可以计算最后一次
14+
// 所以W的长度是nums.length - K + 1
15+
int[] W = new int[nums.length - K + 1];
16+
//定义一个整数sum用于存储每K个元素的和
17+
int sum = 0;
18+
//遍历数组nums并求得W数组的所有值
19+
for (int i = 0; i < nums.length; i++) {
20+
//用+=对nums中连续的元素累加求和
21+
sum += nums[i];
22+
// 如果i>=K，说明前K个元素的值已经累加完毕，窗口开始向右滑动
23+
// 从K个元素之后，每次滑动1个元素
24+
// 需要从sum里减去上一次滑动窗口的首个元素nums[i - K]
25+
// sum -= nums[i - K]得到从第[i-K+1]个元素起到第i个元素为止的K个元素之和
26+
if (i >= K) sum -= nums[i - K];
27+
// 第一组K个元素在nums中的下标从0到K-1
28+
// 所以W的第一个元素是 W[i-K+1] = W[(K-1)-K+1] = W[0]
29+
if (i >= K - 1) W[i - K + 1] = sum;
30+
}
31+
32+
// 首先需要明白本解法中nums、W和left(或right)这三个数组索引的对应关系
33+
//
34+
// 先看W[i]和nums[i]的关系：
35+
// 在前一个给W赋值的for循环代码中可以看出，W[i]对应着nums中从nums[i]算起，到nums[i+K-1]，共K个元素的和
36+
// 如题目示例，nums=[1,2,1,2,6,7,5,1]，K=2，W=[3,3,3,8,13,12,6]
37+
// W[0]=nums[0]+nums[1]=1+2=3，即W[0]等于nums[0]到nums[0+2-1]=nums[1]，共2个元素的和
38+
//
39+
// 再看left[i]和W[i]的关系：
40+
// 给left[i](或right[i])赋值时，需要找到从W[0]到W[i]为止，元素值且索引最小那个元素
41+
// 然后将W中这个元素的索引赋给left[i]
42+
// 即给left[0]赋值时，比较W[0]到W[0]共1个元素，
43+
// 给left[1]赋值时，比较W[0]到W[1]共2个元素，
44+
// 给left[2]赋值时，比较W[0]到W[2]共3个元素...以此类推
45+
// 因为W[0]=w[1]=W[2]=3，而W[0]、W[1]、W[2]三个元素中W[0]的索引最小
46+
// 所以left[0]=left[1]=left[2]=0，都取最小的那个索引0
47+
//
48+
// 同时，由于到nums[nums.length - K + 1]为止，W和nums中的索引是一一对应的
49+
// 而left[i]记录的又是W中的索引，所以left[i]与nums中的元素索引一一对应
50+
// 索引的对应关系清楚了，下面关于left和right的代码就容易理解了
51+
52+
//题目要求返回nums中和最大的3个子序列的起始索引
53+
//我们将这3个子序列中的第1个子序列的可能索引都存入一个整数数组left
54+
int[] left = new int[W.length];
55+
//定义一个整数best，记录每次迭代时，从数组W中获取到的相对最大值在W中的索引
56+
//best默认值为0
57+
int best = 0;
58+
//按索引从小到大遍历数组W
59+
for (int i = 0; i < W.length; i++) {
60+
//W[i] > W[best]表示当前第i个元素W[i]，大于W中已知的最大元素W[best]
61+
//将索引i赋值给best
62+
if (W[i] > W[best]) best = i;
63+
//将当前为止W中最大值的索引best赋给left[i]
64+
left[i] = best;
65+
}
66+
67+
//题目要求返回nums中和最大的3个子序列的起始索引
68+
//我们将这3个子序列中的第3个子序列的可能索引都存入一个整数数组right
69+
int[] right = new int[W.length];
70+
//best默认值为W数组的末尾索引
71+
best = W.length - 1;
72+
//按索引从大到小遍历数组W
73+
for (int i = W.length - 1; i >= 0; i--) {
74+
//W[i] > W[best]表示当前第i个元素W[i]，大于等于W中已知的最大元素W[best]
75+
//将索引i赋值给best
76+
if (W[i] >= W[best]) best = i;
77+
//将当前为止W中最大值的索引best赋给right[i]
78+
right[i] = best;
79+
}
80+
81+
// 定义一个整数数组ans用于返回最终结果，即3个子序列的初始索引
82+
int[] ans = new int[]{-1, -1, -1};
83+
// for循环的控制变量j在循环体中要进行j-K和j + K的操作
84+
// j-K要大于等于0，j+K要小于W.length
85+
// 所以j的初始值为K，j的上限值W.length - K
86+
for (int j = K; j < W.length - K; j++) {
87+
// 定义3个子序列的中间序列的索引为j
88+
// 那么W[j]等于nums[j]到nums[j+K-1]共K个元素的和
89+
// 因为3个子序列不重叠，所以：
90+
// 第1个序列的索引应该小于或等于j-K
91+
// 第3个序列的索引应该大于或等于j+K
92+
// left[j - K]记录了到从nums[0]到nums[j-K]为止，子序列和最大初始索引最小的那个索引
93+
// right[j - K]记录了到nums[nums.length]到nums[j+K]为止，子序列和最大初始索引最小的那个索引
94+
int i = left[j - K], k = right[j + K];
95+
//当ans[0] == -1时，ans还没有赋值
96+
//当W[i] + W[j] + W[k] > W[ans[0]] + W[ans[1]] + W[ans[2]]时
97+
//说明找到了更大的3个子序列之和
98+
//满足上述两个条件之一，即对ans[0]、ans[1]、ans[2]重新赋值
99+
if (ans[0] == -1 || W[i] + W[j] + W[k] >
100+
W[ans[0]] + W[ans[1]] + W[ans[2]]) {
101+
//分别将初始索引i、j、k赋值给ans[0]、ans[1]、ans[2]
102+
ans[0] = i;
103+
ans[1] = j;
104+
ans[2] = k;
105+
}
106+
}
107+
//返回最终结果
108+
return ans;
109+
}
110+
111+
```
112+
113+
**复杂度分析**
114+
115+
时间复杂度：O(N)，
116+
方法中使用了4个for循环，迭代次数都在nums的长度范围内，
117+
所以时间复杂度为4N，消去常数项，时间复杂度为O(N)
118+
119+
空间复杂度：O(N)，
120+
定义了3个整数数组W、left、right，
121+
占用空间都在nums数组的长度范围内，
122+
还定义了一个数组ans，长度为常数3，
123+
所以空间复杂度是3N+3，消去常数项最终空间复杂度为O(N)
124+
125+
---
126+
127+
**参考资料**
128+
129+
* 本题leetCode英文官方题解：
130+
[https://leetcode.com/articles/maximum-sum-of-3-non-overlapping-intervals/](https://leetcode.com/articles/maximum-sum-of-3-non-overlapping-intervals/)

‎leetcode/692-TopKFrequentWords/bigablecat.md‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -60,8 +60,7 @@ O(N), 使用了List存储n个单词
6060
**参考资料**
6161

6262
* 本题leetCode英文官方题解：
63-
[https://leetcode.com/articles/linked-list-cycle/](https://leetcode.com/articles/linked-list-cycle/)
64-
63+
[https://leetcode.com/articles/top-k-frequent-words/](https://leetcode.com/articles/top-k-frequent-words/)
6564

6665
* Collections.sort()的用法和要点：
6766
[https://blog.csdn.net/wsll581/article/details/79953589](https://blog.csdn.net/wsll581/article/details/79953589)

‎leetcode/847-ShortestPathVisitingAllNodes/bigablecat.md‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
**847. 访问所有节点的最短路径**
2+
---
3+
[https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/](https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/)
4+
5+
6+
```java
7+
8+
public int shortestPathLength2(int[][] graph) {
9+
//定义一个整数N，N是图graph节点的数目
10+
int N = graph.length;
11+
// 1<<N是位运算操作，即将1带符号向左位移N位
12+
// 1的二进制数最后8位是0000 0001
13+
// 如1<<2表示将0000 0001右移2位，得到0000 0100，位移后的二进制数用十进制表示等于4=2^2
14+
// 如1<<3表示将0000 0001右移3位，得到0000 1000，位移后的二进制数用十进制表示等于8=2^3
15+
// 可以看出将1右移N位等价于1*2^N
16+
// 定义一个二维数组dist用于记录所有可能的最短路径
17+
// [1 << N][N]表示二维数组的行数是1 << N = 2^N，列数是N
18+
int dist[][] = new int[1 << N][N];
19+
//遍历二维数组dist的每一行
20+
for (int[] row : dist) {
21+
//为整数数组row填充初始值N*N
22+
Arrays.fill(row, N * N);
23+
}
24+
//迭代N次
25+
for (int x = 0; x < N; ++x) {
26+
//将第2^x行的x列赋值为0
27+
dist[1 << x][x] = 0;
28+
}
29+
30+
//for循环迭代(1 << N)次，即2^N次，遍历graph的所有行
31+
//控制变量cover用于获取二维数组的每一行
32+
//使用dist[cover]得到一个整数数组，该数组存放了当前路线经过的所有节点
33+
for (int cover = 0; cover < 1 << N; ++cover) {
34+
//定义boolean值repeat用于判断是否为重复访问
35+
boolean repeat = true;
36+
//当重复访问时进入while循环
37+
while (repeat) {
38+
//将重复访问标识repeat定义为false
39+
repeat = false;
40+
//设graph的每个节点的编号为head，迭代N次，遍历所有节点
41+
for (int head = 0; head < N; ++head) {
42+
//dist[cover]得到当前路径经过的所有节点
43+
//dist[cover][head]存放当前路径到节点head的最短路径
44+
//定义一个整数d作为dist[cover][head]的临时变量
45+
int d = dist[cover][head];
46+
//graph[head]获得当前节点head连通的所有其他节点
47+
for (int next : graph[head]) {
48+
//对当前与head连通的节点next进行位运算操作
49+
//首先将1向右位移next个单位，即求2^next
50+
//再将cover与(1 << next)的结果进行按位或运算
51+
//cover2就是当前路径到节点head经过的最短路径
52+
int cover2 = cover | (1 << next);
53+
if (d + 1 < dist[cover2][next]) {
54+
dist[cover2][next] = d + 1;
55+
//如果cover == cover2，表示两个节点编号相等，即进行了重复访问
56+
if (cover == cover2) {
57+
repeat = true;
58+
}
59+
}
60+
}
61+
}
62+
}
63+
}
64+
65+
//定义一个初始值为N*N的整数ans作为最终返回结果
66+
int ans = N * N;
67+
//遍历二维数组dist的最后一行
68+
for (int cand : dist[(1 << N) - 1]) {
69+
//对比当前列的数值cand与ans，将较小值赋给ans
70+
ans = Math.min(cand, ans);
71+
}
72+
//返回最终结果ans即是最短路线
73+
return ans;
74+
}
75+
76+
```
77+
78+
**复杂度分析**
79+
80+
空间复杂度：O(2^N*N)，
81+
本方法定义了二维数组dist[][]空间复杂度为2^N*N，
82+
83+
---
84+
85+
**参考资料**
86+
87+
* 本题leetCode英文官方题解：
88+
[https://leetcode.com/articles/shortest-path-visiting-all-nodes/](https://leetcode.com/articles/shortest-path-visiting-all-nodes/)

0 commit comments

Comments
 (0)