Skip to main content

8-贪心算法

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

455. 分发饼干​

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int child = 0, si = 0;
        while(child < g.size() && si < s.size())
        {
            if(s[si] >= g[child])
            {
                si++;
                child++;
            }
            else si++;
        }
        return child;
    }
};

376. 摆动序列​

此题可当作搜索题，满足条件+1即可，不要想复杂了

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2) return nums.size();
        int cur = 1, res = 1 , pre = 0;
        for(int i = 1; i < nums.size();i++)
        {
            if((nums[i] - nums[i - 1] != 0) && ((nums[i] - nums[i - 1]) * pre) <= 0)cur++;
            pre = nums[i] - nums[i - 1] == 0 ? pre :(nums[i] - nums[i - 1]) / abs(nums[i] - nums[i - 1]);
            res = max(cur,res);
        }
        return res;
    }
};

53. 最大子数组和​

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

122. 买卖股票的最佳时机 II​

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i = 1; i < prices.size();i++)
        {
            if(prices[i] - prices[i-1] > 0) res += prices[i] - prices[i-1];
        }
        return res;
    }
};

55. 跳跃游戏​

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

45. 跳跃游戏 II​

class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0 , cur = 0;
        while(cur < nums.size() - 1)
        {
            int add = 1 , mu = 0;
            for(int i = 1 ; i <= nums[cur];i++)
            {
                if(cur + i >= nums.size() - 1) return step + 1;
                if(nums[cur + i] + i >= mu)
                {
                    mu = nums[cur + i] + i;
                    add = i;
                }
            }
            step++;
            cur += add;
        }
        return step;
    }
};

1005. K 次取反后最大化的数组和​

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int cur = 0 ,mins = INT_MAX;
        while(cur < nums.size() && k)
        {
            if(nums[cur] < 0)
            {
                nums[cur] = -nums[cur];
                k--;
                mins = min(nums[cur],mins);
            }
            else if(nums[cur] == 0) 
            {
                k = 0;
                break;
            }
            else 
            {
                mins = min(nums[cur],mins);
                break;
            }
            cur++;
        }
        mins = k % 2 == 0 ? 0: -2 * mins;
        return accumulate(nums.begin(),nums.end(),0) + mins;
    }
};

134. 加油站​

可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cur_oil = 0 , all_oil = 0 , start = 0;

        for(int i = 0; i < gas.size();i++)
        {
            cur_oil += gas[i] - cost[i];
            all_oil += gas[i] - cost[i];
            if(cur_oil < 0)
            {
                cur_oil = 0;
                start = i + 1;
            }
        }
        if(all_oil < 0) return -1;
        return start;
    }
};

135. 分发糖果​

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candys(ratings.size() , 1);
        for(int i = 1 ; i < ratings.size() ;i++)
        {
            if(ratings[i] > ratings[i - 1]) candys[i] = candys[i - 1] + 1;
        }
        for(int i = ratings.size() - 1 ; i > 0 ;i--)
        {
            candys[i - 1] = ratings[i - 1] > ratings[i] ? max(candys[i] + 1,candys[i - 1]): candys[i - 1];
        }
        return accumulate(candys.begin(),candys.end(),0);
    }
};

860. 柠檬水找零​

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0 , ten = 0;
        for(int x : bills)
        {
            if(x == 5) five++;
            else if(x == 10) 
            {
                ten++;
                if(five) five--;
                else return false;
            }
            else
            {
                if(ten && five)
                {
                    ten--;
                    five--;
                }
                else if(five >= 3) five -= 3;
                else return false;
            }
        }
        return true;
    }
};

406. 根据身高重建队列​

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

那么只需要按照k为下标重新插入队列就可以了

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[&](const vector<int> &a,const vector<int> &b){
            if(a[0] != b[0]) return a[0] > b[0];
            else return a[1] < b[1];
        });
        vector<vector<int>> res;
        for(auto x:people)
        {
            res.insert(res.begin() + x[1],x);
        }
        return res;
    }
};

646. 最长数对链​

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),[](const vector<int> &a,const vector<int> &b){
            if(a[1] != b[1]) return a[1] < b[1];
            else return a[0] < b[0];
        });
        int len = 1;
        for(int i = 1; i < pairs.size();i++)
        {
            if(pairs[i][0] > pairs[i - 1][1]) len++;
            else pairs[i][1] = pairs[i - 1][1];
        }
        return len;
    }
};

452. 用最少数量的箭引爆气球​

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),[&](const vector<int> &a,const vector<int> &b){
            if(a[0] != b[0]) return a[0] < b[0];
            else return a[1] < b[1];
        });
        int cnt = 1;
        for(int i = 1; i < points.size();i++)
        {
            if(points[i][0] > points[i - 1][1]) cnt++;
            else{
                points[i][1] = min(points[i - 1][1],points[i][1]);
            }
        }
        return cnt;
    }
};

435. 无重叠区间​

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector<int> &a,const vector<int> &b){
            if(a[1] != b[1]) return a[1] < b[1];
            else return a[0] < b[0];
        });
        int len = 0;
        for(int i = 1; i < intervals.size();i++)
        {
            if(intervals[i][0] < intervals[i - 1][1]) 
            {
                len++;
                intervals[i][1] = intervals[i - 1][1];
            }
        }
        return len;
    }
};

763. 划分字母区间​

这道题关键就是将找到各个字母最后出现的位置，判断当前max是不是在最后出现的位置内

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        unordered_map<char , int> umap;
        for(int i = 0; i < s.size();i++) umap[s[i]] = i;
        int maxs = 0,pre = -1;
        for(int i = 0; i < s.size();i++)
        {
            maxs = max(umap[s[i]],maxs);
            if(maxs == i) 
            {
                res.push_back(i - pre);
                pre = i;
            }
        }
        return res;
    }
};

56. 合并区间​

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(),intervals.end(),[&](const vector<int> &a,const vector<int> &b){
            if(a[0] != b[0]) return a[0] < b[0];
            else return a[1] < b[1];
        });
        intervals.push_back({INT_MAX,INT_MAX});
        for(int i = 1;i < intervals.size();i++)
        {
            if(intervals[i][0] > intervals[i - 1][1])res.push_back(intervals[i - 1]);
            else{
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = max(intervals[i - 1][1],intervals[i][1]);
            }
        }
        return res;
    }
};

57. 插入区间​

同56

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end(),[&](const vector<int> &a , const vector<int> &b){
            if(a[0] == b[0]) return a[1] < b[1];
            return a[0] < b[0];
        });
        intervals.push_back({INT_MAX,INT_MAX});
        vector<vector<int>> res;
        for(int i = 1 ; i < intervals.size();i++)
        {
            if(intervals[i][0] > intervals[i - 1][1]) res.push_back(intervals[i - 1]);
            else 
            {
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = max(intervals[i - 1][1],intervals[i][1]);
            }
        }
        return res;
    }
};

228. 汇总区间​

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        if(nums.size() < 1) return {};
        vector<string> res;
        int pre = nums[0],start = nums[0];
        for(int i = 1; i < nums.size();i++)
        {
            if(pre + 1 != nums[i])
            {
                if(pre == start) res.push_back(to_string(start));
                else res.push_back(to_string(start) + "->" + to_string(pre));
                start = nums[i];
            }
            pre = nums[i];
        }
        if(pre == start) res.push_back(to_string(start));
        else res.push_back(to_string(start) + "->" + to_string(pre));
        return res;
    }
};

986. 区间列表的交集​

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        function<vector<int>(int,int )> mix = [&](int i,int j)->vector<int> {
            int left = max(firstList[i][0],secondList[j][0]);
            int right = min(firstList[i][1],secondList[j][1]);
            if(right < left) return {};
            return {left,right};
        };
        vector<vector<int>> res;
        int i = 0, j = 0;
        while(i < firstList.size() && j < secondList.size())
        {
            vector<int> r = mix(i,j);
            if(r.empty()) firstList[i][0] < secondList[j][0] ? i++ : j++;
            else
            {
                res.emplace_back(r);
                if(firstList[i][1] == r[1])
                {
                    i++;
                    secondList[j][0] = r[1];
                }
                else{
                    j++;
                    firstList[i][0] = r[1];
                }
            }
        }
        return res;
    }
};

1288. 删除被覆盖区间​

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector<int> &a,const vector<int> &b){
            if(a[0] == b[0]) return a[1] > b[1];//区间长的优先在前
            return a[0] < b[0];
        });
        int cnt = 0;
        for(int i = 1; i < intervals.size();i++)
        {
            if(intervals[i][0] >= intervals[i - 1][0] && intervals[i][1] <= intervals[i - 1][1])
            {
                cnt++;
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = intervals[i - 1][1];
            }
            else if(intervals[i][0] <= intervals[i - 1][1])
            {
                intervals[i][0] = intervals[i - 1][0];
            }
        }
        return intervals.size() - cnt;
    }
};

738. 单调递增的数字​

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int cur = s.size() - 1;
        while(cur > 0)
        {
            if(s[cur - 1] > s[cur]) 
            {
                s[cur] = '9';
                s[cur - 1]--;
            }
            cur--;
        }
        cur = 1;
        while(cur < s.size())
        {
            if(s[cur - 1] > s[cur])  s[cur] = '9';
            cur++;
        }
        return stoi(s);
    }
};

968. 监控二叉树​

class Solution {
    int count = 0;
    int Camera(TreeNode* root)
    {
        if(!root) return 1;
        int left = Camera(root->left);
        int right = Camera(root->right);
        if(left == 2 || right == 2) 
        {
            count++;
            return 0;
        }
        else if(left == 0 || right == 0) return 1;
        else return 2;
    }
public:
    int minCameraCover(TreeNode* root) {
        // 0 - 安装摄像头  1 - 已经覆盖  2 - 未被覆盖
        //叶子节点默认为 2
        int re = Camera(root);
        if(re == 2) count++;
        return count;
    }
};

1221. 分割平衡字符串​

class Solution {
public:
    int balancedStringSplit(string s) {
        int count = 0;
        int left = 0 , right = 0;
        for(char x: s) 
        {
            if(x == 'R') right++;
            else left++;
            if(right == left) count++;
        }
        return count;
    }
};

605. 种花问题​

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        int count = 0;
        for(int i = 1; i < flowerbed.size() - 1;i++)
        {
            if(flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0)
            {
                count++;
                flowerbed[i] = 1;
            }
        }
        return count >= n;
    }
};

665. 非递减数列​

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        nums.insert(nums.begin(),INT_MIN);
        nums.push_back(INT_MAX);
        int rep = 0, pep = 0;
        for(int i = 2; i < nums.size() - 1;i++)
        {
            if(nums[i] < nums[i - 1]) 
            {
                count++;
                if(nums[i] >= nums[i - 2]) rep++;
                else if(nums[i + 1] >= nums[i - 1]) pep++;
            }
        }
        if(count == 0) return true;
        return count == 1 && (rep || pep);
    }
};

870. 优势洗牌​

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        int cur = 0;
        vector<bool> choosed(nums1.size(),false);
    
        vector<int> res;
        for(int i = 0; i < nums2.size();i++)
        {
            auto start = upper_bound(nums1.begin() + cur,nums1.end(),nums2[i]);
            if(start != nums1.end())
            {
                int i = start - nums1.begin();
                while(i < nums2.size() && choosed[i]) i++;
                if(i < nums2.size())
                {
                    choosed[i] = true;
                    res.push_back(nums1[i]);
                    continue;
                }
            }
            while(choosed[cur]) cur++;
            res.push_back(nums1[cur]);
            choosed[cur++] = true;

        }
        return res;
    }
};

1642. 可以到达的最远建筑​

class Solution {
    //优先队列（小顶堆）维护 ladders 个最大的 gap 使用梯子，其他较小的出堆的 gap 使用 bricks，如果 bricks 用完了返回当前下标；否则能到达最远下标 n - 1。
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int n = heights.size();
        priority_queue<int,vector<int>,greater<int>> que;
        for(int i = 0 ; i < n - 1;i++)
        {
            if(heights[i + 1] > heights[i])
            {
                que.push(heights[i + 1] - heights[i]);
                if(que.size() > ladders)
                {
                    bricks -= que.top();
                    que.pop();
                    if(bricks < 0) return i;
                }
            }
        }
        return n - 1;
    }
};

976. 三角形的最大周长​

class Solution {
    //固定 C 边，那么AB两个边最长就是前面不大于C的两个数
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = A.size() - 1; i >= 2; --i) {
            if (A[i - 2] + A[i - 1] > A[i]) {
                return A[i - 2] + A[i - 1] + A[i];
            }
        }
        return 0;
    }
};