189 8069 5689

代码随想录算法训练营第三十七天|738.单调递增的数字总结-创新互联

贪心算法 一、738.单调递增的数字 题目:

给定一个非负整数 N,找出小于或等于 N 的大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名注册网站空间、营销软件、网站建设、遂宁网站维护、网站推广。

(当且仅当每个相邻位数上的数字 x 和 y 满足 x<= y 时,我们称这个整数是单调递增的。)

示例 1:

  • 输入: N = 10
  • 输出: 9

示例 2:

  • 输入: N = 1234
  • 输出: 1234

示例 3:

  • 输入: N = 332
  • 输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

思路:

1、例如:98,一旦出现strNum[i - 1] >strNum[i]的情况(非单调递增),首先想让strNum[i - 1]--,然后strNum[i]给为9,这样这个整数就是89,即小于98的大的单调递增整数。

2、局部最优:遇到strNum[i - 1] >strNum[i]的情况,让strNum[i - 1]--,然后strNum[i]给为9,可以保证这两位变成大单调递增整数。

全局最优:得到小于等于N的大单调递增的整数。

但这里局部最优推出全局最优,还需要其他条件,即遍历顺序,和标记从哪一位开始统一改成9。

3、此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] >strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

这么说有点抽象,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

所以从前后向遍历会改变已经遍历过的结果!

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 ->329 ->299

确定了遍历顺序之后,那么此时局部最优就可以推出全局。

//版本1
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i >0; i--) {
            if (Integer.parseInt(strings[i])< Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i< strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("",strings));
    }
}

java版本1中创建了String数组,多次使用Integer.parseInt了方法,这导致不管是耗时还是空间占用都非常高,用时12ms,下面提供一个版本在char数组上原地修改,用时1ms的版本

//版本2
class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] >chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i< s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}
二、总结

/file/tupian/20230121/贪心总结water.jpg

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:代码随想录算法训练营第三十七天|738.单调递增的数字总结-创新互联
转载来于:http://cdxtjz.cn/article/csgecj.html

其他资讯