专栏首页机器学习入门LWC 61:738. Monotone Increasing Digits

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

相关文章

  • LWC 59:728. Self Dividing Numbers

    LWC 59:728. Self Dividing Numbers 传送门:728. Self Dividing Numbers Problem: A sel...

    用户1147447
  • 算法细节系列(32):有趣的数学

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LWC 71: 782. Transform to Chessboard

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 1019 数字黑洞 (20 分)

    给定任一个各位数字不完全相同的 4 位正整数,如果我们先把 4 个数字按非递增排序,再按非递减排序,然后用第 1 个数字减第 2 个数字,将得到一个新的数字。一...

    可爱见见
  • 【LeetCode】221. 最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    韩旭051
  • Unique Paths

    问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

    用户1624346
  • 剑指offer(61-67)题解

    例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树

    萌萌哒的瓤瓤
  • Java工具集-数学(阶乘函数)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • leetcode-367-Valid Perfect Square

    chenjx85

扫码关注云+社区

领取腾讯云代金券