CCPC贪心专练（代码随想录篇）

class Solution {
// 核心思想是用尽可能大的饼干满足尽可能大的胃口，从而最大化能满足的孩子数量。
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int cnt = 0;
        int l =g.size()-1, r = s.size()-1;
        while(l>=0&&r>=0){
            if(g[l]<=s[r]){
                r--,l--;
                cnt++;
            }else{
                l--;
            }
        }
        return cnt;
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
    int up = 1, down = 1; // 分别记录以当前元素结尾的上升/下降摆动序列长度
    for (int i = 1; i < nums.size(); ++i) {
        int diff = nums[i] - nums[i-1];
        if (diff > 0) up = down + 1;    // 当前是上升，只能由前一个下降的序列延长
        else if (diff < 0) down = up + 1; // 当前是下降，只能由前一个上升的序列延长
        // 差值为0时，up和down保持不变（不影响结果）
    }
    return max(up, down);
    }
};

class Solution {
    // 设计还需巧妙，巧妙的避开，上一个状态对自身的影响
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int maxN = nums[0];
        for(int i=1; i<nums.size(); ++i){
            sum = sum<0?0:sum; // 必须及时更新这个状态
            sum+=nums[i];
            maxN = max(maxN,sum);
        }
        return maxN;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 有一种，情况，经常会被忽略掉，就是最后一位是0的话，依旧会被跳过。
        int maxFlag = nums[0];
        for(int i=0; i<nums.size()-1; ++i){
            if(maxFlag==0&&maxFlag==nums[i]) return false;
            maxFlag = maxFlag<nums[i]?nums[i]:maxFlag;
            maxFlag--;
        }
        return true;
    }
};

class Solution {
    // 总是对这种特殊位置，判断不清晰，本题就是错在了这种特殊位置上
public:
    int jump(vector<int>& nums) {
        if(nums.size()<=1) return 0;
        // 不断更新，能够抵达的最远距离
        int cur_n = nums[0],max_n=nums[0];
        int cnt = 0; // 次数
        for(int i=0; i<nums.size()-1; ++i){ // 来，让我爽一把
            max_n = max(max_n,i+nums[i]); 
            if(cur_n==i){ // 到了不得不蹦的位置
                cnt++;
                cur_n=max_n;
            }
        }
        return cnt+1;
    }
};

class Solution {
    // 这道题目的贪心，好帅啊，可以重复练习几次，可以记录下来的呢。
    static bool cmp(int a,int b){
        return abs(a)<abs(b);
    }
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(), cmp);
        int sum = 0;
        for(int i=nums.size()-1; i>=0; --i){
            if(nums[i]<0&&k!=0){
                k--;
                sum-=nums[i];
            }else sum+=nums[i];
        }
        if(k>0&&k%2!=0){ // k还剩余
            sum-=2*abs(nums[0]); 
        }
        return sum;
    }
};

class Solution {
    // 通过排除局部的失败情况，快速排除不可能的起点。
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> diff(gas.size());
        int sum = 0;
        for(int i=0; i<gas.size(); ++i){
            diff[i] = gas[i]-cost[i];
            sum += diff[i];
        }
        if(sum<0) return -1;
        int cnt = 0;
        int cur = 0;
        for(int i=0; i<diff.size(); ++i){
            if(cur+diff[i]<0){
                cnt = i+1;
                cur = 0;
            }else cur += diff[i];
        }
        return cnt;
    }
};

class Solution {
public:
    int candy(vector<int>& ratings) {
        int len = ratings.size();
        vector<int> randy(len,0);
        // 从左向右 来一次
        randy[0]=1;
        for(int i=1; i<len; ++i){
            if(ratings[i]>ratings[i-1]) randy[i]=randy[i-1]+1;
            else randy[i]=1;
        }
        // 从右向左 来一次 被用来修补修补
        for(int i=len-2; i>=0; --i){
            if(ratings[i]>ratings[i+1]&&randy[i]<=randy[i+1]) randy[i] = randy[i+1]+1;
        }
        int sum = 0;
        for(int i : randy) sum+=i; 
        return sum;
    }
};

class Solution {
    // 我觉得，这是一道非常酷的题，非常有意思的呢
    // 非常有记录的必要
    static bool cmp(vector<int> a1, vector<int> a2){
        if(a1[0]==a2[0]) return a1[1]<a2[1]; // 从小到大排序
        return a1[0]>a2[0]; // 从大到小排序
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> res;
        
        for(int i=0; i<people.size(); ++i){
            if(people[i][1]==0) res.insert(res.begin()+people[i][1],people[i]);
            else res.insert(res.begin()+people[i][1],people[i]);
        }

        return res;
    }
};

class Solution {
    // 本题考查，对重叠区间的处理方式，先遍历，然后设置区间
    static bool cmp(vector<int> p1,vector<int> p2){
        return p1[0]<p2[0]; // 从小到大
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int cnt = 0;
        int l=-1,r=-1; // 左端点，有端点
        for(int i=0; i<points.size(); ++i){
            int cur_l = points[i][0];
            int cur_r = points[i][1];
            if((cur_l>=l&&cur_l<=r)||(cur_r<=r&&cur_r>=l)){
                l = max(cur_l,l);
                r = min(cur_r,r);
            }else{
                cnt++;
                l = cur_l;
                r = cur_r;
            }
        }
        return cnt;
    }
};

class Solution {
    // 本题考查，对重叠区间的处理方式，先遍历，然后设置区间
    static bool cmp(vector<int> p1,vector<int> p2){
        return p1[0]<p2[0]; // 从小到大
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int cnt = 0;
        int l=-1,r=-1; // 左端点，有端点
        for(int i=0; i<points.size(); ++i){
            int cur_l = points[i][0];
            int cur_r = points[i][1];
            if((cur_l>=l&&cur_l<=r)||(cur_r<=r&&cur_r>=l)){
                l = max(cur_l,l);
                r = min(cur_r,r);
            }else{
                cnt++;
                l = cur_l;
                r = cur_r;
            }
        }
        return cnt;
    }
};

class Solution {
    // 题目读错，结果就很抽象
public:
    vector<int> partitionLabels(string s) {
        vector<int> pos(s.size(),0);
        vector<int> hash(26,0); // 跟这个无关

        // 记录字符序
        for(int i=s.size()-1; i>=0; --i){ // 字符序
            int ch = s[i]-'a'; // 转化
            hash[ch] = max(hash[ch],i);
            pos[i] = hash[ch];
        }
    
        vector<int> res;
        int cnt = 0;
        int maxn = pos[0];
        for(int i=0; i<s.size(); ++i){ // 开始分割字符
            cnt++; // 个数
            maxn = max(maxn,pos[i]); // 最早能结束的位置
            if(i==maxn){
                res.push_back(cnt); // 存储结果
                cnt = 0; // 置零
            }
        }
        if(cnt!=0) res.push_back(cnt);
        return res;
    }
};

class Solution {
    // 从右往左寻找递减点，局部调整高位，确保寻找到最大的单调递增数
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        int flag = str.size()+2;
        for(int i=str.size()-1; i>0; --i){
            if(str[i-1]>str[i]){
                flag = i;
                str[i-1]--;
            }
        }
        for(int i=flag; i<str.size(); ++i){
            str[i]='9';
        }
        return stoi(str);
    }
};

/**
 * 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 cnt = 0;
    // 什么都无0 覆盖1 照相机2
    int dfs(TreeNode* root){
        // 覆盖
        if(root == nullptr) return 1; // 表示被覆盖
        
        int l_num = dfs(root->left);
        int r_num = dfs(root->right);
        
        if(l_num==0 || r_num==0){ // 子节点，未被照到
            cnt++;
            return 2; // 放置照相机
        }
        if(l_num==2 || r_num==2){ // 字节点，有照相机
            return 1; // 于是该节点就被覆盖了
        }
        
        return 0; // 表示该节点，没人照顾。
    }               

    int minCameraCover(TreeNode* root) {
        cnt = 0;
        if(dfs(root)==0) cnt++; // 如果根节点，未被覆盖
        return cnt;
    }
};