当前位置: 首页 > news >正文

代码随想录算法训练营Day37|738.单调递增的数字、贪心算法总结

目录

738.单调递增的数字

方法一:暴力解法

 方法二:贪心解法

贪心算法总结


738.单调递增的数字

题目链接

文章链接

方法一:暴力解法

class Solution {
private:// 各位递增判断函数bool checkNum(int num) {int max = 10;while (num) {int t = num % 10;if (max >= t) max = t;else return false;num = num / 10;}return true;}
public:int monotoneIncreasingDigits(int N) {for (int i = N; i > 0; i--) { // 从大到小遍历if (checkNum(i)) return i;}return 0;}
};

 方法二:贪心解法

         要注意相邻位置比较的逻辑实现和前后遍历顺序,只有从后向前遍历才能减少处理因为前一个相邻元素处理后改变的新值对当前值判断的影响。

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--){if (strNum[i - 1] > strNum[i]) {strNum[i - 1]--;flag = i;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

贪心算法总结

        在贪心算法题的练习过程中,虽然没有能够总结出能够直接套用的模板,但是还是对于不同难度的贪心算法题有了大概的认识。

        首先是一些简单题,基本上通过常识就能解决不用想具体的局部最优和全局最优。

        对于一些中等题,贪心算法就展现出它的巧妙之处了,对于类似重叠区间的题目,利用贪心实现由固定的套路;对于要同时考虑两个维度的题目,往往先选择一个合适的维度进行讨论,再考虑选择另一个维度讨论补充。

        对于一些贪心难题,例如和二叉树等较难的数据结构关联起来,处理起来就相当麻烦,在一刷的时候我选择跳过。

http://www.lryc.cn/news/287075.html

相关文章:

  • 笔记-影响力-对比,互惠,赌徒原理
  • PIL、cv2、numpy,和pytorch(torch)之间的转换
  • Java面试题50道
  • 电脑怎么剪辑视频?这些软件不可错过
  • HBase学习七:Compaction
  • MySQL定期整理磁盘碎片
  • 【centos7安装docker】
  • 四、Flask学习之JavaScript
  • IO 专题
  • MySql索引事务讲解和(经典面试题)
  • 《微信小程序开发从入门到实战》学习九十一
  • 【立创EDA-PCB设计基础】6.布线铺铜实战及细节详解
  • Node.JS CreateWriteStream(大容量写入文件流优化)
  • 安卓开发之自动缩放布局
  • DDD系列 - 第9讲 实体、值对象
  • 5分钟做自己的微信红包封面
  • pytorch中BCELoss 和 binary_cross_entropy_with_logits之间的区别
  • 无刷电机学习-方波电调 程序篇1(AM32)
  • 如何自己制作一个属于自己的小程序?
  • HTML 入门手册(二)
  • 零基础学Python(5)— 基本数据类型
  • centos7安装Redis7.2.4
  • certificate-transparency-go用例
  • 前端上传大文件使用分片上传
  • Kotlin 解构声明
  • 基于若依的ruoyi-nbcio流程管理系统一种简单的动态表单模拟测试实现(四)
  • 遗传算法原理详细讲解(算法+Python源码)
  • Linux文本处理指令汇总
  • Prompt Engineering
  • Ansible剧本playbooks