【贪心算法】贪心算法五

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.跳跃游戏 II

题目链接： 45. 跳跃游戏 II

题目分析：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处。这句话特别重要的地方就是 任意。

下面举个例子，刚开始在0号位置最大跳跃长度是3，可以跳到下标3的位置。

你可以跳转到任意 nums[i + j] 处，这句话意思，nums[i]里面存的3是最大跳跃长度，你可以选择跳3步、跳2步、跳1步。

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

算法原理：

1. 贪心(X)

刚开始处于0好位置，这里有一个最大跳跃长度，那每次跳跃的时候就非常贪心的跳最长跳跃长度。但是这种贪心是错的。

2. 动态规划

这个模型无非就是从左往右的一个模型，其实就是动规里面非常常规的线性dp问题。

1.状态表示

dp[i] 表示：从 0 位置开始，到达 i 位置的时候最小跳跃次数

2.状态转移方程

根据最近一步划分情况：

能够到 i 位置的前提是要满足 nums[j] + j >= i，说明能够从 j 位置到达 i 位置，那到达 j 位置的最小跳跃次数 在 加上 从 j 到 i 这一跳跃次，就是到达 i 位置最小跳跃次数，j的位置有很多，因此外面要求dp[i]的最小值。

3.初始化

dp[0] = 0 初始就在0位置，然后要取dp[i]的最小值，因此0位置之后可以初始化 INT_MAX

4.填表顺序

从左往右

5.返回值

dp[i] 表示：从 0 位置开始，到达 i 位置的时候最小跳跃次数，我们要的是到底n-1位置的最小跳跃次数，因此返回dp[n-1]

class Solution {
public:
    int jump(vector<int>& nums) {

        // 动态规划
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i < n; ++i)
            for(int j = 0; j < i; ++j)
                if(nums[j] + j >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
        return dp[n - 1];
    }
};

虽然可以通过，但是实际复杂度是O(N^2)

3. 类似于层序遍历的过程

刚开始在2这个位置，此时起跳可以跳到3和1的位置。2这里可以表示第1次起跳的位置，3和1表示第2次起跳的位置。

通过第2次起跳的位置，我们可以得到第3从起跳的位置，然后把重叠的删除，这里其实也有一点小贪心，如果能从第2次的1起跳，那为什么还要从第3次重叠的1起跳呢？跳跃次数更多了。所以只有1和4是第三次起跳的位置。

同理从第3次起跳位置，我们可以得到第4次起跳位置，

你会发现这里类似于层序遍历，每次都能知道起跳的左端点和右端点，然后遍历这一层的时候，又能找到下一层的左端点和右端点。只要发现更新出来下一次起跳位置能够覆盖到n-1位置的时候就停止，因为次数已经可以跳到最后一个位置了

如何实现呢？
我们仅需搞两个指针，left指向当前起跳的左端点，right指向当前起跳的右端点，把这个区间遍历一遍就可以找到下一个起跳区间，其中找左端点很好找就是right + 1，找右端点就是在遍历的过程中，拿着nums[i] + i 找到其中的最大值就是右端点。

在这个遍历过程中，我们仅需遍历一次就行了，所以时间复杂度是O(N)

class Solution {
public:
    int jump(vector<int>& nums) {
    
        int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
        while(left <= right)// 保险的写法，以防跳不到 n - 1 的位置
        {
            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;// 跳不到的情况
    }
};

2.跳跃游戏

题目链接： 55. 跳跃游戏

题目分析：

这道题和上面几乎一模一样，无非上面问的是跳到最后一个位置最小跳跃次数，这道题问的是能否跳到最后一个位置。

算法原理：

完全参考上面的解法3：利用层序遍历的过程

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;

    }
};

3.加油站

题目链接： 134. 加油站

题目分析：

选择某个加油站为出发点，环绕一周看是否能回到出发点。如果可以就返回对应的下标，不能就返回-1。

初始时油箱是空的，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i]，油箱容量是无限的。

假设从3位置出发，刚开始油箱为空，此时可以补充1升汽油，但是需要3升汽油才能到下一个位置。所以这个位置不可以，同理4和5都不可以。

可以从1位置出发 ，从这里可以补充4升汽油，仅需消耗1升就可以到下一个位置，到下一个位置还剩下3升

到2的位置，补充5升，现在共有8升，消耗2升，到下一个位置还有6升

然后补充1升，消耗3升，到下一个位置还剩4，在补充2升，消耗4升，到下一个位置还剩2升，在补充3升，消耗5升，到出发点正好剩下0，可以到达，返回3。

算法原理：

解法一：暴力解法 -> 枚举

首先可以想到一个优化，仅需考虑g和c的差就可以了，比如第一个位置会加1升油，消耗3升油，它们的差就是从这个加油站获得的净收益。如果从负开始走绝对是走不到下一个位置的，所以肯定会选择净收益为正的作为出发点。

我们这道题其实特别像是一道模拟的题，任意枚举一个位置看看从这个位置能不能绕一圈会回来就可以。如果不能就去枚举下一个位置。

所以我们的暴力策略就很简单：

1. 依次枚举所有的起点
2. 从起点开始，模拟一遍加油的流程即可

虽然策略很简单，但是要注意这里是有环的，所以写代码的时候要考虑如何从最后一个位置回到0位置。

我们的贪心就是根据暴力优化来的，所以先搞定暴力的代码。然后优化的时候仅需加一句代码，就能将时间复杂度从O(N^2)变成O(N)

如何实现暴力的代码？

这里我们主要考虑就是如何从最后一个位置回到第一个位置，其实这里两层for循环就可以搞定，我们创建一个变量step，用这个变量表示从 i 往后走了多少步，step变化是从 0 ~ n - 1。然后 （i + step）% n (数组大小) 就可以从最后一个位置回到第一个位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        for(int i = 0; i < n; ++i)// 依次枚举所有的起点
        {
            int rest = 0;// 标记一下净收益
            int step = 0;
            for(; step < n; ++step)// 枚举往后走的步数
            {
                int index = (i + step) % n;// 求出走 step 步之后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) break;
            }
            if(rest >= 0) return i;
        }
        return -1;       
    }
};

解法二：优化 -> 找规律（贪心）

diff表示g-c的差，我们的暴力解法是依次固定一个位置为起点，从这个起点开始模拟加油流程，其实就是把净收益加一下。

如果发现从a加到f小于0了，说明从f这个位置开始就不能往后走了，所以从a为起来最多能到f这个位置。这里有一个等式。

我们的暴力是枚举下一个起点然后在走。然后我们这里也有个不等式，

我们要想从a走到b，一定是a>=0的，从a加到f < 0，现在第二个不等式又少了a，那更是< 0

同理从c为起点也是越不过f的，a + b >= 0才能到c，等式少了a+b，那更小于0

所以说发现有一个起点点都跑不到某个位置，那中间的都不用在考虑了，不用在枚举了。直接让 i 指针更新到 五角星 后面的一个位置，也就是 i = i + step + 1

我们最差会遍历数组两遍，假设还是以a为起点，发现到h走不到了，下一个位置就是i，最差我们绕回去在遍历一遍再走到h位置，相当于遍历了数组两遍，然后接下来更新 i 的时候 是 i + step + 1 此时就已经越界了。所以最差遍历数组两遍，时间复杂度O(N)

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        for(int i = 0; i < n; ++i)// 依次枚举所有的起点
        {
            int rest = 0;// 标记一下净收益
            int step = 0;
            for(; step < n; ++step)// 枚举往后走的步数
            {
                int index = (i + step) % n;// 求出走 step 步之后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) break;
            }
            if(rest >= 0) return i;
            i = i + step;//优化
        }
        return -1;

        
    }
};

3.单调递增的数字

题目链接： 738. 单调递增的数字

题目分析：

算法原理：

解法一：暴力解法 -> 暴力枚举

不是给了我们一个n，然后让找到小于等于n的最大数字，且数字是单调递增的。
所以我们可以从n枚举到0，只要找到数字是单调递增的，就返回。因为我们是从大到小枚举所以这个数一定是小于等于n并且是最大的那个数。

1. 从大到小的顺序，枚举 [n，0] 区间内的数字
2. 判断数字是否是 “单调递增的”

这里最主要的就是判断一个数是单调递增的。肉眼很好判断，但是让计算机不好判断，这里我们有两个常用方法：

第一种方法：我们遇到有个数字的时候，如果想处理某一位的时候，最常用的方式就是将数字转化为字符串。

比如要找数字中的每一位，如果单看数字1234你很难找每一位，但是我们可以将1234 转化为 “1234”，此时就可以用指针来遍历每一位

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
    
        for(int i = n; i >= 0; --i)
        {
            string nums = to_string(i);
            int j = 0, m = nums.size();
            for(; j < m - 1; ++j)
            {
                if(nums[j] > nums[j + 1]) break;
            }
            if(j == m - 1) return i;
        }
        return -1;   
    }
};

第二种方法：% 10 ， / 10

prev记录之前%10得到的数字，cur记录/10之后然后当前%10得到的数字。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {

        for(int i = n; i >= 0; --i)
        {
            int prev = INT_MAX, cur = 0, num = i;
            while(num)
            {
                cur = num % 10;
                if(cur > prev) break;
                prev = cur;
                num /= 10;
            }
            if(num == 0) return i;
        }
        return -1;
    }
};

这两种方法都会超时！时间复杂度是O(nlogn)，O(logn)表示把数字中的每一位都提取出来时间复杂度是O(logn)

解法二：贪心（找规律）

假设有下面这样一个数，我们观察1-5是递增的，从5后面开始就是递减的。此时第一个贪心，如果前面的数是递增的我们会不会去修改它？肯定不会！修改高位势必会给高位某个数减小，影响太大了。

1. 如果高位单调递增的话，我们不去修改

从5之后开始下降，我们最终要想找一个单调递增的话，调整一下后面的数使它从5开始递增并且尽可能的大，但是这个想法是实现不了的，你是会让4变成5，但是整个数相比之前就变大了。所以这个策略不行，调整4367使它从5之后开始递增是实现不了的。原因就是后面数的变化受到5的限制。如何解除这个限制呢？让这个5减小1变成4，然后的数都变成9，绝对是最大递增的。

2. 从左往右，找到第一个递减的位置，使其减小1，后面的数全部修改成 9

但是这里还有个问题，比如下面这个数，5是重复的，从左到右扫描到最后一个5的位置，但是执行刚才的策略是让最后一个5减少1，后面数都变成9，但是不行啊，你让最后一个5变成4，这个数就不是一个递增的了。其实我们应该调整第一个5变成4，后面的数都变成9

2. 从左往右，找到第一个递减的位置，从这个位置向前推，推到相同区域的最左段使其减小1，后面的数全部修改成 9

class Solution {
public:
    int monotoneIncreasingDigits(int n) {

        string s = to_string(n);// 把数字转化成字符串

        int i = 0, m = s.size();
        // 找第⼀个递减的位置
        while(i + 1 < m && s[i] <= s[i + 1]) ++i;

        if(i + 1 == m) return n;// 判断⼀下特殊情况

        // 回推
        while(i - 1 >= 0 && s[i] == s[i - 1]) --i;

        s[i]--;
        for(int j = i + 1; j < m; ++j) s[j] = '9';
        return stoi(s);
        
    }
};

证明：

证明方法：反证法

假设贪心解是错误的，那必定会存在一个最优解，证明一下这个最优解是不存在的，那我们的贪心解就是最优的。

这里我们分开讨论，第一种贪心解得到的数和原数个数是匹配的，第二种个数不匹配。

先看第一种情况，假设贪心解不是最优解，那势必会存在一个最优解，最优解是严格大于贪心解并且是严格递增的。其次位数是一样的，贪心解位数都一样，最优解比贪心解大，位数肯定也是一样的。位数一样，从左扫描最优解肯定存在某一位是大于贪心解某一位的。

这里可以分为3个区域，递增区域，让原数减1区域，以及后面的区域。不过如果前两个区域都是一样的话，第三个区域肯定不存在比999还大的。因此我们只考虑前两个区域最优解的某个数大于贪心解

第一块区域，要么大于1、要么大于2、要么大于3，但是都是不存在的，因为这个数是单调递增的，最小的1333333都比原解还大了。

第二块区域，如果中间这个数比贪心解的这个数大最低就是4，但是也是不存在的，最优解也是一个递增的数如果这个是数4，后面即使全是4，最小的是1234444还比原数大，所以也是不存在的。

那后面的区域更别提了，不可能有大于999的数。所以说如果贪心解是错的，根本找不到一个最优解比贪心解大，所以说刚才的假设是错误的，因此我们的贪心解是正确的。

接下来我们看位数减少的情况，我们会发现位数减少的这个数正好是最大的减少位数中的最大数，你想找一个最优解比贪心解还大的情况那必定是6位数，如果是6位数还想保证比原数小，那这个数只能是1111111但是比原数大，因此这个最优解也是不存在的，所以我们的贪心就是最优的。都找不到一个最优解大于贪心解。