LeetCode刷题复盘笔记—一文搞懂贪心算法之738. 单调递增的数字(贪心算法系列第十五篇)

news/2024/3/29 15:16:03/文章来源:https://blog.csdn.net/qq_43498345/article/details/129134021

今日主要总结一下可以使用贪心算法解决的一道题目,738. 单调递增的数字

题目:738. 单调递增的数字

Leetcode题目地址
题目描述:
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:
输入: n = 10
输出: 9

示例 2:
输入: n = 1234
输出: 1234

示例 3:
输入: n = 332
输出: 299

提示:

0 <= n <= 10^9

本题重难点

题目要求小于等于N的最大单调递增的整数,那么拿一个两位的数字来举例。

例如:98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

这一点如果想清楚了,这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

这么说有点抽象,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。

解法一:手动求每一位的数字

C++代码

class Solution {
public:int monotoneIncreasingDigits(int n) {vector<int> mem;int flag = 0;int res = 0;for(; n; n /= 10){mem.emplace_back(n % 10);}if(mem.size() == 1 || mem.empty()) return n; for(int i = 1; i < mem.size(); i++){if(mem[i] > mem[i - 1]){mem[i] --;flag = i;}}for(int i = mem.size() - 1; i >= 0; i--){res *= 10;if(i >= flag) res += mem[i];else res += 9;}return res;}
};

写法二:int 转 string直接得到每一位的数字

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

第一种写法是当时自己第一遍写的,没有想到可以直接int 转 string得到每一位的数字
其实以上两种写法都可以,看哪个容易理解会写一种写法就行!


总结

本题只要想清楚个例,例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]减一,strNum[i]赋值9,这样这个整数就是89。就可以很自然想到对应的贪心解法了。

想到了贪心,还要考虑遍历顺序,只有从后向前遍历才能重复利用上次比较的结果。

最后代码实现的时候,也需要一些技巧,例如用一个flag来标记从哪里开始赋值9。欢迎大家关注本人公众号:编程复盘与思考随笔(关注后可以免费获得本人在csdn发布的资源源码)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_72071.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2022年中国前10电商GMV总结

我是卢松松&#xff0c;点点上面的头像&#xff0c;欢迎关注我哦&#xff01; 1&#xff0c;阿里8万亿;2&#xff0c;京东3万亿;3&#xff0c;拼多多3万亿;4&#xff0c;小程序私域电商3万亿;5&#xff0c;抖音电商1.4万亿。6&#xff0c;抖音本地生活服务电商600亿。7&#xf…

广东望京卡牌科技有限公司,2023年团建活动圆满举行

玉兔初临&#xff0c;春天相随&#xff0c;抖擞精神&#xff0c;好运连连。春天是一个万物复苏的季节&#xff0c;来自广东的望京卡牌科技有限公司&#xff0c;也迎来了新年第一次团建活动。在“乘风破浪、追逐梦想”的口号声中&#xff0c;2023望京卡牌目标启动会团结活动正式…

Fortinet推出新一代自研安全芯片,跨所有网络边缘加速网络与安全融合

专注网络与安全融合的全球网络安全领导者 Fortinet&#xff08;NASDAQ&#xff1a;FTNT&#xff09;&#xff0c;近日宣布推出新一代自研安全芯片 FortiSP5&#xff0c;作为 Fortinet ASIC 技术的最新突破&#xff0c;有力推动了分布式网络边缘安全的重大飞跃。FortiSP5 源自 F…

快鲸scrm发布快递行业私域运营解决方案

现如今&#xff0c;快递行业竞争格局日益激烈&#xff0c;前有“四通一达”等传统快递企业&#xff0c;后有自带互联网基因、绑定电商流量新贵快递企业&#xff0c;如菜鸟、京东等。在这一背景下&#xff0c;很多快递企业开启了增长破局之旅&#xff0c;他们纷纷搭建起私域运营…

0/1 nodes are available: 1 node(s) didn‘t match Pod‘s node affinity.

主要是需要确认你的yaml文件中是否有nodeSelector的配置&#xff0c;一般是因为k8s集群中没有相应的node节点匹配导致 这个错误消息表明您正在尝试在不符合Pod的节点亲和性规则的节点上运行Pod。这通常是由于节点选择器或节点亲和性规则设置不正确引起的。 以下是一些可能导致…

前端零基础入门-002-集成开发环境

本篇目标 了解市面上常用的前端集成开发环境&#xff08;ide&#xff09;掌握 HBuiberX 的使用&#xff1a;下载安装&#xff0c;新建项目、网页、运行网页。 内容摘要 本篇介绍了市面上流行的几款前端集成开发环境&#xff08;ide&#xff09;&#xff0c;并介绍了 Hbuilde…

微软Docker学习记录(第二单元)

文章目录什么是容器&#xff1f;什么是软件容器化&#xff1f;什么是 Docker&#xff1f;Docker 体系结构Docker 引擎Docker 客户端Docker 服务器Docker 对象原文链接&#xff1a; https://learn.microsoft.com/zh-cn/training/modules/intro-to-docker-containers以下原文部分…

Softing dataFEED OPC Suite Extended新版本支持从XML文件中读取生产数据

Softing dataFEED OPC Suite Extended V5.25的新功能——“文件读取&#xff08;File Read&#xff09;”&#xff0c;支持访问XML文件中可用的过程数据。 &#xff08;文件读取功能支持获取由XML文件提供的过程数据&#xff09;dataFEED OPC Suite Extended是用于OPC通信和云连…

技术干货!如何玩转Salesforce测试类 (Test Class)?

测试类主要用于评估其他代码片段&#xff0c;确保一切正常且可靠地运行。这可以作为一种早期预警系统&#xff0c;提醒开发人员出现了错误或问题。 不同类型的程序化测试 测试类可以分为多种不同的类型&#xff0c;这改变了我们编写测试的方式及其预期结果。对于Apex测试类&…

R语言实现可理解的随机森林模型(Random Forest)——iml包

Random Forest 解释模型1. 介绍2. 理解随机森林运行机理2.1导入需要的包2.2 构建随机森林模型2.3 RF特征重要性&#xff1a;2.4 特征对预测结果的影响2.5 交互作用2.6 替代模型&#xff08;Decision tree surrogate model&#xff09;2.71. 介绍 机器学习模型通常可以很好地进…

儿童袖套上架美国亚马逊CPC认证

袖套&#xff0c;也称套袖。是戴在袖管外的套子&#xff0c;旨在保护衣服的袖管。通常戴时松垂于另外一只衣袖外面的袖子。美国CPC认证简介&#xff1a;CPC认证是Children’s Product Certificate的英文简称&#xff0c;CPC证书就类似于国内的质检报告&#xff0c;在通过相关检…

内网渗透(四十五)之横向移动篇-WinRM远程执行命令横向移动

系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…

PrivateLoader PPI服务发现RisePro恶意软件窃取分发信息

称为PrivateLoader的按安装付费&#xff08;PPI&#xff09;软件下载器服务正用于恶意软件RisePro的信息窃取。Flashpoint 于 2022 年 12月13日发现了新的窃取者&#xff0c;此前发现了在名为Russian Market的非法网络犯罪市场上使用该恶意软件泄露的“几组日志”。RisePro是一…

IDEA高效插件和设置

安装好Intellij idea之后&#xff0c;进行如下的初始化操作&#xff0c;工作效率提升十倍。 一. 安装插件 1. Codota 代码智能提示插件 只要打出首字母就能联想出一整条语句&#xff0c;这也太智能了&#xff0c;还显示了每条语句使用频率。 原因是它学习了我的项目代码&…

墨菲安全参与信息通信软件供应链安全社区成员大会并获自主研发创新成果奖

2023年2月16日&#xff0c;首届ICT软件供应链安全治理论坛暨信息通信软件供应链安全社区第二届成员大会在北京成功举办&#xff0c;多位业界顶级专家与工业和信息化部网络安全管理局相关领导出席&#xff0c;为现场观众分享了关于软件供应链可持续性与安全治理行业的前瞻与思考…

Apache Shiro与Spring Security对比

Apache Shiro VS Spring Security 1.Spring Security 官方文档&#xff1a;https://spring.io/projects/spring-security#overview介绍&#xff1a; Spring Security是一个能够为基于Spring的企业应用系统提供声明式的安全访问控制解决方案的安全框架。它提供了一组可以在Spr…

CAS底层原理及ABA问题

一、案例CAS是Java中Unsafe类里面的一个方法&#xff0c;它的全称是叫CompareAndSwap比较并交换的一个意思&#xff0c;它的主要功能是能够去保证在多线程的环境下对于共享变量修改的一个原子性。例如&#xff0c;比如说像这样一个场景&#xff0c;有一个成员变量state&#xf…

【分享】订阅卖家云集简云连接器同步销售出库数据至卖家云系统

方案场景 在企业进行数字化转型过程中&#xff0c;数据割裂是企业面临的最大困难&#xff0c;钉钉作为现企业流行的常用办公系统&#xff0c;与第三方ERP系统之间存在着数据割裂的现象&#xff0c;例如&#xff0c;钉钉与卖家云系统&#xff0c;企业员工原来的办公方式是在钉钉…

Vue基础14之TodoList组件自定义事件、全局事件总线、TodoList全局事件总线

Vue基础14TodoList-组件自定义事件先改Header和Footer子组件&#xff0c;List先不考虑App.vueMyHeader.vueMyFooter.vue全局事件总线实现思路正规写法main.jsApp.vueStudent.vueSchool.vue总结&#xff1a;全局事件总线&#xff08;GlobalEventBus&#xff09;TodoList案例&…

修复 K8s SSL/TLS 漏洞(CVE-2016-2183)指南

作者&#xff1a;老 Z&#xff0c;中电信数智科技有限公司山东分公司运维架构师&#xff0c;云原生爱好者&#xff0c;目前专注于云原生运维&#xff0c;云原生领域技术栈涉及 Kubernetes、KubeSphere、DevOps、OpenStack、Ansible 等。 前言 测试服务器配置 主机名IPCPU内存系…