代码随想录算法训练营第三十天 | leetcode：单调递增的数字,贪心算法总结
1 / 0 / 创建于 11个月前 /
_zzh 的个人博客
738. 单调递增的数字
注意的地方
- int类型使用strval(n)转换为string类型str后，使用数组方式获取str[i],不能使用自增自减操作str[i]++ , str[i]–，以及 str[i] -= str[i], str[i] += str[i]；
- 使用字符串处理后，返回需要intval($str)转回int型，否则会出现返回“09”的情况，导致解答错误。
- 99这种相等的数也属于单调递增
解题方法
原理：从后往前遍历，如果遇到不是单调递增的数，则把前一位数（i-1） - 1操作(例如：90，变成80),同时标记i的位置，把i及之后的数字，都赋值为9。最后变成89。
- 从后往前遍历字符串，如果str[i-1] > str[i]（非单调递增）, 则把str[i-1] - 1, 同时使用flag标记当前处理位置i。
- 从flag位置开始处理字符串，把flag及之后的数字都赋值为9。
复杂度
时间复杂度
O(n)
空间复杂度
O(n)
code
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function monotoneIncreasingDigits($n) {
//转换字符串
$str = strval($n);
$flag = $len = strlen($str);
for($i = $len - 1; $i > 0; $i--){
//判断非递增
if($str[$i-1] > $str[$i]){
//处理i-1
$str[$i-1] = $str[$i-1] - 1;
//flag标记当前位置i
$flag = $i;
}
}
//处理flag及之后的数字都赋值为9
for($i = $flag; $i < $len; $i++){
$str[$i] = "9";
}
//转换为int返回
return intval($str);
}
}贪心算法的一些总结
- 贪心算法简单程度题型的解题核心往往就是生活常识，难点在于怎么把我们的常识应用到程序里面，如何把过程用程序模拟出来。例如：分发饼干，柠檬水找零，甚至是加油站，这些不考虑程序的情况下，就是常识问题。
- 也有很多题目不那么“常识”。解法往往很妙，比如摆动序列，把摆动模拟成上坡下坡，取头尾+上下顶峰的操作；两个维度权衡问题：分发糖果，根据身高重建队列，这种问题第一眼看上去非常难处理，但是遵循一边处理完再处理另一边的原则，就会发现不仅思路清晰，困难题目也不过如此。还有就是重叠区间：用最少数量的箭引爆气球，划分字母区间，合并区间，无重叠区间，这类题目是我觉得贪心算法里唯一算是有套路的题型，基本都是先排序，在判断重叠区间，更新左边界或者右边界，处理重叠的逻辑或者不重叠的逻辑。主要难点就是在更新边界的处理。但是以上题目往往比较难想出这种解法，但是一旦知道解法后，都会忍不住发出感叹：“妙啊！”
- 相对的对个人而言，贪心算法也有很难理解的题型：跳跃游戏。跳跃游戏类的题型，哪怕看了解题过程，也会觉得很抽象。至今都还是有点云里雾里。
- 具体什么叫贪心，卡哥的总结：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号