DAY40:贪心算法(九)单调递增的数字(贪心的思路)

这篇具有很好参考价值的文章主要介绍了DAY40:贪心算法(九)单调递增的数字(贪心的思路)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

738.单调递增的数字(暴力解也需要看一下)

  • 本题暴力解法也需要看一下,虽然暴力解法超时了,但是这种思路是一种很基础的思路,需要了解
  • 数字是没有办法直接采用下标遍历的,如果要for循环遍历每个位置的数字,需要把数字转成字符串string

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

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

  • 0 <= n <= 10^9

暴力解写法

本题题意比较清晰,我们可以首先考虑用暴力来实现一下。也就是给我们一个数值,我们直接从大到小去遍历,并判断每个数值是不是单调递增的。

  • 注意暴力解法不能直接操作i,直接操作i会导致for循环里i–的时候也受到影响!需要用单独的temp来存储i
  • 暴力解法必须需要 bool isIncreasing的原因,是因为while里面break了之后依然会执行外层的for,也就是说会执行for剩下的代码逻辑!我们不能让break出来之后再continue,因此只能加上判断变量,break的情况就判断为false。确定判断为true的时候,才是结束了while循环的时候,此时再返回。
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        for(int i=n;i>=0;i--){
            int max = INT_MAX;
            int temp=i;
            //定义判断变量
            bool isIncreasing = true;
            while(temp){//只要还有数字
                int ten = temp%10;//先取最后一位
                if(max>=ten)  max=ten;
                else{
                    isIncreasing = false;
                    break;//只要前一位不满足大于等于,就说明不是单调递增,记为false继续遍历下个数
                }
                temp=temp/10;//i减少一位        
            }
            //结束while并且满足true,说明找到了
            if(isIncreasing==true) 
                return i;      
        }
        //最后没找到 return 0
		return 0;
    }
};
注意:必须引入isIncreasing变量的原因

暴力解法里面需要注意,while循环中的break语句被执行时,它会立即终止当前正在进行的while循环,并且控制流将会继续从break语句跳出while之后,后面的for代码开始执行。这就意味着即使temp并不是单调递增的(在这种情况下,while循环会由于break语句而提前结束),for循环之后的代码也会被执行!这就可能导致不正确的结果被返回。

break只是跳出当前的循环,在while里面的时候,跳出的是while而不是最外层的for

为此,引入了isIncreasing变量。只有在temp是单调递增的情况下(while循环正常结束,而不是由于break语句而提前结束),isIncreasing变量才会保持为true,并且正确的结果i会被返回。

这种解法逻辑正确,但是超时了。

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode

贪心思路

我们以32来举例。如果两位不符合要求,前一位需要做-1处理这样后一位才有大于前一位的可能

那么前一位-1之后后一位的值应该取最大的,才能让得到的数值最大

因此32的十位-1得到2 个位取最大得到29。也就是说,遍历数字的时候,凡是前面一位>后面一位,都是前面一位做减一,后面一位取最大值(也就是9)

遍历顺序

以332来举例,如果从前往后遍历,遍历到第二个3的时候,就会发现后面的32换成29之后,整体不满足单调递增了

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
从前往后处理的话,因为涉及-1操作,所以后面得到的值,有可能比前面的值要小!会导致遍历到后面不满足单调递增!

从后往前遍历的话,就可以考虑到前一位-1,对前面的数字单调递增特性造成的影响

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode

最开始的写法

  • 后序遍历的原因,是因为涉及到前一位-1,会对单调递增特性有影响
  • 为了方便挨个数字遍历,把int转换成string
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        //转成字符串就是为了方便遍历
        for(int i=str.size()-1;i>0;i--){
            if(str[i-1]<=str[i]) continue;
            //如果出现i-1>i,就把i换成9
            else{
                str[i]='9';
                str[i-1]=str[i-1]-1;//ASCII码-1
            }
        }
        return stoi(str);//string再转成Int
    }
};
debug测试:逻辑错误

上面这段代码提交出现了逻辑错误,因为得到的并不是最大值。

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode

修改版

本题贪心的策略,是遇到了相邻数字前一位>后一位,那么就让前一位变成前一位-1但是此时后面的所有数字都需要变成9

示例如下:

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
比如上面的例子,就必须考虑后面有多个小于前面的数字的情况。

  • 修改版为了让小于情况下后面所有的数字都成为9,需要定义一个变量来控制9的起始位置
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        //flag之后的元素都换成9,初值是不用换的情况
        int flag=str.size();
        //转成字符串就是为了方便遍历
        for(int i=str.size()-1;i>0;i--){
            if(str[i-1]<=str[i]) continue;
            //如果出现i-1>i,就把i换成9
            else{
                flag=i;
                str[i-1]=str[i-1]-1;//ASCII码-1
            }
        }
        cout<<flag<<endl;
        //遍历结束之后flag之后元素都是9
        for(int i=flag;i<str.size();i++){
            str[i]='9';
        }
        return stoi(str);//string再转成Int
    }
};
  • 时间复杂度:O(n),n 为数字长度
  • 空间复杂度:O(n),需要一个字符串,转化为字符串操作更方便
debug测试

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
修改flag初始值后正确。

int转化为字符串的原因

因为本题需要对数字进行遍历,而我们没有直接的方式去获取和操作其特定位置的数字。因此,通常将整数转换为字符串以便于使用下标进行遍历和比较操作。在这种情况下,使用字符串会使操作更加简单直观。

to_string和stoi的用法

我们此处可以查阅c++string的文档:std::basic_string - cppreference.com

DAY40:贪心算法(九)单调递增的数字(贪心的思路),刷题记录,贪心算法,算法,c++,leetcode
to_string() 是 C++ 标准库中的一个函数,它用于将各种数值类型(包括整数、浮点数等)转换为字符串。例如,to_string(123) 将返回字符串 "123"

stoi() 函数则是 to_string() 的反向操作,用于将字符串转换为整数。例如**,stoi("123") 将返回整数 123**。值得注意的是,stoi() 函数会忽略字符串开头的空格,直到找到第一个非空格字符。如果这个字符是数字或者正负符号,函数会继续读取剩余部分,直到遇到非数字字符或到达字符串的末尾。

总结

本题只要想清楚个例,例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]减一,strNum[i]赋值9,这样这个整数就是89。就可以很自然想到对应的贪心解法了

想到了贪心,还要考虑遍历顺序,只有从后向前遍历才能重复利用上次比较的结果。

最后代码实现的时候,也需要一些技巧,例如用一个flag来标记从哪里开始赋值9。文章来源地址https://www.toymoban.com/news/detail-530764.html

到了这里,关于DAY40:贪心算法(九)单调递增的数字(贪心的思路)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode题目详解】第八章 贪心算法 part06 738.单调递增的数字 968.监控二叉树 (day37补)

    当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 # 暴力解法 题意很简单,那么首先想的就是暴力解法了,来我替大家

    2024年02月10日
    浏览(41)
  • 贪心算法part6 | ● 738.单调递增的数字 ● 968.监控二叉树

    代码随想录算法训练营第一天 | 题目、题目 738.单调递增的数字 局部最优:前一个数比当前数小,前一个数位减一,当前数置为9 题目要求小于等于N的最大单调递增的整数,那么拿一个两位的数字来举例。 例如:98,一旦出现strNum[i - 1] strNum[i]的情况(非单调递增),首先想

    2024年02月10日
    浏览(38)
  • 力扣第738题 单调递增的数字 c++ 暴力超时 贪心优化

    738. 单调递增的数字 中等 相关标签 贪心  数学 当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数  n  ,返回  小于或等于  n  的最大数字,且数字呈  单调递增  。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 从N开始

    2024年02月08日
    浏览(37)
  • 贪心算法学习——最长单调递增子序列

    目录 ​编辑 一,题目 二,题目接口 三,解题思路和代码 给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7]  是数组  [0,3,1,6,2,2,7]  的子序列。  

    2024年02月08日
    浏览(42)
  • 力扣算法刷题Day59|单调栈

    力扣题目:# 503.下一个更大元素II  刷题时长:参考题解后2min 解题方法:单调栈 复杂度分析 时间O(n) 空间O(n) 问题总结 如何解决环的问题 本题收获 循环数组解决方案 思路一:将两个nums数组拼接在一起,使用单调栈计算出每一个元素的下一个最大值,最后再把结果集即res

    2024年02月13日
    浏览(84)
  • 算法刷题Day 52 最长递增子序列+最长连续递增子序列+最长重复子数组

    我自己想出来的方法,时间复杂度应该是 O(n2) 滑动窗口 连续的话,可以考虑用滑动窗口 动态规划 贪心算法

    2024年02月14日
    浏览(54)
  • 算法刷题Day 29 递增子序列+全排列+全排列II

    如果直接像下面这样写的话,会出错,出错的案例类似: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9nrEEc2S-1688623883770)(LC491-递增子序列+LC.assets/image-20230703201315163.png)] 本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子

    2024年02月15日
    浏览(43)
  • 【算法日志】贪心算法刷题:重叠区问题(day31)

    目录 前言 无重叠区间(筛选区间) 划分字母区间(切割区间)  合并区间 今日的重点是掌握重叠区问题。

    2024年02月12日
    浏览(48)
  • 单调递增的数字——力扣738

    题目描述 解法

    2024年02月13日
    浏览(36)
  • leetcode 738. 单调递增的数字

             这题用暴力法会超时,我就没试了,采用了个挺巧的方法,为了方便需要先将整数n转换为字符串的形式,然后从后向前遍历,当两个数字非递增时,将前一个数字--,后一个数字的位置记录在index中,之后需要将这个index以后的数字全赋为9。  为了防止将不需要赋

    2024年02月14日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包