【代码随想录】刷题笔记Day34

发布时间:2023年12月17日

前言

  • 考过概率论,发过一场烧,兜兜转转又一月,轻舟已撞万重山,赶紧刷题

贪心算法理论基础

  • 贪心的本质:局部最优→全局最优
  • 无套路,常识性推导 + 举反例

455. 分发饼干 - 力扣(LeetCode)

  • 先排序,局部最优:最大/小的饼干分给最大/小的小孩,秒了
  • class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            sort(g.begin(), g.end());
            sort(s.begin(), s.end());
            int j = s.size() - 1;
            int sum = 0;
            for(int i = g.size() - 1; i >= 0; i--){
                if(j >= 0 && s[j] >= g[i]){
                    sum++;
                    j--;
                }
            }
            return sum;
        }
    };

?376. 摆动序列 - 力扣(LeetCode)

  • 情况一:上下坡中有平坡,取一边的差值等于0
  • 情况二:数组首尾两端,取一个虚拟头,preDiff初始为0,平坡
  • 情况三:单调坡中有平坡,遇到拐点再更新prediff
  • class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            if (nums.size() <= 1) return nums.size();
            int curDiff = 0; // 当前一对差值
            int preDiff = 0; // 前一对差值
            int result = 1;  // 记录峰值个数,序列默认序列最右边有一个峰值
            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; // 注意这里,只在摆动变化的时候更新prediff
                }
            }
            return result;
        }
    };
  • // 题解来的代码,类似自己起初的思路(可惜自己用flag-1/1调不出来)
    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            int res = 0;
            int reverse = 0; //初始不知道第一次会上坡还是下坡
            for(int i = 1; i < nums.size(); i++){
                if(nums[i-1]<nums[i] && reverse != 1){  // 这个≠很精髓
                    res++;
                    reverse = 1;//记录上坡了
                }
                else if(nums[i-1]>nums[i] && reverse != 2){
                    res++;
                    reverse = 2;//记录下坡了
                } 
            }
            return res + 1; //res是两两比较得来的值,差一个边界值要+1
        }
    };

?53. 最大子数组和 - 力扣(LeetCode)

  • 贪心思路:若连续和为负数,则从下一个数重新开始求连续和
  • 注意:用result及时记录连续和的最大值(也可能是负的)
  • class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int result = INT32_MIN;
            int count = 0;
            for (int i = 0; i < nums.size(); i++) {
                count += nums[i];
                if (count > result) { // 取区间累计的最大值(相当于不断确定最大子序终止位置)
                    result = count;
                }
                if (count <= 0) count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
            }
            return result;
        }
    };

后言

  • 第二题死磕太久了,蓝受,一下子就10点了,贪心第一次做好难想哦~?
文章来源:https://blog.csdn.net/qq_56077562/article/details/134956893
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。