【贪心算法】day7

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

也可以点击下面连接，学习其他算法

55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/description/

个人解

思路：

• 和上一题一样

屎山代码：

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

时间复杂度：$O(n)$
空间复杂度：$O(1)$

134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/description/

优质解

思路：

• 题目要求：按顺序绕环路行驶一周
• 暴力解法：枚举所有起点，从起点开始遍历一遍
• 贪心优化：如果从点i开始出发，走了step步以后，失败了，则代表[i, i + step]区间的点都不能作为起点（因为失败一定是下一步不够油了，区间内的所有点作为起点的时候原始油为0，更不够）

代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0; i < n; i++)
        {
            int step = 0;
            int res = 0;
            for(; step < n; step++)
            {
                int nxt = (i + step) % n; // 防止越界
                res = res + gas[nxt] - cost[nxt];
                if(res < 0)
                {
                    i = i + step; // 贪心优化
                    break;
                }
            }
            if(res >= 0) return i;
        }
        return -1;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

738. 单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/

优质解

思路：

• 暴力解法：从 n 开始枚举到 0，然后判断数字是否是递增的，如果是：即为得到的“最大”递增数
• 贪心策略（对于"原数"）：
  • 如果高位单调递增，则不去修改（因为我们是要找“最大数”，修改行为肯定是"该位减小"，极有可能破坏递增）
  • 当发现第一个“不递增”的位置时，无法通过增大后一位来实现“递增”（因为这时候比原来的数大了），只能降低本位，然后把后面的数全填9即可
    • 但是，如果修改位置的前一个位置与本位相同，修改后会破坏递增，此时，需要递归的往前调整（即：其实是修改这些连续相同数中的“第一个”数）
• （判断是否“递增”）技巧：
  • 转换成字符串，然后双指针
  • 用%10 和 /10

屎山代码：

class Solution {
public:
    int monotoneIncreasingDigits(int m) {
        string s = to_string(m);
        int n = s.size();
        int i = 0;
        while(i < n - 1 && s[i] <= s[i + 1]) i++;
        if(i == n - 1) return m; // 特殊情况，不需要修改
        while(i - 1 >= 0 && s[i - 1] == s[i]) i--;
        s[i]--;
        for(int j = i + 1; j < n; j++) s[j]  = '9';
        return stoi(s);
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！