贪心算法day01
目录
理论基础?
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法并没有固定的套路
手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455.分发饼干??
看到题目的第一想法
对数组排序
两个for循环，从小到大，
满足条件则count+1，break
然后用一个startIndex 记录刚才分配的位置,让i从startindex开始，防止重复
看到代码随想录之后的想法
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
? ?1 不用两个for循环，用一个for循环，里面使用index来控制，当满足条件时，index--
自己实现过程中遇到的困难
?需要注意胃口和饼干尺寸? 尺寸>=胃口才能满足
先从大的开始匹配，要注意先后顺序，胃口用for循环，尺寸用index控制，不然有可能
若对尺寸进行for循环，所有的尺寸都无法满足最大胃口(最大尺寸<最大胃口)，胃口将永远不会缩减(index）
class Solution {
//我的思路 用小饼干投喂胃口小的，使用startIndex记录上次位置
/*public int findContentChildren(int[] g, int[] s) {
int count = 0;
int startIndex = 0;
Arrays.sort(g);
Arrays.sort(s);
//把最小的分配给最小的孩子
for(int j=0;j<g.length;j++){
for(int i=startIndex;i<s.length;i++){
if(s[i]>=g[j]){
count++;
startIndex=i+1;
break;
}
}
}
return count;
}*/
//卡哥思路，用大饼干投喂大的
//每次取最大的饼干
public int findContentChildren(int[] g, int[] s) {
int count = 0;
int index = s.length-1;
Arrays.sort(g);
Arrays.sort(s);
//应该是对g进行for循环
//不然index--可能永不执行，尺寸最开始小于胃口的话，就永远不会出现胃口的减小
/*for(int i=s.length-1;i>=0;i--){
if(index>0&&s[i]>=g[index]){
index--;
count++;
}
}*/
//如果对胃口for循环,最大胃口满足不了，就往下走，直到能满足的胃口
//用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式，这也是常用的技巧。
//额外用一个index 来确定第二个数组的遍历位置
for(int i=g.length-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
index--;
count++;
}
}
return count;
}
}376.?摆动序列??
看到题目的第一想法
摆动判断，
nums[i+1]-num[i]与nums[i] 和nums[i-1]异号
不知道如何判断两个异号
看到代码随想录之后的想法
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列
贪心算法? 把单调坡的都删除，得到一个最大的上下坡
? ?1 使用prediff 记录前一个 坡度，curdiff记录后一个坡度，当他们异号时记录下来
? ? ?有几种不同的情况需要讨论
? ? ? 1 上下坡中有平坡? 只记录平坡最后的节点 就是curr>0 or curr<0 pre可以=0
? ? ? ?2 单调坡中有平坡 不记录 需要把prediff=curdiff 放到 if中来进行，从而记住最开始的prediff的走向
? ? ? ? 3 首尾需要讨论 首默认prediff=0 ，尾部默认有个result=1
?????????if(prediff>=0&&curdiff<0)||（prediff<=0&&curdiff>0）把等于0的情况也考虑进去了?
自己实现过程中遇到的困难
? ? ? 1 上下坡中有平坡? 只记录平坡最后的节点 就是curr>0 or curr<0 pre可以=0
? ? ? ?2 单调坡中有平坡 不记录 需要把prediff=curdiff 放到 if中来进行，从而记住最开始的prediff的走向
? ? ? ? 3 首尾需要讨论 首默认prediff=0 ，尾部默认有个result=1
?????????if(prediff>=0&&curdiff<0)||（prediff<=0&&curdiff>0）把等于0的情况也考虑进去了?
每次记录curdiff? prediff只需要跟着curdiff走
class Solution {
public int wiggleMaxLength(int[] nums) {
//1 如何判断是否是摆动序列 看正负交替
//while()
//nums[i]-nums[i-1] >0
//nums[i+1] - nums[i]<0
//count++
//如何判断两个数异号
//for(int i=1;i<nums.length-1;i++){
//
//卡哥做法，
//本题是要求从原始序列中删除一些元素来获得子序列
//prediff 代表前一段的走向，curdiff 代表后一段的走向(prediff>0&&curdiff<0)||(prediff<0&&curdiff>0)
//贪心 获取每一阶段局部最优的 --》整体最优
//局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
//整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列
//需要考虑几种情况
//1 上下坡中有平坡 只保留平坡中的最后一个，就变成了峰值了
//2 数组首尾两端 首端用prediff=0 ，尾端用result=1
//3 单调坡度有平坡 单调坡度不需要记录
int prediff =0;
int result = 1;
int curdiff ;
for(int i=0;i<nums.length-1;i++){
curdiff = nums[i+1]-nums[i];
if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)){
result++;
prediff=curdiff;
}
}
return result;
}
}53.?最大子序和??
代码随想录
?
看到题目的第一想法
用for循环，双重，把最大子数组和做个记录
看到代码随想录之后的想法
贪心
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
单重for循环，使用sum记录遍历过的值(当前连续和)，使用result记录遍历过的最大值(所有连续和中最大的)
当sum<0时，令sum=0，因为sum<0 后续遍历只会让连续和越来越小
自己实现过程中遇到的困难
需要把result赋值为Integer.MIN_VALUE,令result=0全为负数时无法得到result
我最开始用sum>0 来更新result ，其实是不对的，因为有可能数组全负数，result永不更新
只需要sum<0时 更新sum就行，每次进入循环sum=sum+nums[i]
?
class Solution {
public int maxSubArray(int[] nums) {
//卡哥思路，遇到正数就记录，看是否比result大，如果大就令result=它
//贪心获取部分最大的和就行
//result不能等于0，要为最小值
int result = Integer.MIN_VALUE;;
int sum = 0;
for(int i=0;i<nums.length;i++){
//不能用sum>0 来做判断，要用sum<0来做判断
sum+=nums[i];
/*if(sum>0){
result = result>sum?result:sum;
}else{
sum = 0;
}*/
if(result<sum){
result = sum;
}
if(sum<0){
sum=0;
}
}
return result;
}
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！