代码随想录算法训练营第三十六天 | LeetCode 738. 单调递增的数字、贪心算法总结

简介: 代码随想录算法训练营第三十六天 | LeetCode 738. 单调递增的数字、贪心算法总结

代码随想录算法训练营第三十六天 | LeetCode 738. 单调递增的数字、贪心算法总结

文章链接:单调递增的数字贪心算法总结

视频链接:单调递增的数字

1. LeetCode 738. 单调递增的数字

1.1 思路

  1. 本题的贪心思路是什么?举个例子 32,这不是一个单调递增的数字,那就要处理后再返回了,十位上的 3一定要-1,它如果不变的话,就无法处理,因为要返回一个<=32 的数,3->2 后,个位上的 2 就可以变大了,直接 2->9,最终返回29
  2. 大体思路:如果发现两位不符合单调递增前一位小于等于后一位的情况要做处理时,就要对前一位-1,后一位再变为 9。
  3. 那我们要从前往后遍历还是从后往前遍历呢?拿 332 举例,如果从前往后,比较到十位和个位时,整体从332->329,但此时百位和十位又不对了,因为后面处理完的值可能是比前面的值小的,没有重复利用到前面的比较结果。如果从后往前遍历,比较到十位和个位时,整体从332->329,再比较百位和十位时,整体从 329->299,这样能得到我们要的结果是因为从后往前遍历时是能够利用到后面遍历过的结果的
  4. 为了方便遍历,把 n 变为字符数组char[] chars=(n+“”).toCharArray()。再定义个 start 标记从哪个位置开始往后遍历将数值变为 9,初始化为 chars.length,初始化为这个是因为如果数字本身就是单调递增的就不用更改数值
  5. for(int i=chars.length-1;i>0;i++)这里 i 不能等于 0 是因为后面是 i-1 和 i 比较,等于 0 会越界,然后是处理逻辑,if(chars[i-1]>chars[i])即前面一位大于当前一位时,就要将前一位-1,chars[i-1]–,然后用 start=i 标记一下位置,后面处理 start 后面的数位都变为 9
  6. 上面处理完就要更新数值 9 了,for(int i=start;i<chars.length;i++)chars[i]=‘9’。
  7. 这里可能疑惑,为什么不在上面第一个循环里就把数值变为 9 呢?举例 1000,我们这里比较处理的逻辑只发生在千位和百位的“10”,只会变为了“09”,整体就是变为了“0900”而我们要的是“999”
  8. 最后将这个 char[] 转为 String 后再转为 int

1.2 代码

//
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] chars=(n+"").toCharArray();
        int start=chars.length;
        for(int i=chars.length-1;i>0;i--){
            if(chars[i-1]>chars[i]){
                chars[i-1]--;
                start=i;
            }
        }
        for(int i=start;i<chars.length;i++){
            chars[i]='9';
        }
        return Integer.parseInt(new String(chars));
    }
}

贪心算法总结

2.1 理论基础

  1. 贪心很简单,就是常识?
    贪心思路往往很巧妙,并不简单
  2. 贪心有没有固定的套路?
    无套路,也没有框架,只能多练
  3. 什么题目是贪心呢?

观点来自程序员Carl:如果找出局部最优并可以推出全局最优,就是贪心,如果局部最优都没找出来,就不是贪心,可能是单纯的模拟。但学会解题就行

  1. 如何知道局部最优推出全局最优,有数学证明么?

观点来自程序员Carl:在做贪心题的过程中,如果再来一个数据证明,其实没有必要,手动模拟一下,如果找不出反例,就试试贪心。面试中,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了

2.2 贪心简单题

以下三道题目就是简单题,大家会发现贪心感觉就是常识。是的,如下三道题目,就是靠常识,但也得具体分析局部最优是什么,全局最优是什么,贪心也要贪的有理有据。

  1. 455. 分发饼干
  2. 1005. K 次取反后最大化的数组和
  3. 860. 柠檬水找零

2.3 贪心中等题

贪心中等题,靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处

  1. 376. 摆动序列
  2. 738. 单调递增的数字
2.3.1 贪心解决股票问题

大家都知道股票系列问题是动规的专长,其实用贪心也可以解决,而且还不止就这两道题目,但这两道比较典型。

  1. 122. 买卖股票的最佳时机 II
  2. 714. 买卖股票的最佳时机含手续费
2.3.2 两个维度权衡问题

在出现两个维度相互影响的情况时,两边一起考虑一定会顾此失彼,要先确定一个维度,再确定另一个一个维度。

  1. 135. 分发糖果
  2. 406. 根据身高重建队列

2.4 贪心难题

这里的题目如果没有接触过,其实是很难想到的,甚至接触过,也一时想不出来,所以题目不要做一遍,要多练!

2.4.1 贪心解决区间问题

关于区间问题,各种覆盖各种去重。

  1. 55. 跳跃游戏
  2. 45. 跳跃游戏 II
  3. 452. 用最少数量的箭引爆气球
  4. 435. 无重叠区间
  5. 763. 划分字母区间
  6. 56. 合并区间
2.4.2 其他难题
  1. 最大子数组和其实是动态规划的题目,但贪心性能更优,很多同学也是第一次发现贪心能比动规更优的题目。
  2. 134. 加油站可能以为是一道模拟题,但就算模拟其实也不简单,需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。
  3. 最后贪心系列压轴题目968. 监控二叉树,不仅贪心的思路不好想,而且需要对二叉树的操作特别娴熟,这就是典型的交叉类难题了。
目录
打赏
0
0
0
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
6月前
|
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
94 7