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

Commitf53e2b2

Browse files
Update
1 parent80cb4d9 commitf53e2b2

10 files changed

+335
-61
lines changed

‎pics/39.组合总和.png

2.74 KB
Loading

‎pics/39.组合总和1.png

8.91 KB
Loading

‎problems/0039.组合总和.md

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -39,8 +39,7 @@ candidates 中的数字可以无限制重复被选取。
3939

4040
本题搜索的过程抽象成树形结构如下：
4141

42-
![39.组合总和](https://img-blog.csdnimg.cn/20201123202227835.png)
43-
42+
![39.组合总和](https://img-blog.csdnimg.cn/20201223170730367.png)
4443
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！
4544

4645
而在[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)和[回溯算法：求组合总和！](https://mp.weixin.qq.com/s/HX7WW6ixbFZJASkRnCTC3w) 中都可以知道要递归K层，因为要取k个元素的组合。
@@ -75,7 +74,7 @@ void backtracking(vector<int>& candidates, int target, int sum, int startIndex)
7574

7675
在如下树形结构中：
7776

78-
![39.组合总和](https://img-blog.csdnimg.cn/20201123202227835.png)
77+
![39.组合总和](https://img-blog.csdnimg.cn/20201223170730367.png)
7978

8079
从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。
8180

@@ -148,7 +147,7 @@ public:
148147

149148
在这个树形结构中：
150149

151-
![39.组合总和](https://img-blog.csdnimg.cn/20201123202227835.png)
150+
![39.组合总和](https://img-blog.csdnimg.cn/20201223170730367.png)
152151

153152
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。
154153

@@ -160,8 +159,8 @@ public:
160159

161160
如图：
162161

163-
![39.组合总和1](https://img-blog.csdnimg.cn/20201123202349897.png)
164162

163+
![39.组合总和1](https://img-blog.csdnimg.cn/20201223170809182.png)
165164

166165
for循环剪枝代码如下：
167166

‎problems/0056.合并区间.md

Lines changed: 93 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,61 @@
1-
##题目链接
2-
https://leetcode-cn.com/problems/merge-intervals/
1+
>「代码随想录」出品，毕竟精品！
32
4-
##思路
5-
这道题目看起来就是一道模拟类的题，但其实是一道贪心题目！
3+
#56. 合并区间
64

7-
按照左区间排序之后，每次合并都取最大的右区间，这样就可以合并更多的区间了。
5+
题目链接：https://leetcode-cn.com/problems/merge-intervals/
86

9-
那有同学问了，这不是废话么？ 当然要取最大的右区间啊。
7+
给出一个区间的集合，请合并所有重叠的区间。
108

11-
**是的，一想就是这么个道理，但它就是贪心的思想，局部最优推导出整体最优**。
9+
示例 1:
10+
输入: intervals =[[1,3],[2,6],[8,10],[15,18]]
11+
输出:[[1,6],[8,10],[15,18]]
12+
解释: 区间[1,3] 和[2,6] 重叠, 将它们合并为[1,6].
1213

13-
这也就是为什么很多同学刷题的时候都没有发现自己用了贪心。
14+
示例 2:
15+
输入: intervals =[[1,4],[4,5]]
16+
输出:[[1,5]]
17+
解释: 区间[1,4] 和[4,5] 可被视为重叠区间。
18+
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
1419

15-
合并思路：如果`intervals[i][0] < intervals[i - 1][1]` 即intervals[i]起始位置 < intervals[i - 1]终止位置，则一定有重复，需要合并。
20+
提示：
1621

17-
如图所示：
22+
* intervals[i][0] <= intervals[i][1]
1823

19-
<imgsrc='../pics/56.合并区间.png'width=600> </img></div>
24+
#思路
25+
26+
大家应该都感觉到了，此题一定要排序，那么按照左边界排序，还是右边界排序呢？
27+
28+
都可以！
29+
30+
那么我按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
31+
32+
局部最优可以推出全局最优，找不出反例，试试贪心。
33+
34+
那有同学问了，本来不就应该合并最大右边界么，这和贪心有啥关系？
35+
36+
有时候贪心就是常识！哈哈
37+
38+
按照左边界从小到大排序之后，如果`intervals[i][0] < intervals[i - 1][1]` 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
39+
40+
即：intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内，那么一定有重复！
41+
42+
这么说有点抽象，看图：（**注意图中区间都是按照左边界排序之后了**）
43+
44+
![56.合并区间](https://img-blog.csdnimg.cn/20201223200632791.png)
45+
46+
知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？
47+
48+
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
2049

2150
C++代码如下：
2251

23-
```
52+
```C++
2453
classSolution {
2554
public:
26-
//按照区间左边界排序
55+
//按照区间左边界从小到大排序
2756
static bool cmp (const vector<int>& a, const vector<int>& b) {
2857
return a[0] < b[0];
2958
}
30-
3159
vector<vector<int>> merge(vector<vector<int>>& intervals) {
3260
vector<vector<int>> result;
3361
if (intervals.size() == 0) return result;
@@ -36,14 +64,15 @@ public:
3664
int length = intervals.size();
3765

3866
for (int i = 1; i < length; i++) {
39-
int start = intervals[i - 1][0];
40-
int end = intervals[i - 1][1];
67+
int start = intervals[i - 1][0]; // 初始为i-1区间的左边界
68+
int end = intervals[i - 1][1]; // 初始i-1区间的右边界
4169
while (i < length && intervals[i][0] <= end) { // 合并区间
42-
end = max(end, intervals[i][1]);
43-
if (i == length - 1) flag = true; // 最后一个区间也合并了
44-
i++;
70+
end = max(end, intervals[i][1]); // 不断更新右区间
71+
if (i == length - 1) flag = true;// 最后一个区间也合并了
72+
i++; // 继续合并下一个区间
4573
}
46-
result.push_back({start, end});
74+
// start和end是表示intervals[i - 1]的左边界右边界，所以最优intervals[i]区间是否合并了要标记一下
75+
result.push_back({start, end});
4776
}
4877
// 如果最后一个区间没有合并，将其加入result
4978
if (flag == false) {
@@ -53,3 +82,47 @@ public:
5382
}
5483
};
5584
```
85+
86+
当然以上代码有冗余一些，可以优化一下，如下：（思路是一样的）
87+
88+
```C++
89+
classSolution {
90+
public:
91+
vector<vector<int>> merge(vector<vector<int>>& intervals) {
92+
vector<vector<int>> result;
93+
if (intervals.size() == 0) return result;
94+
// 排序的参数使用了lamda表达式
95+
sort(intervals.begin(), intervals.end(),[](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
96+
97+
result.push_back(intervals[0]);
98+
for (int i = 1; i < intervals.size(); i++) {
99+
if (result.back()[1] >= intervals[i][0]) { // 合并区间
100+
result.back()[1] = max(result.back()[1], intervals[i][1]);
101+
} else {
102+
result.push_back(intervals[i]);
103+
}
104+
}
105+
return result;
106+
}
107+
};
108+
```
109+
110+
* 时间复杂度：O(nlogn) ，有一个快排
111+
* 空间复杂度：O(1)，我没有算result数组（返回值所需容器占的空间）
112+
113+
114+
#总结
115+
116+
对于贪心算法，很多同学都是：**如果能凭常识直接做出来，就会感觉不到自己用了贪心, 一旦第一直觉想不出来, 可能就一直想不出来了**。
117+
118+
跟着「代码随想录」刷题的录友应该感受过，贪心难起来，真的难。
119+
120+
那应该怎么办呢？
121+
122+
正如我贪心系列开篇词[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)中讲解的一样，贪心本来就没有套路，也没有框架，所以各种常规解法需要多接触多练习，自然而然才会想到。
123+
124+
「代码随想录」会把贪心常见的经典题目覆盖到，大家只要认真学习打卡就可以了。
125+
126+
就酱，学算法，就在「代码随想录」，值得介绍给身边的朋友同学们！
127+
128+

‎problems/0070.爬楼梯.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,43 @@
11

2+
#思路
3+
4+
本题大家多举一个例子，就发现这其实就是斐波那契数列。
5+
6+
题目509. 斐波那契数中的代码初始化部分稍加改动，就可以过了本题。
7+
8+
C++代码如下：
9+
```
10+
class Solution {
11+
public:
12+
int climbStairs(int n) {
13+
if (n <= 1) return n;
14+
vector<int> dp(n + 1);
15+
dp[0] = 1;
16+
dp[1] = 1;
17+
for (int i = 2; i <= n; i++) {
18+
dp[i] = dp[i - 1] + dp[i - 2];
19+
}
20+
return dp[n];
21+
22+
}
23+
};
24+
```
25+
26+
既然这么简单为什么还要讲呢，其实本题稍加改动就是一道面试好题，如果每次可以爬 1 或 2或3或者m 个台阶呢，走到楼顶有几种方法？
27+
28+
29+
30+
* 确定dp数组以及下标的含义
31+
32+
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法
33+
34+
* 确定递推公式
35+
36+
dp[i]有几种来源，dp[i - 1]，dp[i - 2]
37+
38+
* dp数组如何初始化
39+
* 确定遍历顺序
40+
241
dp里求排列，1 2 步 和 2 1 步都是上三个台阶，但不一样！
342

443
这是求排列
@@ -17,3 +56,19 @@ public:
1756
}
1857
};
1958
```
59+
60+
#总结
61+
62+
如果我来面试的话，我就会想给候选人出一个 本题原题，看其表现，如果顺利写出来，进而在要求每次可以爬[1 - m]个台阶应该怎么写。
63+
64+
顺便再考察一下两个for循环的嵌套顺序，为什么target放外面，nums放里面。这就能反馈出对背包问题本质的掌握程度，是不是刷题背公式，一眼就看出来。
65+
66+
这么一连套下来，如果候选人都能答出来，相信任何一位面试官都是非常满意的。
67+
68+
**本题代码不长，题目也很普通，当稍稍一进阶就可以考察本质问题，而且题目进阶的内容在leetcode上并没有，一定程度上就可以排除掉刷题党了，简直是面试题目的绝佳选择！**
69+
70+
相信通过这道简单的斐波那契数列题目，大家能感受到大厂面试官最喜欢什么样的面试题目了，并不是手撕红黑树！
71+
72+
73+
所以本题是一道非常好的题目。
74+

0 commit comments

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