Skip to content

Commit aa3fdac

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent f66167d commit aa3fdac

File tree

8 files changed

+373
-18
lines changed

8 files changed

+373
-18
lines changed

‎README.md

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -47,10 +47,10 @@
4747
* 求职
4848
* [程序员的简历应该这么写！！（附简历模板）](https://mp.weixin.qq.com/s/nCTUzuRTBo1_R_xagVszsA)
4949
* [BAT级别技术面试流程和注意事项都在这里了](https://mp.weixin.qq.com/s/815qCyFGVIxwut9I_7PNFw)
50-
* [深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Yzrkim-5bY0Df66Ao-hoqA)
51-
* [北京有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/FQTzoZtqXQ2rlS1UthGrag)
52-
* [上海有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/msqbX6eR2-JBQOYFfec4sg)
53-
* [成都有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Y9Qg22WEsBngs8B-K8acqQ)
50+
* [深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/3VJHF2zNohBwDBxARFIn-Q)
51+
* [北京有这些互联网公司，你都知道么？]()
52+
* [上海有这些互联网公司，你都知道么？]()
53+
* [成都有这些互联网公司，你都知道么？]()
5454

5555
* 算法性能分析
5656
* [关于时间复杂度，你不知道的都在这里！](https://mp.weixin.qq.com/s/LWBfehW1gMuEnXtQjJo-sw)
@@ -196,6 +196,8 @@
196196
* [贪心算法：跳跃游戏](https://mp.weixin.qq.com/s/606_N9j8ACKCODoCbV1lSA)
197197
* [贪心算法：跳跃游戏II](https://mp.weixin.qq.com/s/kJBcsJ46DKCSjT19pxrNYg)
198198
* [贪心算法：K次取反后最大化的数组和](https://mp.weixin.qq.com/s/dMTzBBVllRm_Z0aaWvYazA)
199+
* [本周小结！（贪心算法系列二）](https://mp.weixin.qq.com/s/RiQri-4rP9abFmq_mlXNiQ)
200+
* [贪心算法：加油站](https://mp.weixin.qq.com/s/aDbiNuEZIhy6YKgQXvKELw)
199201

200202

201203
* 动态规划
@@ -359,6 +361,7 @@
359361
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md) |哈希表 |简单|**模拟**|
360362
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md) |链表 |中等|**模拟**|
361363
|[0763.划分字母区间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0763.划分字母区间.md) |贪心 |中等|**双指针/贪心** 体现贪心尽可能多的思想|
364+
|[0738.单调递增的数字](https://github.com/youngyangyang04/leetcode/blob/master/problems/0738.单调递增的数字.md) |贪心算法 |中等|**贪心算法** 思路不错，贪心好题|
362365
|[0739.每日温度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0739.每日温度.md) |栈 |中等|**单调栈** 适合单调栈入门|
363366
|[0767.重构字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0767.重构字符串.md) |字符串 |中等|**字符串** + 排序+一点贪心|
364367
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md) |孤岛问题 |中等|**bfs** **dfs**|

‎problems/0135.分发糖果.md

Lines changed: 60 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,41 @@
1+
> 好了
12
2-
## 思路
33

4-
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑就会顾此失彼。
4+
# 135. 分发糖果
55

6-
本题贪心贪在哪里呢？
6+
链接：https://leetcode-cn.com/problems/candy/
77

8-
先确定每个孩子左边的情况（也就是从前向后遍历）
8+
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
9+
10+
你需要按照以下要求，帮助老师给这些孩子分发糖果：
11+
12+
* 每个孩子至少分配到 1 个糖果。
13+
* 相邻的孩子中，评分高的孩子必须获得更多的糖果。
14+
15+
那么这样下来，老师至少需要准备多少颗糖果呢？
16+
17+
示例 1:
18+
输入: [1,0,2]
19+
输出: 5
20+
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
21+
22+
示例 2:
23+
输入: [1,2,2]
24+
输出: 4
25+
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
26+
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
27+
28+
29+
# 思路
30+
31+
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，**如果两边一起考虑一定会顾此失彼**。
32+
33+
34+
先确定右边评分大于左边的情况（也就是从前向后遍历）
35+
36+
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
37+
38+
局部最优可以推出全局最优。
939

1040
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
1141

@@ -22,20 +52,27 @@ for (int i = 1; i < ratings.size(); i++) {
2252

2353
![135.分发糖果](https://img-blog.csdnimg.cn/20201117114916878.png)
2454

25-
再确定每个孩子右边的情况（从后向前遍历）
55+
再确定左孩子大于右孩子的情况（从后向前遍历）
2656

2757
遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
2858

2959
因为如果从前向后遍历，根据 ratings[i + 1] 来确定 ratings[i] 对应的糖果，那么每次都不能利用上前一次的比较结果了。
30-
**所以确定每个孩子右边的情况一定要从后向前遍历！**
3160

32-
此时又要开始贪心，如果 ratings[i] > ratings[i + 1]，就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，**因为candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多**。
61+
**所以确定左孩子大于右孩子的情况一定要从后向前遍历！**
62+
63+
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
64+
65+
那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
66+
67+
局部最优可以推出全局最优。
68+
69+
所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，**candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多**。
3370

3471
如图：
3572

3673
![135.分发糖果1](https://img-blog.csdnimg.cn/20201117115658791.png)
3774

38-
所以代码如下：
75+
所以该过程代码如下：
3976

4077
```C++
4178
// 从后向前
@@ -70,7 +107,22 @@ public:
70107
};
71108
```
72109
110+
# 总结
111+
112+
这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。
113+
114+
那么本题我采用了两次贪心的策略：
115+
116+
* 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
117+
* 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
118+
119+
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
120+
121+
就酱，如果感觉「代码随想录」干货满满，就推荐给身边的朋友同学们吧，关注后就会发现相见恨晚！
122+
123+
73124
> **我是[程序员Carl](https://github.com/youngyangyang04)，[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)可以找我，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
74125
75126
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
76127
128+

‎problems/0376.摆动序列.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,7 @@
6060

6161
针对以上情形，result初始为1（默认最右面有一个峰值），此时curDiff > 0 && preDiff <= 0，那么result++（计算了左面的峰值），最后得到的result就是2（峰值个数为2即摆动序列长度为2）
6262

63-
C++代码如下：
63+
C++代码如下（和上图是对应的逻辑）：
6464

6565
```C++
6666
class Solution {
@@ -70,8 +70,8 @@ public:
7070
int curDiff = 0; // 当前一对差值
7171
int preDiff = 0; // 前一对差值
7272
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
73-
for (int i = 1; i < nums.size(); i++) {
74-
curDiff = nums[i] - nums[i - 1];
73+
for (int i = 0; i < nums.size() - 1; i++) {
74+
curDiff = nums[i + 1] - nums[i];
7575
// 出现峰值
7676
if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
7777
result++;

‎problems/0738.单调递增的数字.md

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
2+
# 思路
3+
4+
## 暴力解法
5+
6+
暴力一波 果然超时了
7+
8+
```C++
9+
class Solution {
10+
private:
11+
bool checkNum(int num) {
12+
int max = 10;
13+
while (num) {
14+
int t = num % 10;
15+
if (max >= t) max = t;
16+
else return false;
17+
num = num / 10;
18+
}
19+
return true;
20+
}
21+
public:
22+
int monotoneIncreasingDigits(int N) {
23+
for (int i = N; i > 0; i--) {
24+
if (checkNum(i)) return i;
25+
}
26+
return 0;
27+
}
28+
};
29+
```
30+
## 贪心算法
31+
32+
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
33+
34+
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
35+
36+
这一点如果想清楚了，这道题就好办了。
37+
38+
**局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数**。
39+
40+
**全局最优：得到小于等于N的最大单调递增的整数**。
41+
42+
**但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9**。
43+
44+
此时是从前向后遍历还是从后向前遍历呢？
45+
46+
这里其实还有一个贪心选择，对于“遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9”的情况，这个strNum[i - 1]--的操作应该是越靠后越好。
47+
48+
因为这样才能让这个单调递增整数尽可能的大。例如：对于5486，第一位的5能不减一尽量不减一，因为这个减一对整体损失最大。
49+
50+
所以要从后向前遍历，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，这样保证这个减一的操作尽可能在后面进行（即整数的尽可能小的位数上进行）。
51+
52+
53+
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
54+
55+
C++代码如下：
56+
57+
```C++
58+
class Solution {
59+
public:
60+
int monotoneIncreasingDigits(int N) {
61+
string strNum = to_string(N);
62+
// flag用来标记赋值9从哪里开始
63+
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
64+
int flag = strNum.size();
65+
for (int i = strNum.size() - 1; i > 0; i--) {
66+
if (strNum[i - 1] > strNum[i] ) {
67+
flag = i;
68+
strNum[i - 1]--;
69+
}
70+
}
71+
for (int i = flag; i < strNum.size(); i++) {
72+
strNum[i] = '9';
73+
}
74+
return stoi(strNum);
75+
}
76+
};
77+
78+
```
79+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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/20201124161234338.png)，关注后就会发现和「代码随想录」相见恨晚！**
80+
81+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
82+

‎problems/0879.盈利计划.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2+
（待完整）
3+
https://www.cnblogs.com/grandyang/p/11108205.html
4+
5+
* 如果g >= group[k - 1]，则说明犯罪k可以执行，因为人数已经足够了
6+
* 如果profit[k - 1] >= p，则说明只执行犯罪k就能达到利润p，可以单独执行，接着我们考虑必须执行犯罪k，然后加上前面的利润不低于p - profit[k - 1]的方案，这样凑出的方案利润也会超过p
7+
* 否则犯罪k不能执行，此时只能直接将前面 dp[k - 1][g][p]利润超过p的方案搬过来
8+
9+
```
10+
class Solution {
11+
public:
12+
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
13+
int K = group.size(), MOD = 1e9 + 7;
14+
//dp[k][g][p]使用计划[1,2,3,... k],最多g个人，盈利不少于p个方案个数
15+
vector<vector<vector<int> > > dp(K + 1, vector<vector<int> >(G + 1, vector<int>(P + 1, 0)));
16+
for (int k = 1; k <= K; ++k){
17+
for (int g = 1; g <= G; ++g){
18+
for (int p = 0; p <= P; ++p){
19+
//如果人数g能够执行第k种犯罪（人数g >= 第k种犯罪需要的人数group[k - 1]）
20+
if (g >= group[k - 1]){
21+
if (profit[k - 1] >= p){
22+
//如果执行第k种犯罪获得的利润profit[k - 1]不小于p，则可以单独执行该犯罪
23+
dp[k][g][p] += 1;
24+
}
25+
//将第k个方案产生的利润profit[k]与之前方案产生的利润凑出不少于p
26+
//dp[k - 1][g - group[k]][p > profit[k] ? p - profit[k] : 0]表示在使用[1, k - 1]这些犯罪，使用人数不超过g - group[k]，获得路润不少于p - profit[k]
27+
//这样前面的产生p - profit[k]的利润再加上执行第k个犯罪的利润profit[k]就能到达到利润不少于p（注意p 可能大于 profit[k]，所以不能为负数）
28+
dp[k][g][p] = (dp[k][g][p] + dp[k - 1][g - group[k - 1]][p > profit[k - 1] ? p - profit[k - 1] : 0]) % MOD;
29+
}
30+
//不执行第k个犯罪，直接将前面的利润超过p的方案搬过来
31+
dp[k][g][p] = (dp[k][g][p] + dp[k - 1][g][p]) % MOD;
32+
}
33+
}
34+
}
35+
return dp[K][G][P];
36+
}
37+
};
38+
39+
```

‎problems/导读.md

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,9 +19,9 @@
1919
* [程序员的简历应该这么写！！（附简历模板）](https://mp.weixin.qq.com/s/nCTUzuRTBo1_R_xagVszsA)
2020
* [BAT级别技术面试流程和注意事项都在这里了](https://mp.weixin.qq.com/s/815qCyFGVIxwut9I_7PNFw)
2121
* [深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Yzrkim-5bY0Df66Ao-hoqA)
22-
* [北京有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/FQTzoZtqXQ2rlS1UthGrag)
23-
* [上海有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/msqbX6eR2-JBQOYFfec4sg)
24-
* [成都有这些互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Y9Qg22WEsBngs8B-K8acqQ)
22+
* [北京有这些互联网公司，你都知道么？]()
23+
* [上海有这些互联网公司，你都知道么？]()
24+
* [成都有这些互联网公司，你都知道么？]()
2525

2626
* 算法性能分析
2727
* [关于时间复杂度，你不知道的都在这里！](https://mp.weixin.qq.com/s/LWBfehW1gMuEnXtQjJo-sw)
@@ -166,6 +166,8 @@
166166
* [贪心算法：跳跃游戏II](https://mp.weixin.qq.com/s/kJBcsJ46DKCSjT19pxrNYg)
167167
* [贪心算法：K次取反后最大化的数组和](https://mp.weixin.qq.com/s/dMTzBBVllRm_Z0aaWvYazA)
168168
* [本周小结！（贪心算法系列二）](https://mp.weixin.qq.com/s/RiQri-4rP9abFmq_mlXNiQ)
169+
* [贪心算法：加油站](https://mp.weixin.qq.com/s/aDbiNuEZIhy6YKgQXvKELw)
170+
169171

170172
（持续更新.....）
171173

0 commit comments

Comments
 (0)