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

Commitf881e3e

Browse files
Update
1 parent1b906da commitf881e3e

9 files changed

+235
-46
lines changed

‎README.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -59,11 +59,11 @@
5959
* 求职
6060
*[程序员的简历应该这么写！！（附简历模板）](https://mp.weixin.qq.com/s/nCTUzuRTBo1_R_xagVszsA)
6161
*[BAT级别技术面试流程和注意事项都在这里了](https://mp.weixin.qq.com/s/815qCyFGVIxwut9I_7PNFw)
62-
*[深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/3VJHF2zNohBwDBxARFIn-Q)
63-
*[北京有这些互联网公司，你都知道么？]()
62+
*[北京有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/BKrjK4myNB-FYbMqW9f3yw)
6463
*[上海有这些互联网公司，你都知道么？]()
65-
*[成都有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Y9Qg22WEsBngs8B-K8acqQ)
64+
*[深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/3VJHF2zNohBwDBxARFIn-Q)
6665
*[广州有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Ir_hQP0clbnvHrWzDL-qXg)
66+
*[成都有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Y9Qg22WEsBngs8B-K8acqQ)
6767

6868

6969
* 算法性能分析
@@ -217,6 +217,7 @@
217217
*[贪心算法：根据身高重建队列](https://mp.weixin.qq.com/s/-2TgZVdOwS-DvtbjjDEbfw)
218218
*[本周小结！（贪心算法系列三）](https://mp.weixin.qq.com/s/JfeuK6KgmifscXdpEyIm-g)
219219
*[贪心算法：根据身高重建队列（续集）](https://mp.weixin.qq.com/s/K-pRN0lzR-iZhoi-1FgbSQ)
220+
*[贪心算法：用最少数量的箭引爆气球](https://mp.weixin.qq.com/s/HxVAJ6INMfNKiGwI88-RFw)
220221

221222

222223
* 动态规划

‎problems/0406.根据身高重建队列.md

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -130,8 +130,6 @@ public:
130130
131131
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n^2)了。
132132
133-
对于本题，不用vector的话，如果有多少人就申请多大的固定数组来模拟插入操作也可以，这样就不会有扩充数组的情况，但是就要真的手动模拟插入的操作了，比较麻烦。
134-
135133
改成链表之后，C++代码如下：
136134
137135
```C++

‎problems/0416.分割等和子集.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,11 @@
4444
* 背包如何正好装满，说明找到了总和为 sum / 2 的子集。
4545
* 背包中每一个元素一定是不可重复放入。
4646

47+
**按照这四部在分析一波**
48+
* 确定dp数组以及下标的含义
49+
* 确定递推公式
50+
* dp数组如何初始化
51+
* 确定遍历顺序
4752

4853
定义里数组为dp[]，dp[i] 表示 背包中放入体积为i的商品，最大价值为dp[i]。
4954

‎problems/0435.无重叠区间.md

Lines changed: 83 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,70 @@
1+
<palign='center'>
2+
<imgsrc="https://img-blog.csdnimg.cn/20201215214102642.png"width=400 >
3+
</p>
4+
<palign="center">
5+
<ahref="https://github.com/youngyangyang04/leetcode-master"><imgsrc="https://img.shields.io/badge/Github-leetcode--master-lightgrey"alt=""></a>
6+
<ahref="https://img-blog.csdnimg.cn/20201115103410182.png"><imgsrc="https://img.shields.io/badge/刷题-微信群-green"alt=""></a>
7+
<ahref="https://img-blog.csdnimg.cn/20201210231711160.png"><imgsrc="https://img.shields.io/badge/公众号-代码随想录-brightgreen"alt=""></a>
8+
<ahref="https://space.bilibili.com/525438321"><imgsrc="https://img.shields.io/badge/B站-代码随想录-orange"alt=""></a>
9+
<ahref="https://www.zhihu.com/people/sun-xiu-yang-64"><imgsrc="https://img.shields.io/badge/知乎-代码随想录-blue"alt=""></a>
10+
<ahref="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><imgsrc="https://img.shields.io/badge/头条-代码随想录-red"alt=""></a>
11+
</p>
112

2-
##思路
313

4-
这道题目如果真的去模拟去重复区间的行为，是非常麻烦的，还要有删除区间。
14+
>代码很简单，思路很高端
15+
16+
#435. 无重叠区间
17+
18+
题目链接：https://leetcode-cn.com/problems/non-overlapping-intervals/
19+
20+
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
21+
22+
注意:
23+
可以认为区间的终点总是大于它的起点。
24+
区间[1,2] 和[2,3] 的边界相互“接触”，但没有相互重叠。
25+
26+
示例 1:
27+
输入:[[1,2],[2,3],[3,4],[1,3]]
28+
输出: 1
29+
解释: 移除[1,3] 后，剩下的区间没有重叠。
30+
31+
示例 2:
32+
输入:[[1,2],[1,2],[1,2]]
33+
输出: 2
34+
解释: 你需要移除两个[1,2] 来使剩下的区间没有重叠。
35+
36+
示例 3:
37+
输入:[[1,2],[2,3]]
38+
输出: 0
39+
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
40+
41+
##思路
542

643
**相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？**
744

8-
按照右边界排序，从左向右遍历，右边界越小越好，因为右边界越小，留给下一个区间的空间就越大，所以可以从左向右遍历，优先选右边界小的。
45+
这其实是一个难点！
946

10-
按照左边界排序，那么就是从右向左遍历，左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
47+
按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
1148

12-
如果按照左边界排序，还从左向右遍历的话，要处理各个区间右边界的各种情况，就比较复杂了，这其实也就不是贪心了。
49+
按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
1350

51+
如果按照左边界排序，还从左向右遍历的话，要处理各个区间右边界的各种情况，就很复杂了。
52+
53+
一些同学做这道题目可能真的去模拟去重复区间的行为，这是比较麻烦的，还要去删除区间。
54+
55+
题目只是要求移除区间的个数，没有必要去真实的模拟删除区间！
1456

1557
**我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了**。
1658

59+
此时问题就是要求非交叉区间的最大个数。
60+
61+
右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。
62+
63+
局部最优推出全局最优，试试贪心！
64+
1765
这里记录非交叉区间的个数还是有技巧的，如图：
1866

19-
<imgsrc='../pics/435.无重叠区间.png'width=600> </img></div>
67+
![435.无重叠区间](https://img-blog.csdnimg.cn/20201221201553618.png)
2068

2169
区间，1，2，3，4，5，6都按照右边界排好序。
2270

@@ -26,7 +74,7 @@
2674

2775
区间4结束之后，在找到区间6，所以一共记录非交叉区间的个数是三个。
2876

29-
总共区间个数为6，减去非交叉区间的个数（3），为3。移除区间的最小数量就是3。
77+
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。
3078

3179
C++代码如下：
3280

@@ -41,7 +89,7 @@ public:
4189
if (intervals.size() == 0) return 0;
4290
sort(intervals.begin(), intervals.end(), cmp);
4391
int count = 1; // 记录非交叉区间的个数
44-
int end = intervals[0][1];
92+
int end = intervals[0][1]; // 记录区间分割点
4593
for (int i = 1; i < intervals.size(); i++) {
4694
if (end <= intervals[i][0]) {
4795
end = intervals[i][1];
@@ -52,6 +100,33 @@ public:
52100
}
53101
};
54102
```
103+
* 时间复杂度：O(nlogn) ，有一个快排
104+
* 空间复杂度：O(1)
105+
106+
大家此时会发现如此复杂的一个问题，代码实现却这么简单！
107+
108+
#总结
109+
110+
本题我认为难度级别可以算是hard级别的！
111+
112+
总结如下难点：
113+
114+
* 难点一：一看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排。
115+
* 难点二：排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了。
116+
* 难点三：直接求重复的区间是复杂的，转而求最大非重复区间个数。
117+
* 难点四：求最大非重复区间个数时，需要一个分割点来做标记。
118+
119+
**这四个难点都不好想，但任何一个没想到位，这道题就解不了**。
120+
121+
一些录友可能看网上的题解代码很简单，照葫芦画瓢稀里糊涂的就过了，但是其题解可能并没有把问题难点讲清楚，然后自己再没有钻研的话，那么一道贪心经典区间问题就这么浪费掉了。
122+
123+
贪心就是这样，代码有时候很简单（不是指代码短，而是逻辑简单），但想法是真的难！
124+
125+
这和动态规划还不一样，动规的代码有个递推公式，可能就看不懂了，而贪心往往是直白的代码，但想法读不懂，哈哈。
126+
127+
**所以我把本题的难点也一一列出，帮大家不仅代码看的懂，想法也理解的透彻！**
128+
129+
循序渐进学算法，认准「代码随想录」就够了，值得介绍给身边的朋友同学们！
55130

56131
>我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
57132
Lines changed: 44 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,44 @@
11

2-
// 如何转化为01背包问题
2+
#思路
3+
4+
尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，**这样就化解成01背包问题了**。
5+
6+
只不过物品的重量为store[i]，物品的价值也为store[i]。
7+
8+
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
9+
10+
接下来进行动规四步曲：
11+
12+
* 确定dp数组以及下标的含义
13+
14+
我习惯直接使用一维dp数组，如果习惯使用二维dp数组的同学可以看这篇：
15+
16+
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
17+
18+
* 确定递推公式
19+
20+
dp[j]有两个来源方向，一个是dp[j]自己，一个是dp[j - stones[i]]。
21+
22+
那么dp[j]就是取最大的：**dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);**
23+
24+
一些同学可能看到这dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i]，看着有点晕乎。
25+
26+
还是要牢记dp[j]的含义，要知道dp[j - stones[i]]为 容量为j - stones[i]的背包最大所背重量。
27+
28+
* dp数组如何初始化
29+
30+
既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。
31+
32+
因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000
33+
34+
如何初始化呢，只要因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。
35+
36+
* 确定遍历顺序
37+
38+
for循环遍历石头的数量嵌套一个for循环遍历背包容量，且因为是01背包，每一个物品只使用一次，所以遍历背包容量的时候要倒序。
39+
40+
具体原因我在
341

4-
尽量让石头分成，重量相同的两堆，这样就化解成 01背包问题了。
542

643
```
744
class Solution {
@@ -12,13 +49,14 @@ public:
1249
for (int i = 0; i < stones.size(); i++) sum += stones[i];
1350
int target = sum / 2;
1451
for (int i = 0; i < stones.size(); i++) {
15-
for (int j = target; j >= 0; j--) {
16-
if (j - stones[i] >= 0) {
17-
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
18-
}
52+
for (int j = target; j >= stones[i]; j--) {
53+
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
1954
}
2055
}
2156
return sum - dp[target] - dp[target];
2257
}
2358
};
2459
```
60+
61+
* 时间复杂度：O(m * n) , m是石头总重量，n为石头块数
62+
* 空间复杂度：O(m)

‎problems/动态规划理论基础.md

Lines changed: 48 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,62 +1,88 @@
1+
#什么是动态规划
12

23
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
34

4-
所以动态规划中每一个状态一定是由上一个状态推导出来的，**这一点就区分于贪心**
5+
所以动态规划中每一个状态一定是由上一个状态推导出来的，**这一点就区分于贪心**，贪心是局部直接选最优的，
6+
7+
在[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)中我举了一个背包问题的例子。
8+
9+
例如：有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。
10+
11+
动态规划中dp[j]是又dp[j-weight[i]]推导出来的。
12+
13+
但如果是贪心呢，dp[j]每次选一个最大的或者最小的就完事了。
14+
15+
所以贪心解决不了动态规划的问题，这也是最大的区别。
16+
17+
很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。
18+
19+
大家只要知道，动规是由前一个状态推导出来的，而贪心是局部直接算最优的，就够用了。
20+
21+
对于上述提到的背包问题，后序会详细讲解。
22+
23+
24+
#动态规划的解题步骤
525

626
题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp[i]表示的是什么。
727

828
这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。
929

10-
关于状态转移公式，
30+
状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。
1131

12-
对于动态规划问题，我将拆解为如下四步曲，这四步都搞清楚了，才能说把动态规划真的掌握了！
32+
**对于动态规划问题，我将拆解为如下四步曲，这四步都搞清楚了，才能说把动态规划真的掌握了！**
1333

1434
* 确定dp数组以及下标的含义
15-
* dp数组如何初始化
1635
* 确定递推公式
36+
* dp数组如何初始化
1737
* 确定遍历顺序
1838

39+
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
40+
41+
因为一些情况是递推公式决定了dp数组要输入初始化！
42+
1943
后面的讲解中我都是围绕着这四个点来经行讲解。
2044

2145
可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。
2246

23-
其实 确定递推公式 仅仅是解题里的一步而且， dp数组的初始化 以及确定遍历顺序，都非常重要，
47+
其实 确定递推公式 仅仅是解题里的一步而且，dp数组以及下标的含义， dp数组的初始化 以及确定遍历顺序，都非常重要。
2448

25-
**很多同学搞不清楚dp数组应该如何初始化，或者遍历的顺序，以至于记下来公式，但写的程序怎么改都通过不了**。
49+
后序的讲解的大家就会发现其重要性。
2650

27-
#动态规划如何debug
51+
很多同学甚至知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。
2852

29-
平时我自己写的时候也经常出问题，**找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！**
53+
#动态规划应该如何debug
3054

55+
平时我自己写的时候也经常出问题，**找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！**
3156

32-
#背包三讲
57+
一些同学对于dp的学习是上来就是俯视类型的，总是想一下子全盘接纳，一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。
3358

34-
背包九讲其实看起来还是有点费劲的，而且都是伪代码理解起来吃力
35-
<imgsrc='../pics/416.分割等和子集1.png'width=600> </img></div>
59+
这是一个很不好的习惯！
3660

61+
**做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果**。
3762

63+
然后在写代码，如果代码没通过就打印dp数组，看看是不是和自己推导的哪里不一样。
3864

65+
如果和自己模拟推导的一样，那么就是自己的递归公式有问题。
3966

40-
#完全背包
67+
如果和自己模拟推导的不一样，那么就是代码实现细节有问题。
4168

42-
有N 种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i种 物品的耗费的空间是Ci ，得到的价值是Wi 。求解:将哪些物品装入背包，可使 这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
69+
**这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了**。
4370

44-
这个问题非常类似于01背包问题，所不同的是每种物品有无限件
71+
我来举一个例子：一些同学可能代码通过不了，都会把代码抛到出来问：我这里代码都已经和题解一模一样的，为什么通过不了呢？
4572

73+
发出这样的问题之前，其实可以自己先思考这三个问题：
4674

47-
首先想想为什么01背包中要按照v递减的次序来 循环。让v递减是为了保证第i次循环中的状态F[i, v]是由状态F[i − 1, v − Ci]递 推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入 第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果F[i − 1, v − Ci]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加 选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结 果F[i, v − Ci]，所以就可以并且必须采用v递增的顺序循环。这就是这个简单的
48-
程序为何成立的道理。
75+
* 这道题目我推导状态转移公式了么？
76+
* 我打印dp数组的日志了么？
77+
* 打印出来了dp数组和我想的一样么？
4978

79+
**如果这灵魂三问自己都做到了，基本上这道题目也就解决了**，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。
5080

51-
值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。(可能说的就是组合或者排列了)
81+
然后在问问题，目的性就很强了，回答问题的同学也可以快速知道提问者的疑惑了。
5282

53-
#多重背包
83+
#动态规划可以解决哪一类问题
5484

55-
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费 的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
5685

57-
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略 微一改即可。
5886

5987

60-
#总结
6188

62-
后台回复：背包九讲 就可以获得pdf

0 commit comments

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