LWC 61:738. Monotone Increasing Digits

LWC 61:738. Monotone Increasing Digits

传送门:738. Monotone Increasing Digits

Problem:

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].

思路1: 求 <= N中,每一位大于等于前一位的最大num。无脑做法,不断减一,直到找到第一个符合Monotone定义的数。

超时版本:

    public int monotoneIncreasingDigits(int N) {
        int num = N;
        while (!valid(String.valueOf(num))) {
            num --;
        }
        return num;
    }

    boolean valid(String num) {
        int n = num.length();
        char[] cs = num.toCharArray();
        for (int i = 1; i < n; ++i) {
            if (cs[i] < cs[i - 1]) return false;
        }
        return true;
    }

显然遇到大数时会超时。

思路2: 举个例子,比如33296这个数,先看6,因为9比6大,显然不符合Monotone定义,所以为了满足求得最大的num,6一定变成9,且9减1,所以这个数就变成了33289,同理此时2和3是不符合定义,于是又变成了32999,还是一样,最终就变成了29999。

再看一个例子:23296,根据上述的过程则变为22999。所以只要对其中的每一位减一,后续的几位都变成9,生成多个候选解,那么必然有一个解在其中。

比如:

23296

可以生成:
1. 19999
2. 22999
3. 23199
4. 23289

取其符合Monotone定义的最大数即可

Java版本:

    public int monotoneIncreasingDigits(int N) {
        int max = 0;
        String num = String.valueOf(N);
        int n = num.length();

        for (int i = 0; i < n; ++i) {
            StringBuilder sb = new StringBuilder(num.substring(0, i + 1));
            int tmp = Integer.parseInt(sb.toString()) - 1;
            StringBuilder ss = new StringBuilder(String.valueOf(tmp));
            for (int j = i + 1; j < n; ++j) {
                ss.append("9");
            }
            int cmp = Integer.parseInt(ss.toString());
            if (valid(ss.toString()))
                max = Math.max(max, cmp);
        }

        if (valid(num)) max = Math.max(max, N);

        return max;
    }

    boolean valid(String num) {
        int n = num.length();
        char[] cs = num.toCharArray();
        for (int i = 1; i < n; ++i) {
            if (cs[i] < cs[i - 1]) return false;
        }
        return true;
    }

Python版本:

    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        ans = 0
        num = str(N)
        n = len(num)

        for i in range(n):
            sb = num[0 : i + 1]
            tmp = int(sb) - 1
            ss = str(tmp)
            for j in range(i + 1, n):
                ss += '9'
            cmp = int(ss)
            if self.valid(ss):
                ans = max(ans, cmp)

        if self.valid(num):
            ans = max(ans, N)

        return ans

    def valid(self, num):
        n = len(num)
        for i in range(1, n):
            if num[i] < num[i - 1]:
                return False
        return True   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

最简单的匿名方法与委托示例

using System; namespace ConsoleApplication1 {     class Program     {    ...

19610
来自专栏机器学习入门

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers 传送门:POJ 2739. Sum of Consecutive...

1947
来自专栏知识分享

C#中public与private与static

现在静下心来想要重新细致的过一遍C#,因为自己做C#没有底气,, 闲话少说 先来一句话 public(共有的) 声明的方法和属性,可以被外部调用. privat...

2784
来自专栏每日一篇技术文章

Swift3.0 - 真的很简单

中文翻译文档 https://github.com/numbbbbb/the-swift-programming-language-in-chinese

1151
来自专栏IT进修之路

原 分分钟看懂java用引用传递与值传递在

1805
来自专栏Kiba518

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

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

883
来自专栏程序员的SOD蜜

在C++中反射调用.NET(三) 使用非泛型集合的委托方法C++中的列表对象list C++传递集合数据给.NET创建泛型List实例反射静态方法反射调用索引器当委托遇到协变和逆变C++/CLI

在.NET与C++之间传输集合数据 上一篇《在C++中反射调用.NET(二)》中,我们尝试了反射调用一个返回DTO对象的.NET方法,今天来看看如何在.NET与...

25310
来自专栏博客园

.NET面试题解析(03)-string与字符串操作

4.以下代码执行后内存中会存在多少个字符串?分别是什么?输出结果是什么?为什么呢?

792
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict、Set专栏-新排版)

在线预览:http://github.lesschina.com/python/base/pop/3.listtupledict_set.html

1985
来自专栏云霄雨霁

LL(1)语法分析程序

1230

扫码关注云+社区