自学内容网 自学内容网

贪心系列专题篇二

增减字符串匹配

题目

思路

贪心策略:对于[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))


原文地址:https://blog.csdn.net/wmh_1234567/article/details/140408621

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