LeetCode 738. Monotone Increasing Digits

738. Monotone Increasing Digits

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()代替。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

1773
来自专栏PHP在线

php的字符串常用函数

1. str_word_count 统计单词个数 2. count_chars 得到字符串里面字符的有关情况 3. str_len 得到字符串长度,就是...

4186
来自专栏Coding迪斯尼

使用普拉特分析法解析极为复杂的算术表达式

1063
来自专栏Kiba518

C#语法——泛型的多种应用

泛型是.NET Framework 2.0 版类库就已经提供的语法,主要用于提高代码的可重用性、类型安全性和效率。

923
来自专栏jessetalks

Javascript基础回顾 之(一) 类型

  本来是要继续由浅入深表达式系列最后一篇的,但是最近团队突然就忙起来了,从来没有过的忙!不过喜欢表达式的朋友请放心,已经在写了:) 在工作当中发现大家对Jav...

3757
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

1180
来自专栏Golang语言社区

【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解

题目描述: 给定一字符串表示的高精度数,判断它是否是可循环的。如果假设字符串num的长为n,则将num从1开始乘到n,如果每次得到的结果包含的字符元素都和a是相...

35511
来自专栏伪君子的梦呓

题解~按照特定的格式输出~C++做法

一共三行,第一行:位数 第二行: 用空格分开的每个数字,注意最后一个数字后没有空格 第三行: 按逆序输出这个数

544
来自专栏HansBug's Lab

1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

3015
来自专栏前端小栈

正则详解

转自: JS正则表达式一条龙讲解,从原理和语法到JS正则、ES6正则扩展,最后再到正则实践思路

1113

扫码关注云+社区

领取腾讯云代金券