【Day25 LeetCode】贪心Ⅲ

一、贪心Ⅲ

1、加油站 134

这道题直接想法是采用二重循环暴力搜索，简单粗暴但是会超时，是因为以每个点为起点最坏的情况可能都要遍历完全部的序列，有大量重复的操作，那有没有优化的地方呢？有一个结论：如果以$i$位置出发最远可达$j$位置，那么在在这段区间里的任意一点出发都不可能达到比$j$位置更远的地方。反证法可以得出。可以通过这个结论避免大量重复搜索，每个位置只会经过一次。
代码如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size(), s = 0;
        for(int i=0; i<n; ++i){
            s = gas[i] - cost[i];
            int j = (i + 1) % n;
            while(s >= 0 && i != j){
                s += gas[j] - cost[j];
                j = (j + 1) % n;
            }
            if(j==i && s >= 0)
                return i;
            if(j <= i)
                return -1;
            i = j - 1;
        }
        return -1;
    }
};

2、分发糖果 135

分发糖果需要满足其左右孩子的评分高低，直接想着满足两边的条件比较困难，可以先满足一边的条件，在此基础上再满足另一边的条件。
先满足与左边孩子的条件，从前往后看，如果当前孩子评分高于左孩子，则当前孩子的糖果是左孩子的糖果数加1，如果不高于，则给最少的糖果，1个。
在此基础上，再去从后往前看每个孩子的右孩子，如果当前孩子评分高于右孩子，则 当前孩子糖果是在已有糖果 和 右孩子糖果+1之间取最大值，这样可以满足左右孩子两个条件。
代码如下：

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

3、柠檬水找零 860

这题逻辑比较清楚，10美元只能用5美元找零，20美元可以用3个5美元 或者 1个5美元1个10美元找零。但10美元只能用于20美元找零，5美元可用于10、20美元找零，用处更多，所以应该优先使用10美元5美元去找零20美元，如果没有10美元再全用5美元找零。

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int num_5 = 0, num_10 = 0; // 5/10美元数量
        for(int bill : bills){
            switch(bill){
                case 5:
                    num_5++;
                    break;
                case 10:{
                    num_5--;
                    num_10++;
                    break;
                }
                case 20:{
                    // 优先使用10美元
                    if(num_10 > 0)
                        num_10--;
                    else
                        num_5 -= 2;
                    num_5--;
                }
            }
            if(num_10 < 0 || num_5 < 0)
                return false;
        }
        return true;
    }
};

4、根据身高重建队列 406

有两个元素，一个是身高h，一个是前面不小于当前高度的人数k。可以先按考虑按身高h排序，确定之后再按 k进行插入

class Solution {
    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];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> ans;
        for(auto p : people)
            ans.insert(ans.begin()+p[1], p);
        return ans;
    }
};

二、写在后面

加油站这题比较巧妙，如果能想到那个结论就很容易进行优化。分发糖果和根据身高重建队列这题主要是当需要满足两边条件时，同时兼顾两边处理起来麻烦， 可以先处理一边，再处理另一边。

原文地址：https://blog.csdn.net/H2020fighting/article/details/145320690

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！