代码随想录-算法训练营day31(贪心算法01:分发饼干,摆动序列,最大子数组和)
第八章 贪心算法 part01
● 理论基础
● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和
贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。
不用花心思去研究其规律， 没有思路就立刻看题解。
基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。
学完贪心之后再去看动态规划，就会了解贪心和动规的区别。
详细布置
理论基础
https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
455.分发饼干
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
376. 摆动序列
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
53. 最大子序和
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl
●day 26 休息
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BRday31
分发饼干
//优先满足大胃口
class Solution {
public int findContentChildren(int[] g, int[] s) {
//贪心无套路,也不用严格证明,局部最优能推出全局最优即可
//大饼干尽量满足胃口大的孩子
//或者尽量用小饼干去满足一个小孩
Arrays.sort(g);//记得排序
Arrays.sort(s);
int sindex = s.length - 1;
int result = 0;
for(int i = g.length - 1; i>=0;i--){//遍历大胃口,有限考虑大胃口
if( sindex >= 0 && s[sindex] >= g[i]){
result++;
sindex--;
}
}
return result;
}
}
//优先利用小饼干
class Solution {
public int findContentChildren(int[] g, int[] s) {
//贪心无套路,也不用严格证明,局部最优能推出全局最优即可
//大饼干尽量满足胃口大的孩子
//或者尽量用小饼干去满足一个小孩
Arrays.sort(g);//记得排序
Arrays.sort(s);
int result = 0;
int gstart = 0;
for(int i = 0; i < s.length ; i++){//遍历小饼干,尽量去满足一个小孩
if( gstart <= g.length - 1 && s[i] >= g[gstart] ){
result++;
gstart++;
}
}
return result;
}
}
摆动序列
class Solution {
public int wiggleMaxLength(int[] nums) {
//双指针记录坡度变化
int pre = 0;
int last = 0;
int result = 1;//默认最后有一个坡
for( int i = 0; i < nums.length - 1; i++ ){//不用判断最后一个
last = nums[i + 1] - nums[i];
if( pre >= 0 && last < 0 || pre <= 0 && last > 0){
result++;
pre = last;//只在坡度方向有变化的时候才更改
}
}
return result;
}
}
最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
//连续和为负数直接抛弃
int sum = 0;
int result = nums[0];
for( int i = 0; i < nums.length; i++){
sum += nums[i];
if( sum > result) result = sum;
if( sum < 0) sum = 0;//不如重新开始
}
return result;
}
}
感谢大佬分享:
代码随想录-算法训练营day31【贪心算法01：理论基础、分发饼干、摆动序列、最大子序和】-CSDN博客