leetcode-notes-20230914

134. 加油站（C++贪心算法实现）

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //设置currSum，用来保存从i+1更新后的sum总油量和
        int currSum = 0;
        int totalSum = 0;
        //结果返回变量
        int start = 0;

        // 遍历油的数组
        for(int i = 0;i < gas.size();i++){
            totalSum += gas[i] - cost[i];
            currSum += gas[i] - cost[i];

            if(currSum < 0){
                currSum = 0;
                start = i + 1;
            }
        }

        if(totalSum < 0){
            return -1;
        }

        return start;
    }
};

135. 分发糖果（C++贪心算法实现）

class Solution {
public:
    int candy(vector<int>& ratings) {
        //设置和ratings长度相同的数组，并初始化元素值为0
        vector<int> candys(ratings.size(), 1);

        //从前向后遍历，右孩子大于左孩子的情况
        for(int i = 1; i < ratings.size();i++){
            if(ratings[i] - ratings[i - 1] > 0){
                candys[i] = candys[i - 1] + 1;//这个时候有孩子一定大于左孩子1
            }
        }

        //从后向前遍历
        //判断左孩子大于右孩子的情况
        for(int i = ratings.size() - 2;i >= 0;i --){
            if(ratings[i] - ratings[i + 1] > 0){
                candys[i] = max(candys[i], candys[i + 1] + 1);
            }
        }

        //统计总和
        int result = 0;
        for(int i = 0;i < candys.size();i++){
            result += candys[i];
        }
        return result;
    }
};

860. 柠檬水找零（C++贪心算法实现）

//其中当bills[i] == 20时，优先使用一张10面值+一张5面值的，尽可能多地保留5面值，因为5面值相对来说更加通用
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        //进行模拟
        //curr_xxx表示当前商家手里面的钱的数量
        int curr_five = 0;
        int curr_ten = 0;
        int curr_twenty = 0;

        //for循环实现遍历
        for(int i = 0;i < bills.size();i++){
            if(bills[i] == 5){
                curr_five += 1;
            }else if(bills[i] == 10){
                //10元面值的钱增加1
                curr_ten += 1;
                //5元面值的钱减少1
                if(curr_five <= 0){
                    return false;
                }else{
                    curr_five -= 1;
                }
            }else if(bills[i] == 20){
                //20元面值的钱增加1
                curr_twenty += 1;
                //有两种可能
                if(curr_ten >= 1 && curr_five >= 1){//第1种：找一张10面值+一张5面值的
                    curr_ten -= 1;
                    curr_five -= 1;
                    continue;
                }else if(curr_five >= 3){//第2种：找三张5面值的
                    curr_five -= 3;
                    continue;
                }else{//没有满足的找零，那么直接返回false
                    return false;
                }
            }
        }
        return true;
    }
};

406. 根据身高重建队列（C++贪心算法实现）

class Solution {
public:

    //设置排列器，传入参数为vector数组地址
    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) {
        //思路：先排身高最高的，身高相同的，按照后边的ki进行排序
        sort(people.begin(), people.end(), cmp);

        vector<vector<int>> result;//创建的结果返回数组
        
        //在循环中根据每个元素的ki对元素进行重新排序即可得到最终的结果队列
        for(int i = 0;i < people.size();i++){
            //得到当前i同学应该在的位置
            int pos = people[i][1];
            result.insert(result.begin() + pos, people[i]);
        }
        return result;
    }
};

406. 根据身高重建队列（C++贪心算法实现，将结果队列从vector<vector>替换为list<vector>）

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>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        //使用list数组实现
        list<vector<int>> result;
        for(int i = 0;i < people.size();i++){
            int pos = people[i][1];
            //使用迭代器
            std::list<vector<int>>::iterator it = result.begin(); 
            while(pos--){
                it++;
            }
            result.insert(it, people[i]);
        }
        return vector<vector<int>>(result.begin(), result.end());
    }
   
};

452. 用最少数量的箭引爆气球（C++贪心算法实现）

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) {
        //思路：寻找最少的x坐标，使得其落在尽可能多的区间内
        sort(points.begin(), points.end());

        //取排序后的第一个数组元素的右边界
        int right = points[0][1];
        int result = 1;

        //遍历从index=1开始的所有元素，得到最终的结果
        for(int i = 1; i < points.size();i++){
            if(points[i][0] > right){//表示下一个元素大于上一个的最小右right边界，需要增加箭的数量
                right = points[i][1];
                result++;
            }else{//表示该区间与上一个区间有交集
                right = min(points[i][1], right);//更新right为该区间和上一个区间的最小right边界
            }
        }
        return result;
    }
};

435. 无重叠区间（C++贪心算法实现）

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) {
        //思路：按照左边界进行排序之后，从index=1开始判断，该区间的左边界是否在右边界以内
        //如果是，那么判断是删除当前区间还是删除上一个区间，这个看哪个区间的右边界大，右边界大的优先删除
        //即可

        sort(intervals.begin(), intervals.end(), cmp);
        int pre = 0;//保存的前一个保留下来的数组index
        int result = 0;
        
        for(int i = 1;i < intervals.size();i++){
            if(intervals[i][0] < intervals[pre][1]){
                //判断保留下来哪一个区间
                if(intervals[i][1] < intervals[pre][1]){
                    pre = i;//保存下来小的
                }
                //结果+1
                result ++;
            }else{//表示没有交集，那么直接将保留区间index的变量pre更新为i
                pre = i;
            }
        }

        return result;
    }
};

763. 划分字母区间（C++贪心算法实现）

class Solution {
public:
    vector<int> partitionLabels(string s) {
        //一共有27个英文字母
        int hash[27] = {0};
        for(int i = 0;i < s.size();i++){
            hash[s[i] - 'a'] = i;
        }

        //结果返回数组
        vector<int> result;
        int start = 0;
        int end = 0;

        for(int i = 0;i < s.size();i++){
            //更新end下标
            end = max(end, hash[s[i] - 'a']);
            if(i == end){
                //加入包含当前字母的区间长度
                result.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return result;
    }
};

56. 合并区间（C++贪心算法实现）

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        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);

        //如果当前区间的左边界小于上一个区间的右边界，那么合并两个区间同时，更新left和right
        int left = intervals[0][0];
        int right = intervals[0][1];

        //定义的结果数组
        vector<vector<int>> result;
        result.push_back(intervals[0]);

        //从index=1开始遍历
        for(int i = 1;i < intervals.size();i++){
            if(intervals[i][0] <= right){
                vector<int> tmp;
                tmp.push_back(left);
                tmp.push_back(max(right, intervals[i][1]));
                result.pop_back();//弹出上一个区间
                result.push_back(tmp);
                //更新right边界
                right = max(right, intervals[i][1]);
            }else{//如果当前的left大于等于上一个的右边界，那么直接加入即可，然后更新
                result.push_back(intervals[i]);
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }

        return result;

    }
};

738. 单调递增的数字（C++贪心算法实现）

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //思路：将数字转换为字符串，然后判断strNum[i - 1]是否大于strNum[i]，如果是，
        //需要将strNum[i - 1] --;同时将strNum[i]替换为9
        string strNum = to_string(n);

        int flag = strNum.size();

        //从后向前遍历
        for(int i = strNum.size() - 1;i > 0;i--){
            if(strNum[i - 1] > strNum[i]){
                strNum[i - 1]--;
                flag = i;
            }
        }

        // 从flag开始，全部设置为9
        for(int i = flag;i < strNum.size();i++){
            strNum[i] = '9';
        }

        return stoi(strNum);
    }
};

（困难） 968. 监控二叉树（C++贪心算法实现）

/**
 * 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 = 0;
    
    //遍历二叉树，按照从下往上的顺序进行
    int traversal(TreeNode* curr){
        // 空结点，该结点有覆盖
        if(curr == nullptr){
            return 2;//返回2（状态2表示该结点为空结点且有覆盖）
        }

        //得到left结点和right结点
        int left = traversal(curr->left);//左结点
        int right = traversal(curr->right);//右结点

        //对中节点情况的处理
        //情况1：左右节点都有覆盖
        if(left == 2 && right == 2){
            return 0;//表示当前父结点
        }

        //情况2分为如下几种：
        //left == 0 && right == 0，左右节点无覆盖
        //left == 1 && right == 0，左结点有摄像头，右结点无覆盖
        //left == 0 && right == 1，左节点无覆盖，右结点有摄像头
        //left == 0 && right == 2，左结点无覆盖，右结点有覆盖
        //left == 2 && right == 0，左结点有覆盖，右结点无覆盖
        if(left == 0 || right == 0){
            result++;//表示当左右结点至少有一个结点无覆盖时，在中结点增加摄像头
            return 1;//表示增加摄像头
        }


        //情况3分为如下几种：
        //left == 1 && right == 2，左节点有摄像头，右结点有覆盖
        //left == 2 && right == 1，左结点有覆盖，右结点有摄像头
        //left == 1 && right == 1，左右节点均有摄像头
        if(left == 1 || right == 1){
            return 2;//那么left和right的父亲结点设置为2，表示有覆盖
        }

        return -1;
    }


    int minCameraCover(TreeNode* root) {
        result = 0;//初始化结果为0

        //表示无覆盖
        if(traversal(root) == 0){
            result ++;
        }

        return result;
    }
};