贪心算法day01

发布时间:2024年01月04日

目录

理论基础?

455.分发饼干??

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难

376.?摆动序列??

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难

53.?最大子序和??

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难


理论基础?

代码随想录

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

贪心算法并没有固定的套路

手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

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;

    }
}

文章来源:https://blog.csdn.net/weixin_47455684/article/details/135308652
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。