贪心算法笔记

正如这个算法的名字一样，解决题目的时候用一种贪婪的思想来解决问题，比如说我们要从一堆钞票中取3张，并且总和要最高，所以我们在遍历这堆钞票价值的时候，尽可能地选择炒面面值最高的，这样就得到了最终解。所以，贪心的思路就是利用每一个阶段的最优解，最终达到全局最优解。下面的题目是一些利用贪心解决的算法问题，题目列表来源代码随想录入口

1.序列问题

1.1摆动序列

解法一：贪心

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;
            }
        }
        return result;
    }
};

解法二：动态规划

class Solution {
public:
    //动态规划实现：dp[i][0]表示第i个数作为山峰的摆动子序列的最长长度
    //动态规划实现：dp[i][1]表示第i个数作为山谷的摆动子序列的最长长度
    int dp[1005][2];//这个大小是根据题目给出数值的范围来定义的
    int wiggleMaxLength(vector<int>& nums) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = dp[0][1] = 1;
        for(int i = 1; i < nums.size(); i++){
            dp[i][0] = dp[i][1] = 1;
            for(int j = 0; j < i; j++){       
                if(nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

1.2单调递增的数字

这个题目如果我们暴力循环求解的话，会出现超时报错，所以我们采用构建的方式的，利用单调递增且数字尽可能大这两个条件来构建我们的答案数字。
实现思路：
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 2998

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        //flag用来标记赋值9从哪开始
        //设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for(int i = strNum.size() - 1; i > 0; i--){
            if(strNum[i - 1] > strNum[i]){
                flag = i;
                strNum[i - 1]--;
            }
        }
        for(int i = flag; i < strNum.size(); i++){
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

2.多维度权衡

在有些题目中，我们对于数据的处理不再是只考虑一个指标了，可能有两个甚至多个指标，以两个指标为例，排序需要考虑两个指标折衷的情况，这就是多维度权衡问题。

2.1分发糖果

这个题目中，每一个孩子能够获得多少糖果需要考虑左手和右手的人的分数（有两个维度需要考虑）

这个题目采用两次遍历解决，第一次遍历为从前往后：每一个人考虑左手那个人的rating，左手的人没自己高，那么自己的糖果数就比左手那个人多一个，否则就保持默认的一个。
第一次遍历完成之后，第二次遍历就从后往前，每一个人只考虑自己右手的那个人的rating，没自己高的话，自己根据自己本身糖果数和右手糖果数+1相比较取最大值。
两次遍历完成之后就是最少糖果分发的数量

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        //从前向后
        for(int i = 1; i < ratings.size(); i++){
            if(ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        //从后向前
        for(int i = ratings.size() - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        return accumulate(candyVec.begin(), candyVec.end(), 0);
    }
};

2.2根据身高重构队列

这个题目当中，我们不仅不需要考虑升高h，还需要考虑k值（前面有k个比当前人高）

class Solution {
public:
    //自定义排序规则：按照身高从大到小排，如果身高相同就让k小的在前面
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for(int i = 0; i < people.size(); i++){
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};

3.区间问题

区间问题一般都涉及到区间重叠去重问题，区间合并问题等等，具体可以看看下面相关的区间题目。

3.1跳跃问题

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxJump = nums[0];
        int i = 1;
        while(i < nums.size() && maxJump > 0){
            maxJump = max(maxJump - 1, nums[i]);
            i++;
        }
        if(i == nums.size()) return true;
        return false;
    }
};

3.2跳跃问题 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0; //当前覆盖的最远距离下标
        int ans = 0;
        int nextDistance = 0; //下一步覆盖的最远距离下标
        for(int i = 0; i < nums.size() - 1; i++){//注意i的取值范围
            nextDistance = max(nums[i] + i, nextDistance);//更新下一步覆盖的最远距离下标
            if(i == curDistance){
                curDistance = nextDistance;//更新当前的最远覆盖距离下标
                ans++;
            }
        }
        return ans;
    }
};

3.3用最小数量的箭引爆气球

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);

        int result = 1; //points不为空至少需要一支箭
        for(int i = 1; i < points.size(); i++){
            if(points[i][0] > points[i - 1][1]){
                //区间无重叠，需要一支箭
                result++;
            }else{
                //气球i和气球i - 1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }
        return result;
    }
};

3.4无重叠区间

解法一：区间右边界排序

class Solution {
public:
    //按照区间右边界排序
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() <= 1) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; //记录非交叉区间的个数
        int end = intervals[0][1]; //记录区间分割点
        for(int i = 1; i < intervals.size(); i++){
            if(end <= intervals[i][0]){
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

解法二：区间左边界排序

class Solution {
public:
    //按照区间左端值从小到大排列
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() <= 1) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int ans = 0;
        int end = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++){
            if(intervals[i][0] < end){
                ans++;
                //注意这里不是max而是min，因为要把更大右边界的那个区间给去除（因为它更可能和别的区间有交集）
                end = min(end, intervals[i][1]);
            }else{
                end = intervals[i][1];
            }
        }
        return ans;
    }
};

3.5划分字母区间

这个题目，我们首先获得每个字母最后出现的index，之后再遍历字符串，只要我们字符串下边i == 字母的最后index的时候，这个时候就可以分割一次，此时分割下来的字符串片段符合题目要求。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hash(26, 0);
        for(int i = 0; i < s.size();i++){
            hash[s[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.size(); i++){
            //找到字符出现的最远边界
            right = max(right, hash[s[i] - 'a']);
            if(i == right){
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

3.6合并区间

学习这个题目巧妙合并区间！！

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() <= 1) return intervals;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> result;
        //第一个区间就可以放进结果集里，后面如果重叠，再result上直接合并
        result.push_back(intervals[0]);

        for(int i = 1; i < intervals.size(); i++){
            if(result.back()[1] >= intervals[i][0]){//区间重叠
                //合并区间
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            }else{
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

4.其他

4.1最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res =nums[0];
        for(int i = 1; i < nums.size(); i++){
            nums[i] += max(nums[i - 1], 0);
            res = max(res, nums[i]);
        }
        return res;
    }
};

4.2加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for(int i = 0; i < gas.size(); i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum <  0){
                start =  i + 1;//起始位置更新
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
};

4.3监控二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int result;
    //后序遍历：左右根
    int travel(TreeNode* cur){
        //空节点，为有覆盖状态
        if(cur == NULL) return 2;

        int left = travel(cur -> left);
        int right = travel(cur -> right);
        //情况1：左右节点都有覆盖
        if(left == 2 && right == 2) return 0;
        //情况2
        if(left == 0 || right == 0){
            result++;
            return 1;
        }
        //情况3
        if(left == 1 || right == 1) return 2;
        //下面这个return -1 永远都不会执行
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        result = 0;
        //情况4：root未被覆盖
        if(travel(root) == 0){
            result++;
        }
        return result;
    }
};