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 条评论
登录 后参与评论

相关文章

来自专栏用户画像

3.2.4页面分配策略

对于分页式的虚拟内存,在准备执行时,不需要也不可能把一个进程的所有页都读取到内存,因此,操作系统必须决定读取多少页,也就是说,给特定的进程分配多大的内存空间,这...

571
来自专栏技术点滴

原型模式(Prototype)

原型模式(Prototype) 原型模式(Prototype) 意图:用原型实例制定创建对象的种类,并且通过拷贝这些原型创建新的对象。 应用:Java/C#中的...

1695
来自专栏Android知识点总结

05-图解数据结构之队列--Queue

864
来自专栏IMWeb前端团队

ECMAScript 2015 (ES6) in Node.js(译)

本文作者:IMWeb link 原文出处:IMWeb社区 未经同意,禁止转载 原文:https://nodejs.org/en/docs/es6/ ...

18210
来自专栏小樱的经验随笔

Codeforces 712C Memory and De-Evolution

C. Memory and De-Evolution time limit per test:2 seconds memory limit per test:2...

2626
来自专栏Python中文社区

教你用 Cython 自己造轮子

我们要造的轮子是一个最简单的栈的实现,用 C/C++来编写能够减小不必要的开销,带来显著的加速。

1013
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch 管理文档

ES支持近实时的索引、更新、查询、删除文档,近实时就意味着刚刚索引的数据需要1秒钟后才能搜索到,这也是与传统的SQL数据库不同的地方。 更多的ES文档资料参...

1839
来自专栏极客猴

如何优雅地进行序列化操作

需要使用Gson或者Fastjson第三方的库,将对象转化为json数据。 我在这里使用Gson做示范。

723
来自专栏快乐八哥

Angular企业级开发(4)-ngResource和REST介绍

一、RESTful介绍 ? RESTful维基百科 REST(表征性状态传输,Representational State Transfer)是Roy Fie...

1747
来自专栏程序员与猫

Elasticsearch 相关 api 操作

A. es 操作 1. 检查 es 集群健康状态 bash命令:curl -XGET 'localhost:9200/_cat/health?v&pretty...

18210

扫码关注云+社区