算法随想录| 738.单调递增的数字 ,968.监控二叉树 , 总结

发布时间:2024年01月18日

738.单调递增的数字?

代码随想录

思路

本来以为可以用回溯的,结果他不是求子集,回溯不了。

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        # 将整数转换为字符串
        strNum = list(str(N))
        # 从右往左遍历字符串
        for i in range(len(strNum) - 1, 0, -1):
            # 如果当前字符比前一个字符小,说明需要修改前一个字符
            if strNum[i - 1] > strNum[i]:
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1
                # 将修改位置后面的字符都设置为9,因为修改前一个字符可能破坏了递增性质
                for j in range(i, len(strNum)):
                    strNum[j] = '9'

        # 将列表转换为字符串,并将字符串转换为整数并返回
        return int(''.join(strNum))

总结

这个贪心确实想不出来,不过一看答案就恍然大悟了,从右向左遍历,看数是否是递增的,如果不是就提前减一,把后面的数都变成9,这样他就是局部最优了。

其中“strNum = list(str(N))”和“int(''.join(strNum))”都是我想用的却写不出来的知识,要记。

968.监控二叉树?(可以跳过

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

代码随想录

我选择下次再战,不是没有勇气,而是更有性价比。

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