算法训练营Day37(贪心6)

发布时间:2024年01月20日

738.单调递增的数字?力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

注意特例1000

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # 将整数转换为字符串
        strNum = str(n)
        # flag用来标记赋值9从哪里开始
        # 设置为字符串长度,为了防止第二个for循环在flag没有被赋值的情况下执行
        flag = len(strNum)
        
        # 从右往左遍历字符串
        for i in range(len(strNum) - 1, 0, -1):
            # 如果当前字符比前一个字符小,说明需要修改前一个字符
            if strNum[i - 1] > strNum[i]:
                flag = i  # 更新flag的值,记录需要修改的位置
                # 将前一个字符减1,以保证递增性质
                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]
        
        # 将flag位置及之后的字符都修改为9,以保证最大的递增数字
        for i in range(flag, len(strNum)):
            strNum = strNum[:i] + '9' + strNum[i + 1:]
        # 将最终的字符串转换回整数并返回
        return int(strNum)

968.监控二叉树?(可以跳过)力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

本题是贪心和二叉树的一个结合,比较难,一刷就跳过吧。?

总结?

可以看看贪心算法的总结,贪心本来就没啥规律,能写出个总结篇真的不容易了?

文章来源:https://blog.csdn.net/2301_79788081/article/details/135702324
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。