贪心算法

贪心算法

1 简介

贪⼼的本质是选择每⼀阶段的局部最优，从⽽达到全局最优。

和贪心像对应的是动态规划，例如经典的背包问题，会在下一次笔记中记录

什么时候用贪心，什么时候用动态规划呢？

• 通过局部最优实现整体最优的情况
• 一般来说很难证明这一点，只能通过经验判断

2 解题步骤

• 将问题分解为若⼲个⼦问题
• 找出适合的贪⼼策略
• 求解每⼀个⼦问题的最优解
• 将局部最优解堆叠成全局最优解

但是实际上只要想清楚局部最优和全局最优，就已经足够了

3 经典题目

3.1 摆动序列

Leetcode 376

摆动序列有三种情况：

1. 正常的上下坡度
2. 有平坡的上下摆动
3. 单调坡度中出现了平坡

对每一个情况单独分析即可

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int prediff = 0; // 构造个虚拟的 pre 处理第一个
        int curdiff = 0;
        int result = 1; // 最后一个自动计算

        // 最后一个数字不进入循环
        for (int i = 0; i < nums.size() - 1; i++) {
            curdiff = nums[i] - nums[i + 1];
            // 使用 = 表示一边出现平坡，这种节点需要计算
            if ((prediff <= 0 && curdiff > 0) ||
                (prediff >= 0 && curdiff < 0)) {
                result++;
                prediff = curdiff;  // 只在坡度变化时记录，避免单调平坡
            }
        }
        return result;
    }
};

3.2 跳跃游戏 II

Leetcode 45

维护两个距离，如果到达了前一个距离的最大值，就要更新步数，同时把下一个改成前一个

class Solution {
public:
    int jump(vector<int>& nums) {
        // 维护一个两个最大位置，只要到达了 currdis 的最大距离，就需要 + 1 步数
        int currdis = 0;
        int nextdis = 0;
        int ans = 0;
        if (nums.size() == 1) return 0;
        for (int i = 0; i < nums.size(); i++) {
            nextdis = max(i + nums[i], nextdis); // 这里记得取最大值
            // 走到了最远的距离，需要更新
            if (i == currdis) {
                ans++;
                currdis = nextdis;
            }
            if (currdis >= nums.size() - 1) {
                return ans;
            }
        }
        return -1;
    }
};

3.3 分发糖果

Leetcode 135

贪心，分为正向和反向两种，第一次考虑正向局部最优，第二次考虑反向局部最优化

在第二次的时候徐需要使用 max 来同时不破坏第一次的局部最优化

#include <vector>
using namespace std;

class Solution {
public:
    int candy(vector<int>& ratings) {
        // 先全部设置为1
        // 直接计算相邻的就行
        int sum = 0;
        int pre = 0; // 上一个人的糖果数量
        // 正向遍历
        vector<int> candy(ratings.size(), 0);
        for (int i = 0; i < ratings.size(); i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                // 比上一个分高
                candy[i] = candy[i - 1] + 1;
            } else {
                // 不高或者第一个，只给 1
                candy[i] = 1;
            }
        }

        // 反过来再来一次
        for (int i = ratings.size() - 1; i >= 0; i--) {
            if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1]) {
                // 比上一个分高，有可能会更新，两者取最大值
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
        }
        for (int c : candy) {
            sum += c;
        }
        return sum;
    }
};

3.4 根据身高重建队列

Leetcode 406

这道题目有两个维度，如果出现了两个维度，一定要将一个维度确定了再考虑另一个

尝试将两个维度都分别排序，然后发现按照身高进行排序能够直接确定一个维度（实际解题可以两者都尝试）

有两个关键特性：

1. 如果身高比前面的小，那么可以随意插队，不影响已经排序的数据（所以要先按照身高排序）

2. 在已经排序的情况下，按照 k 进行重定位，一定能保证被插入的元素前面符合条件（按顺序插入）

3. 综上两条，如果先排序，再按照顺序插入，则可以满足整个队伍的条件

#include <vector>
#include <list>
#include <algorithm>
using namespace std;

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        // 比较身高，身高从大到小，相同则k从小到大
        if (a[0] != b[0]) {
            return a[0] > b[0];
        } else {
            return a[1] < b[1];
        }
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 使用链表，操作完毕更改成vector
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que;
        for (vector<int> p : people) {
            auto it = que.begin();
            // list 的 it 只能一个个加
            for (int j = 0; j < p[1]; j++) it++;
            que.insert(it, p);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

3.5 单调递增的数字

LeetCode 738

关键还是想清楚逻辑

一旦高位出现不递增的情况，高位 - 1，同时全部低位直接设置成 9 即可

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        // 如果高位不符合，改全部低位为9，将高位 - 1
        string nums = to_string(n);
        int flag = nums.size(); // 表示低位全部标记为9
        for (int i = nums.size() - 1; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                nums[i - 1]--;
                flag = i;
            }
        }
        for (int i = flag; i < nums.size(); i++) {
            nums[i] = '9';
        }
        return stoi(nums);
    }
};

3.6 监控二叉树

LeetCode 968

劲爆尾杀，做这题要很强的抽象建模能力，总结来是有两点：

1. 从叶子节点出发，每两个放一个摄像头，可以尽可能的监控更多
2. 将每一个节点状态分成：摄像头，被覆盖，无覆盖三种情况，并分别讨论每种情况的处理

既然是叶子结点，那就是后序遍历，然后返回值设置为状态

class Solution {
public:
    // 0 无覆盖 1 有摄像头 2 有覆盖
    // 使用后序遍历
    int minCameraCover(TreeNode* root) {
        int count = 0;
        int r = last_traversal(root, count);
        if (r == 0) count++; // 根节点没有被覆盖
        return count;
    }

    // Post Order Traversal
    int last_traversal(TreeNode* root, int& count) {
        if (!root) return 2; // null 视为有覆盖

        // 后序遍历，可以获得子节点的状态信息
        int l = last_traversal(root->left, count);
        int r = last_traversal(root->right, count);

        // 注意这三个顺序不可以颠倒！
        // 只要有个未被覆盖就需要装摄像头
        if (l == 0 || r == 0) {
            count++;
            return 1;
        }
        // 装了摄像头就不用装
        if (l == 1 || r == 1) return 2;
        // 有覆盖 需要交给父节点装摄像头
        if (l == 2 || r == 2) return 0;
        return -1;
    }
};

4 总结

贪心没有什么特定的套路，倒不如说更加考验问题抽象建模的能力

也许是我做题太少，我还没能力进行很好的总结，也许日后再写这一部分吧