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

Commitaa3fdac

Browse files
Update
1 parentf66167d commitaa3fdac

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
classSolution {
@@ -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++;
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+
classSolution {
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)
[8]ページ先頭
©2009-2025 Movatter.jp