Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.
(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)
Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].
题目大意:给出一个数,返回比这个数小的最大的各个位上是单调递增的数
这是我开始选择的方法,非常直白,但是直白简单的方法往往不是最佳的解法,提交到LeetCode上,给我抛出一个超时,可见效率有多低。首先写一个函数,判断一个数是否是符合要求的,如果不符合要求,就将这个数递减,直到找到符合的数为止,试想假如这个数是95555555555,那么符合题意的数是9,想想看要做多少次减法啊!!!!
public int monotoneIncreasingDigits(int N) {
int n = N;
while (!isIncreaseNum(n)){
n--;
}
return n;
}
public boolean isIncreaseNum(int num){
String str = Integer.toString(num);
char[] chars = str.toCharArray();
for (int i = 1 ; i < chars.length;i++){
if (chars[i] < chars[i-1]) return false;
}
return true;
}
针对数字研究后,知道可以很容易的写出另外一种更优秀的解法。
public int monotoneIncreasingDigits(int N) {
char[] chars = Integer.toString(N).toCharArray();
int index = 0;
for (int i = 1 ; i < chars.length ; i++){
if (chars[i] == chars[index]) continue;
if (chars[i] < chars[index]){
chars[index] = (char)(chars[index] - 1);
for (int j = index+1;j<chars.length;j++){
chars[j] = '9';
}
break;
}else
index = i;
}
return Integer.parseInt(new String(chars));
}
本解法,采用 一个index值记录一个将要减一的一位,后面的所有位置为9即可。是不是非常简单呢?思路就不讲解了,也是非常的直白。
将一个char[]的数组转化为String类型,不可以直接调用toString()方法,查看char的toSting()方法,可以知道:
public String toString() {
return getClass().getName() + "@" + Integer.toHexString(hashCode());
}
像这样返回的不是String类型;应该采用newString(chars),转为String类型。
最后,string转为int:
Integer.parseInt() 也可以采用 Integer.valueOf()代替。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。