Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit845a0df

Browse files
committed
add 0209
1 parentdbe51e8 commit845a0df

File tree

5 files changed

+172
-75
lines changed

5 files changed

+172
-75
lines changed

‎README.md

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -85,7 +85,8 @@
8585
| 49|[Group Anagrams][0049]| Hash Table, String|
8686
| 50|[Pow(x, n)][0050]| Math, Binary Search|
8787
| 56|[Merge Intervals][0056]| Array, Sort|
88-
| 209|[长度最小的子数组(Minimum Size Subarray Sum)][0209]| Array, Sort|
88+
| 209|[长度最小的子数组(Minimum Size Subarray Sum)][0209]| 数组、双指针、二分查找|
89+
| 215|[数组中的第K个最大元素(Kth Largest Element in an Array)][0215]| 堆、分治算法|
8990
| 554|[Brick Wall][0554]| Hash Table|
9091
| 1014|[最佳观光组合(Best Sightseeing Pair)][1014]| 数组|
9192

@@ -168,11 +169,13 @@
168169
[0049]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0049/README.md
169170
[0050]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0050/README.md
170171
[0056]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0056/README.md
172+
[0209]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0209/README.md
173+
[0215]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0215/README.md
171174
[0554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0554/README.md
172175
[1014]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/1014/README.md
176+
173177
[0004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0004/README.md
174178
[0010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0010/README.md
175-
176179
[0023]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0023/README.md
177180
[0025]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0025/README.md
178181
[0030]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0030/README.md

‎note/0209/README.md

Lines changed: 71 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -2,80 +2,106 @@
22

33
##题目描述
44

5-
我们从二叉树的根节点`root` 开始进行深度优先搜索。
5+
给定一个含有 **n** 个正整数的数组和一个正整数 **s** ，找出该数组中满足其和**≥ s** 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
66

7-
在遍历中的每个节点处，我们输出 `D` 条短划线（其中 `D` 是该节点的深度），然后输出该节点的值。（_如果节点的深度为`D`，则其直接子节点的深度为`D + 1`。根节点的深度为`0`）。_
8-
9-
如果节点只有一个子节点，那么保证该子节点为左子节点。
10-
11-
给出遍历输出 `S`，还原树并返回其根节点 `root`。
12-
13-
**示例 1：**
14-
15-
**![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/recover-a-tree-from-preorder-traversal.png)**
7+
**示例：**
168

179
```
18-
输入："1-2--3--4-5--6--7"
19-
输出：[1,2,5,3,4,6,7]
10+
输入：s = 7, nums = [2,3,1,2,4,3]
11+
输出：2
12+
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。
2013
```
2114

22-
**示例 2：**
15+
**进阶：**
2316

24-
**![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114101-pm.png)**
17+
* 如果你已经完成了_O_(_n_) 时间复杂度的解法, 请尝试_O_(_n_ log_n_) 时间复杂度的解法。
2518

26-
```
27-
输入："1-2--3---4-5--6---7"
28-
输出：[1,2,5,3,null,6,null,4,null,7]
29-
```
19+
**标签：** 数组、双指针、二分查找
3020

31-
**示例 3：**
3221

33-
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114955-pm.png)
22+
##思路 0
3423

35-
```
36-
输入："1-401--349---90--88"
37-
输出：[1,401,null,349,88,90]
24+
直接暴力法，两重 for 循环，记录最小长度即可，代码很简单，如下所示：
25+
26+
27+
```java
28+
classSolution {
29+
publicintminSubArrayLen(ints,int[]nums) {
30+
int ans=Integer.MAX_VALUE;
31+
for (int i=0; i< nums.length; i++) {
32+
int sum= nums[i];
33+
if (sum>= s) {
34+
return1;
35+
}
36+
for (int j= i+1; j< nums.length; j++) {
37+
sum+= nums[j];
38+
if (sum>= s) {
39+
ans=Math.min(ans, j- i+1);
40+
break;
41+
}
42+
}
43+
}
44+
return ans==Integer.MAX_VALUE?0: ans;
45+
}
46+
}
3847
```
3948

40-
**提示：**
49+
##思路 1
4150

42-
* 原始树中的节点数介于`1` 和`1000` 之间。
43-
* 每个节点的值介于`1` 和`10 ^ 9` 之间。
51+
对上面进行优化，我们通过首位两个指针来模拟滑动窗口，如果加起来值小于 s，则向右扩大窗口直至不小于 s，然后固定窗口右侧来向左缩小窗口，同时更新符合条件的最小窗口长度即可，代码如下所示：
4452

45-
**标签：** 树、深度优先搜索
53+
```java
54+
classSolution {
55+
publicintminSubArrayLen(ints,int[]nums) {
56+
int left=0, right=0, sum=0, ans=Integer.MAX_VALUE;
57+
while (right< nums.length) {
58+
sum+= nums[right++];// 向右扩大窗口
59+
while (sum>= s) {// 如果不小于 s，则收缩窗口左边界
60+
ans=Math.min(ans, right- left);// 更新结果
61+
sum-= nums[left++];// 向左缩小窗口
62+
}
63+
}
64+
return ans==Integer.MAX_VALUE?0: ans;
65+
}
66+
}
67+
```
4668

69+
##思路 2
4770

48-
##思路
71+
进阶中说了，尝试使用 O(nlogn) 时间复杂度的解法，由于数组都是正整数构成，所以前缀和一定是递增的，想到的应该就是用二分查找了，可以用 sums 数组来存储 nums 数组的前缀和，sums[i] 代表 nums[0] 到 nums[i - 1] 总和，然后遍历 sums 数组，对 sums[i] + s 进行二分查找然后不断更新结果即可，具体代码如下所示：
4972

50-
直接暴力两层 for 循环肯定过不了关，我们把公式变化为`(A[i] + i) + (A[j] - j)`，看到此应该就可以想到在每次遍历`j` 时，只需要知道`max(A[i] + i)` 即可。
5173

5274
```java
5375
classSolution {
54-
55-
publicintmaxScoreSightseeingPair(int[]A) {
56-
int ans=0, cur=A[0]+0;
57-
for (int j=1; j<A.length; j++) {
58-
ans=Math.max(ans, cur+A[j]- j);// 计算当前最大得分
59-
cur=Math.max(cur,A[j]+ j);// 更新最大的 A[i] + i
76+
publicintminSubArrayLen(ints,int[]nums) {
77+
int ans=Integer.MAX_VALUE;
78+
int[] sums=newint[nums.length+1];
79+
for (int i=0; i< nums.length; i++) {
80+
sums[i+1]= sums[i]+ nums[i];
6081
}
61-
return ans;
62-
}
63-
64-
publicstaticvoidmain(String[]args) {
65-
Solution solution=newSolution();
66-
int[]A=newint[]{8,1,5,2,6};
67-
System.out.println(solution.maxScoreSightseeingPair(A));
82+
for (int i=0; i< nums.length; i++) {
83+
int target= s+ sums[i];// 确定要搜索的目标值
84+
// Java 二分查找 Arrays.binarySearch 如果找到就会返回该元素的索引；
85+
// 如果没找到就会返回一个负数，这个负数取反之后再减一就是查找的值应该在数组中的位置；
86+
// 例如 [-1, 0, 1, 5] 中二分查找 2，其返回值就是 -4，其 -(-4) - 1 = 3，所以 2 这个元素插入到数组的索引就是 3
87+
int bound=Arrays.binarySearch(sums, target);
88+
if (bound<0) {
89+
bound=-bound-1;
90+
}
91+
if (bound< sums.length) {// 当 bound 确定插入点不在 sums 数组的最后面时，说明不小于 target 的值了
92+
ans=Math.min(ans, bound- i);
93+
}
94+
}
95+
return ans==Integer.MAX_VALUE?0: ans;
6896
}
6997
}
70-
7198
```
7299

73-
74100
##结语
75101

76102
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
77103

78104

79105

80-
[title]:https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal
106+
[title]:https://leetcode-cn.com/problems/minimum-size-subarray-sum
81107
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎note/1014/README.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,6 @@ class Solution {
4646
System.out.println(solution.maxScoreSightseeingPair(A));
4747
}
4848
}
49-
5049
```
5150

5251

‎src/com/blankj/hard/_1028/Solution.java

Lines changed: 26 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,32 @@
1313
* </pre>
1414
*/
1515
publicclassSolution {
16+
// public TreeNode recoverFromPreorder(String S) {
17+
// char[] chars = S.toCharArray();
18+
// int len = chars.length;
19+
// List<TreeNode> levels = new LinkedList<>();
20+
// for (int i = 0; i < len; ) {
21+
// int level = 0, val = 0;
22+
// while (chars[i] == '-') { // 获取所在层级，Character.isDigit() 会比较慢
23+
// ++i;
24+
// ++level;
25+
// }
26+
// while (i < len && chars[i] != '-') { // 获取节点的值
27+
// val = val * 10 + chars[i++] - '0';
28+
// }
29+
// TreeNode curNode = new TreeNode(val);
30+
// if (level > 0) {
31+
// TreeNode parent = levels.get(level - 1);
32+
// if (parent.left == null) { // 如果节点只有一个子节点，那么保证该子节点为左子节点。
33+
// parent.left = curNode;
34+
// } else {
35+
// parent.right = curNode;
36+
// }
37+
// }
38+
// levels.add(level, curNode); // 因为是前序遍历（根-左-右），也就是右覆盖左时，此时左树已遍历完成，故无需考虑覆盖问题
39+
// }
40+
// return levels.get(0);
41+
// }
1642

1743
publicTreeNoderecoverFromPreorder(StringS) {
1844
char[]chars =S.toCharArray();
@@ -44,33 +70,6 @@ public TreeNode recoverFromPreorder(String S) {
4470
returnstack.get(0);
4571
}
4672

47-
// public TreeNode recoverFromPreorder(String S) {
48-
// char[] chars = S.toCharArray();
49-
// int len = chars.length;
50-
// List<TreeNode> levels = new LinkedList<>();
51-
// for (int i = 0; i < len; ) {
52-
// int level = 0, val = 0;
53-
// while (chars[i] == '-') { // 获取所在层级，Character.isDigit() 会比较慢
54-
// ++i;
55-
// ++level;
56-
// }
57-
// while (i < len && chars[i] != '-') { // 获取节点的值
58-
// val = val * 10 + chars[i++] - '0';
59-
// }
60-
// TreeNode curNode = new TreeNode(val);
61-
// if (level > 0) {
62-
// TreeNode parent = levels.get(level - 1);
63-
// if (parent.left == null) { // 如果节点只有一个子节点，那么保证该子节点为左子节点。
64-
// parent.left = curNode;
65-
// } else {
66-
// parent.right = curNode;
67-
// }
68-
// }
69-
// levels.add(level, curNode); // 因为是前序遍历（根-左-右），也就是右覆盖左时，此时左树已遍历完成，故无需考虑覆盖问题
70-
// }
71-
// return levels.get(0);
72-
// }
73-
7473
publicstaticvoidmain(String[]args) {
7574
Solutionsolution =newSolution();
7675
TreeNode.print(solution.recoverFromPreorder("1-2--3--4-5--6--7"));
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
packagecom.blankj.medium._0209;
2+
3+
importjava.util.Arrays;
4+
5+
/**
6+
* <pre>
7+
* author: Blankj
8+
* blog : http://blankj.com
9+
* time : 2020/06/30
10+
* desc :
11+
* </pre>
12+
*/
13+
publicclassSolution {
14+
// public int minSubArrayLen(int s, int[] nums) {
15+
// int ans = Integer.MAX_VALUE;
16+
// for (int i = 0; i < nums.length; i++) {
17+
// int sum = nums[i];
18+
// if (sum >= s) {
19+
// return 1;
20+
// }
21+
// for (int j = i + 1; j < nums.length; j++) {
22+
// sum += nums[j];
23+
// if (sum >= s) {
24+
// ans = Math.min(ans, j - i + 1);
25+
// break;
26+
// }
27+
// }
28+
// }
29+
// return ans == Integer.MAX_VALUE ? 0 : ans;
30+
// }
31+
32+
// public int minSubArrayLen(int s, int[] nums) {
33+
// int left = 0, right = 0, sum = 0, ans = Integer.MAX_VALUE;
34+
// while (right < nums.length) {
35+
// sum += nums[right++]; // 向右扩大窗口
36+
// while (sum >= s) { // 如果不小于 s，则收缩窗口左边界
37+
// ans = Math.min(ans, right - left);// 更新结果
38+
// sum -= nums[left++]; // 向左缩小窗口
39+
// }
40+
// }
41+
// return ans == Integer.MAX_VALUE ? 0 : ans;
42+
// }
43+
44+
publicintminSubArrayLen(ints,int[]nums) {
45+
intans =Integer.MAX_VALUE;
46+
int[]sums =newint[nums.length +1];
47+
for (inti =0;i <nums.length;i++) {
48+
sums[i +1] =sums[i] +nums[i];
49+
}
50+
for (inti =0;i <nums.length;i++) {
51+
inttarget =s +sums[i];// 确定要搜索的目标值
52+
// Java 二分查找 Arrays.binarySearch 如果找到就会返回该元素的索引；
53+
// 如果没找到就会返回一个负数，这个负数取反之后再减一就是查找的值应该在数组中的位置；
54+
// 例如 [-1, 0, 1, 5] 中二分查找 2，其返回值就是 -4，其 -(-4) - 1 = 3，所以 2 这个元素插入到数组的索引就是 3
55+
intbound =Arrays.binarySearch(sums,target);
56+
if (bound <0) {
57+
bound = -bound -1;
58+
}
59+
if (bound <sums.length) {// 当 bound 确定插入点不在 sums 数组的最后面时，说明不小于 target 的值了
60+
ans =Math.min(ans,bound -i);
61+
}
62+
}
63+
returnans ==Integer.MAX_VALUE ?0 :ans;
64+
}
65+
66+
publicstaticvoidmain(String[]args) {
67+
Solutionsolution =newSolution();
68+
System.out.println(solution.minSubArrayLen(7,newint[]{2,3,1,2,4,3}));
69+
}
70+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp