当前位置: 首页 > article >正文

代码随想录打卡Day27

今天是贪心算法的第一天,感觉除了第一道题很简单,第二道和第三道在想的时候都没完全把思路想清楚,似懂非懂的,代码老是写不对,无奈只能去看视频讲解。

455.分发饼干

这道题先把两个输入的数组升序排列,然后用两个指针分别指向g和s,当满足s[j] >= g[i]的时候则直接将i++,j++,result++,否则仅j++。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int result = 0;
        // sort(g.begin(), g.end());
        // sort(s.begin(), s.end());
        for(int i = 0, j = 0; i < g.size() && j < s.size(); ){
            if(s[j] >= g[i]){
                result++;
                i++;
                j++;
            }
            else j++;
        }
        return result;
    }
};

376. 摆动序列

这道题目老老实实看讲解,这道题用图画出来特别形象,感觉这个也用到了之前二叉树的那种双指针法的思路,这里需要默认首元素之前存在一个平坡,由于prediff初始值为0,则判断条件中prediff需要>=0或者<=0,curdiff则为<0或>0。这道题目还有一个关键,就是只有prediff和curdiff符号相反时才会更新prediff,并不是每个循环都会更新prediff,这主要是为了应对平坡和单调平坡的情况,这一点其实还蛮难想到的。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2) return 1;  //只有一个元素的情况
        int result = 1;  //即使是2个相等元素,结果也至少为1
        int prediff = 0;  //默认首元素之前存在一个平坡
        int curdiff = 0; //记录当前元素与后一个元素之间的差值
        for(int i = 0; i < nums.size() - 1; i++){
            curdiff = nums[i + 1] - nums[i];
            if((prediff >= 0 && curdiff < 0) ||
            (prediff <= 0 && curdiff > 0)){
                result++;
                prediff = curdiff;
            }
        }
        return result;
    }
};

53. 最大子序和

这道题在做的时候首先想到的是暴力法可以把这道题AC,但是没有用暴力,在想怎么用贪心解决的时候我只想到了最大和子序列一般从正数开始,却没有想到还有数组中全为负数的情况,另外,用贪心法应该考虑的是总和小于0时立马抛弃当前的和,而不是考虑最大和子序列应该从哪个数开始。看完思路以后自己写了下代码,老是写不对,debug了几十分钟,遂放弃,看代码实现。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
            if(sum > result) result = sum;
            if(sum < 0) sum = 0;            
        }
        return result;
    }
};

哎,感觉后两道贪心还是有点点难,后面要二刷的。


http://www.kler.cn/a/297400.html

相关文章:

  • 【Oracle篇】全面理解优化器和SQL语句的解析步骤(含执行计划的详细分析和四种查看方式)(第二篇,总共七篇)
  • [数据集][目标检测]电动车入梯进电梯电单车入梯检测数据集VOC+YOLO格式7106张3类别
  • (六十八)第 10 章 内部排序(简单选择排序)
  • zookeeper是啥?在kafka中有什么作用
  • 暂停Windows更新方法
  • Arduino IDE安装操作指南
  • 协议层面优化a2dp性能
  • STM32 RTC实时时钟
  • 【数学建模】2024数学建模国赛经验分享
  • SpringCloud:Gateway
  • Spring Boot集成Hazelcast Jet快速入门DEMO
  • Oceanbase 数据库审计
  • cas单点登录流程揭密
  • 八、3 DMA数据转运(代码)
  • ICLR2024: 大视觉语言模型中对象幻觉的分析和缓解
  • 数学建模笔记——层次分析法
  • 图像去噪技术:传统中值滤波与改进中值滤波算法的比较
  • 虚幻引擎VR游戏开发02 | 性能优化设置
  • Docker打包镜像
  • 基于SpringBoot的大健康养老公寓管理系统