周口师范做网站,河北项目网在建项目,网站建设图片qq群,wordpress淘口令插件本文目录 738.单调递增的数字做题看文章 968.监控二叉树做题看文章 贪心算法总结以往忽略的知识点小结个人体会 738.单调递增的数字
代码随想录#xff1a;738.单调递增的数字 Leetcode#xff1a;738.单调递增的数字
做题
无思路。
看文章
例如#xff1a;98#xff… 本文目录 738.单调递增的数字做题看文章 968.监控二叉树做题看文章 贪心算法总结以往忽略的知识点小结个人体会 738.单调递增的数字
代码随想录738.单调递增的数字 Leetcode738.单调递增的数字
做题
无思路。
看文章
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先让strNum[i - 1]–然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。 贪心算法如果由前往后遍历由左往右如果strNum[i - 1]减一了可能又小于strNum[i - 2]。故应该由后往前由由往左遍历。
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因为修改前一个字符可能破坏了递增性质strNum[i:] 9 * (len(strNum) - i)# 将列表转换为字符串并将字符串转换为整数并返回return int(.join(strNum))时间复杂度O(n)n 为数字长度 空间复杂度O(n)需要一个字符串转化为字符串操作更方便
968.监控二叉树
代码随想录968.监控二叉树 Leetcode968.监控二叉树
做题
每隔一层放一个摄像头同时记录两个方案root放或不放但只能通过一般的测试例。
看文章
从下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少。 头结点放不放摄像头也就省下一个摄像头 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
后序遍历并实时返回结点的状态具体代码如下
class Solution:# Greedy Algo:# 从下往上安装摄像头跳过leaves这样安装数量最少局部最优 - 全局最优# 先给leaves的父节点安装然后每隔两层节点安装一个摄像头直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) - int:# 定义递归函数result [0] # 用于记录摄像头的安装数量if self.traversal(root, result) 0:result[0] 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) - int:if not cur:return 2left self.traversal(cur.left, result)right self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left 2 and right 2:return 0# 情况2:# left 0 right 0 左右节点无覆盖# left 1 right 0 左节点有摄像头右节点无覆盖# left 0 right 1 左节点无覆盖右节点有摄像头# left 0 right 2 左节点无覆盖右节点覆盖# left 2 right 0 左节点覆盖右节点无覆盖if left 0 or right 0:result[0] 1return 1# 情况3:# left 1 right 2 左节点有摄像头右节点有覆盖# left 2 right 1 左节点有覆盖右节点有摄像头# left 1 right 1 左右节点都有摄像头if left 1 or right 1:return 2时间复杂度: O(n)需要遍历二叉树上的每个节点 空间复杂度: O(n)
贪心算法总结
代码随想录贪心算法总结
以往忽略的知识点小结
python进行list切片赋值时要确保赋值的长度与被赋值的长度相同即便是同一个赋值
个人体会
完成时间1h30min。 心得贪心算法多想想。
