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

相关文章

来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

1878
来自专栏mukekeheart的iOS之旅

No.014 Longest Common Prefix

14. Longest Common Prefix Total Accepted: 112204 Total Submissions: 385070 Diffi...

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

合并排序

分治算法: 用分治策略实现n个元素进行排序的方法。 基本思想: 将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终排好序的子集合合并成所要...

1839
来自专栏Java3y

LinkedHashMap就这么简单【源码剖析】

1334
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

671
来自专栏拂晓风起

java 将数组排序 指这种数组:[] ArrayList之类的请用Collection.sort

891
来自专栏King_3的技术专栏

leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

1105
来自专栏郭耀华‘s Blog

剑指offer第八天

32.把数组排成最小的数 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出...

3426
来自专栏机器学习和数学

[数据结构与算法] 链接表总结

上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有...

2707
来自专栏河湾欢儿的专栏

数组

591

扫码关注云+社区