【贪心算法】day7
📝前言说明：
- 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行其他贪心算法题目的学习
| 点击链接 | 开始学习 |
|---|---|
| 贪心day1 | 贪心day2 |
| 贪心day3 | 贪心day4 |
| 贪心day5 | 贪心day6 |
| 贪心day7 | 贪心day8 |
| 贪心day9 | 贪心day10 |
也可以点击下面连接，学习其他算法
| 点击链接 | 开始学习 |
|---|---|
| 优选专题 | 动态规划 |
| 递归、搜索与回溯 | 贪心算法 |
题单获取→ 【贪心算法】题单汇总
题目
55. 跳跃游戏
题目链接：https://leetcode.cn/problems/jump-game/description/
个人解
思路：
- 和上一题一样
屎山代码：
classSolution{public:boolcanJump(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)returnfalse;returntrue;}};时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
134. 加油站
题目链接：https://leetcode.cn/problems/gas-station/description/
优质解
思路：
- 题目要求：按顺序绕环路行驶一周
- 暴力解法：枚举所有起点，从起点开始遍历一遍
- 贪心优化：如果从点
i开始出发，走了step步以后，失败了，则代表[i, i + step]区间的点都不能作为起点（因为失败一定是下一步不够油了，区间内的所有点作为起点的时候原始油为0，更不够）
代码：
classSolution{public:intcanCompleteCircuit(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(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
738. 单调递增的数字
题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/
优质解
思路：
- 暴力解法：从
n开始枚举到0，然后判断数字是否是递增的，如果是：即为得到的“最大”递增数 - 贪心策略（对于"原数"）：
- 如果高位单调递增，则不去修改（因为我们是要找“最大数”，修改行为肯定是"该位减小"，极有可能破坏递增）
- 当发现第一个“不递增”的位置时，无法通过增大后一位来实现“递增”（因为这时候比原来的数大了），只能降低本位，然后把后面的数全填
9即可- 但是，如果修改位置的前一个位置与本位相同，修改后会破坏递增，此时，需要递归的往前调整（即：其实是修改这些连续相同数中的“第一个”数）
- （判断是否“递增”）技巧：
- 转换成字符串，然后双指针
- 用
%10和/10
屎山代码：
classSolution{public:intmonotoneIncreasingDigits(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';returnstoi(s);}};时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
