- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
力扣题目链接(opens new window) 。
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增.
(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。) 。
示例 1
示例 2
示例 3
说明: N 是在 [0, 10^9] 范围内的一个整数 。
题目举的例子有点不太好理解,这里再举一个吧 。
什么意思呢?就是32这个输入数,其不满足各个位数上的数字是单调递增的规则 。
因此需要找一个比32小但是尽可能大的整数,该整数还要满足各个位数上的数字单调递增的规则 。
那么29显然是符合条件的 。
用人脑想可以想到上面情况中29是符合条件的数,但是用算法怎么实现?
如果去遍历nums(32),可以得到nums[i](2)小于nums[i - 1](3) 。
此时出现了单调递减,不符合条件,需要去找比nums小的一个最大单调递增整数 。
怎么找?
因为32已经是单调递减了,所以 个位上的2无论怎么变化都不能逆转递减的趋势,因此需要把十位减小使整体满足递减的要求 ,按照上述逻辑可以得到22 。
因为大于等于都算递增,所以此时的22已经满足单调递增的条件了,接下来需要达成最大整数这个条件 。
显然22不是小于32的数中满足单调递增的最大整数,在2X中找最大整数,那X只要取9就可以使整体最大,所以满足所有条件的数是29 。
总结一下:
当遍历遇到单调递减的两位数时, 可以直接将十位数减1,然后个位取9,得到小于当前这两位数的最大单调递增整数 。
这里也可以确认 ,遍历时我们是两个两个数来判断是否符合条件的 。
问题又来了,遍历nums的顺序是什么呢?
先说结论,应该 从后先前遍历 。
举个例子:
如果 从前向后 遍历,过程如下
先得到33,33满足单调递增条件,不管 。
然后得到32,不满足条件,按照上面的逻辑找到小于32有满足条件的最大整数29,遍历结束 。
此时整体为329,还是不满足条件 。
原因是 从前向后遍历没有将前面判断得到的结果利用起来 。
在来看 从后向前 遍历:
先得的32,不满足条件,修改为29,此时整体为329 。
然后得到32(基于前一步的结果),还是不满足条件,修改为29,此时整体为299,遍历结束 。
结果正确 。
上面其实就是全部的解题逻辑了,但是按照上面的讨论去实现代码时会发现有问题,每次遇到单调递减的数时我们会下意识的直接把9给换到相应位置,但其实这样会出错 。
举个例子:
这个例子的正确答案是2999,如果在实现时按照上面的问题逻辑来的话,得到的结果会是2929 。
先不说它是不是最大的吧,它就不满足单调递增 。
因此我们需要一个变量,记录最后一次要改9的位置,然后将其后位置的所有数全部改成9 。
3 2 3 2
↑ ↑
i-1 i
i 处要改9,此时,flag == 3 。
3 2 3 2
↑ ↑
i-1 i
此时flag还是3 。
3 2 3 2
↑ ↑
i-1 i
i 处要改9,此时,flag == 1 。
遍历结束,将flag往后的所有数都改成9,得到正确结果2999 。
注意, flag的初始值应该指向数组末尾 。
注意这里给的输入是一个int,要先把其转化为str才能遍历 。
然后改完记得再转回来(使用 stoi函数 ) 。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
int flag = strNum.size();//flag初始值应该指向数组末尾
for(int i = strNum.size() - 1; i > 0; --i){
if(strNum[i - 1] > strNum[i]){//单调递减
strNum[i - 1]--;
// strNum[i] = '9';
flag = i;//记录要修改9的位置
}
}//遍历完成,找到要修改9的位置
for(int i = flag; i < strNum.size(); ++i){//将flag后的数全改为9
strNum[i] = '9';
}
int num = stoi(strNum);//转回int
return num;
}
};
最后此篇关于【LeetCode贪心#11】单调递增的数字(详解)的文章就讲到这里了,如果你想了解更多关于【LeetCode贪心#11】单调递增的数字(详解)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
fiddle :http://jsfiddle.net/rtucgv74/ 我正在尝试将第一个字符与 3 位数字匹配。所以下面的代码应该提醒f234。但反而返回 null ? 源代码: var reg
复制代码 代码如下: Dim strOk,strNo strOk = "12312321$12
我想找 {a number} / { a number } / {a string}模式。我可以得到number / number工作,但是当我添加 / string它不是。 我试图找到的例子: 15
我,我正在做一个模式正则表达式来检查字符串是否是: 数字.数字.数字,如下所示: 1.1.1 0.20.2 58.55541.5221 在java中我使用这个: private static Patt
我有一个字符串,我需要检查它是否在字符串的末尾包含一个数字/数字,并且需要将该数字/数字递增到字符串末尾 +1 我会得到下面的字符串 string2 = suppose_name_1 string3
我正在寻找一个正则表达式 (数字/数字),如(1/2) 数字必须是 1-3 位数字。我使用 Java。 我认为我的问题比正则表达式更深。我无法让这个工作 String s ="(1/15)";
谁能帮我理解为什么我在使用以下代码时会出现类型错误: function sumOfTwoNumbersInArray(a: [number, number]) { return a[0] +
我看到有些人过去也遇到过类似的问题,但他们似乎只是不同,所以解决方案也有所不同。所以这里是: 我正在尝试在 Google Apps 脚本中返回工作表的已知尺寸范围,如下所示: var myRange
我试图了解python中的正则表达式模块。我试图让我的程序从用户输入的一行文本中匹配以下模式: 8-13 之间的数字“/” 0-15 之间的数字 例如:8/2、11/13、10/9 等。 我想出的模式
简单地说,我当前正在开发的程序要求我拆分扫描仪输入(例如:2 个火腿和奶酪 5.5)。它应该读取杂货订单并将其分成三个数组。我应该使用 string.split 并能够将此输入分成三部分,而不管中间字
(number) & (-number) 是什么意思?我已经搜索过了,但无法找到含义 我想在 for 循环中使用 i & (-i),例如: for (i = 0; i 110000 .对于i没有高于
需要将图像ID设置为数字 var number = $(this).attr('rel'); number = parseInt(number); $('#carousel .slid
我有一个函数,我想确保它接受一个字符串,后跟一个数字。并且可选地,更多的字符串数字对。就像一个元组,但“无限”次: const fn = (...args: [string, number] | [s
我想复制“可用”输入数字的更改并将其添加或减去到“总计”中 如果此人将“可用”更改为“3”,则“总计”将变为“9”。 如果用户将“可用”更改为“5”,则“总计”将变为“11”。 $('#id1').b
我有一个与 R 中的断线相关的简单问题。 我正在尝试粘贴,但在获取(字符/数字)之间的断线时遇到问题。请注意,这些值包含在向量中(V1=81,V2=55,V3=25)我已经尝试过这段代码: cat(p
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我在 Typescript 中收到以下错误: Argument of type 'number[]' is not assignable to parameter of type 'number' 我
在本教程中,您将通过示例了解JavaScript 数字。 在JavaScript中,数字是基本数据类型。例如, const a = 3; const b = 3.13; 与其他一些编程语言不同
我在 MDN Reintroduction to JavaScript 上阅读JavaScript 数字只是浮点精度类型,JavaScript 中没有整数。然而 JavaScript 有两个函数,pa
我们在 Excel 中管理库存。我知道这有点过时,但我们正在发展商业公司,我们所有的钱都被困在业务上,没有钱投资 IT。 所以我想知道我可以用Excel自动完成产品编号的方式进行编程吗? 这是一个产品
我是一名优秀的程序员,十分优秀!