贪心系列专题篇二

增减字符串匹配

题目

思路

贪心策略：对于[0,n]，当遇到“I”时，把所剩的数中最小的拿来使用；

                                    当遇到“D”时，把所剩的数中最大的拿来使用，最后还剩一个数，放末尾。

代码

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n=s.size();
        vector<int> ret;
        int left=0,right=n;
        for(int i=0;i<n;i++){
            if(s[i]=='I') ret.push_back(left++);
            else ret.push_back(right--);
        }
        ret.push_back(left);
        return ret;
    }
};

最优除法

题目

思路

对于一个数组，例如有a,b,c,d,e,f，由于所有的数都是大于2的，依题意，如何加括号使表达式的值最大？即：把除了前两个数之外的其他数都调整到分子的位置就可以了，即：

贪心策略

当只有一个数，返回；当有两个数，返回二者对应格式；

当数的个数大于2个，把前括号加到第二个数前面，后括号加到最后一个数的后面。

代码

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n=nums.size();
        string s;
        if(n==1){
            s+=to_string(nums[0]);
        }
        else if(n==2){
            s+=to_string(nums[0]);
            s+='/';
            s+=to_string(nums[1]);
        }
        else{
            s+=to_string(nums[0]);
            s+="/(";
            for(int i=1;i<n-1;i++){
                s+=to_string(nums[i]);
                s+='/';
            }
            s+=to_string(nums[n-1]);
            s+=")";
        }
        return s;
    }
};

跳跃游戏II

题目

思路

下面将采用看似是贪心，但实则也不太算是贪心来解决，或者也可以说是类似于层序遍历。

当遇到某一步和后一步有重叠部分时，把重叠的那一部分归为步数较小的那一步的范围。

使用两个指针来指向某一步的最左边和最右边，另外使用一个变量maxpos记录当前步的范围内最远能走到什么位置。

指针更新规则：left=right+1，right=maxpos。

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int left=0,right=0,maxpos=0,n=nums.size();
        int ret=0;
        while(left<=right){//保险的写法，以防到不到末尾
            if(maxpos>=n-1)
                return ret;
            for(int i=left;i<=right;i++){
                maxpos=max(maxpos,nums[i]+i);
            }
            left=right+1;
            right=maxpos;
            ret++;
        }
        return -1;
    }
};

跳跃游戏

题目

思路

这道题其实和上一道题《跳跃游戏II》的解法是一样的，只不过是问题问的不一样。

解法如下：

下面将采用看似是贪心，但实则也不太算是贪心来解决，或者也可以说是类似于层序遍历。

当遇到某一步和后一步有重叠部分时，把重叠的那一部分归为步数较小的那一步的范围。

使用两个指针来指向某一步的最左边和最右边，另外使用一个变量maxpos记录当前步的范围内最远能走到什么位置。

指针更新规则：left=right+1，right=maxpos。

代码

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

加油站

题目

思路

由于有两个数组，其实我们关注的并不是两个数组中元素是大还是小，关注的而是两个数组对应位置处元素的差值大小，以示例一为例：

如果我们遍历整个数组，然后以数大于等于0的位置为开始，往后绕环走，直到走一圈或者不能够走不到一圈为止，这样的话，时间复杂度是O(N^2)，会超时的，所以我们需要进行优化，遍历整个数组显然是必不可少的，那么优化的方法就是使用“滑动窗口”。

贪心策略

当我们找到元素大于等于0的位置，往后绕环走n-1步，如果不支持走n-1步，那么我们就从不支持走n-1步的位置的下一个地方开始走，因为如果按普通理解，我们是会从开始位置的下一个位置开始走，但是这样是无意义的，因为开始位置的值是大于等于0的，这样都不支持走n-1步，更别说减去这个大于等于0的数了，这样的话时间复杂度是0(N），显然是可行的。

我们把关注点放在diff数组上

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        vector<int> diff(n);
        for(int i=0;i<n;i++)
            diff[i]=gas[i]-cost[i];
        for(int i=0;i<n;i++){
            if(diff[i]<0) continue;
            else{
                long long tmp=diff[i];
                for(int k=1;k<n;k++){
                    if(tmp>=0){
                        tmp+=diff[(i+k)%n];
                    }
                    if(tmp<0){
                        i+=k;
                        break;
                    }
                }
                if(tmp>=0) return i;
            }
        }
        return -1;
    }
};//贪心（时间复杂度O(N)）