跳转至

Day26 | Part1

约 474 个字 38 行代码 预计阅读时间 2 分钟

理论基础

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

贪心算法并没有固定的套路。唯一的难点就是如何通过局部最优，推出整体最优

刷题时，手动模拟一下感觉可以局部最优推出整体最优，且想不到反例，则试一试贪心

一般解题步骤:

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

做题的时候，只要想清楚局部最优是什么，如何推导出全局最优，就够了

455.分发饼干

局部最优: 大饼干喂给胃口大的; 全局最优喂饱尽可能多的小孩

  • 排序,从后向前遍历小孩数组g，用大饼干s优先满足胃口大的，并统计满足小孩数量
1
2
3
4
5
6
7
8
int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int cnt = 0, idx = s.size() - 1;
    for(int i = g.size() - 1; i >= 0; i --) 
        if(idx >= 0 && s[idx] >= g[i]) cnt ++, idx --;
    return cnt;
}

376.摆动序列

  • 局部最优：删除单调坡度上的节点，那么这个坡度就可以有两个局部峰值
  • 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列

PS: 不需要真正删除,计数即可(要求的是最长摆动子序列的长度)

三种情况: 上下坡中有平坡ref, 数组首尾两端ref, 单调坡中有平坡ref

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int wiggleMaxLength(vector<int>& nums) {
    if(nums.size() <= 1) return nums.size();
    // cnt记录峰值个数，序列默认序列最右边有一个峰值
    int cnt = 1, cur = 0, prev = 0; //prev前一对差值, cur当前一对差值
    for(int i = 0; i < nums.size() - 1; i ++) {
        cur = nums[i + 1] - nums[i];
        if(prev >= 0 && cur < 0 || prev <= 0 && cur > 0) cnt ++, prev = cur;
    }
    return cnt;
}

也可以利用动态规划 → 参考

53.最大子序和

暴力: 第一层for设置起始位置，第二层for遍历数组寻找最大值

  • 203/210 cases passed(N/A) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int maxSubArray(vector<int>& nums) {
    int res = INT32_MIN, cnt;
    for(int i = 0; i < nums.size(); i ++) {
        cnt = 0;
        for(int j = i; j < nums.size(); j ++) {
            cnt += nums[j];
            res = cnt > res ? cnt : res;
        }
    }
    return res;
}

贪心 :

  • 局部最优：当前连续和为负数时立刻放弃，从下一个元素重新计算连续和
  • 全局最优：选取最大连续和

相当于是暴力解法中的不断调整最大子序和区间的起始位置 示意图

1
2
3
4
5
6
7
8
9
int maxSubArray(vector<int>& nums) {
    int res = INT32_MIN, cnt = 0;
    for(int i = 0; i < nums.size(); i ++) {
        cnt += nums[i];
        if(cnt > res) res = cnt;// 取区间累计的最大值
        if(cnt <= 0) cnt = 0; // 重置最大子序起始位置
    }
    return res;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论