代码随想录算法训练营Day36 | 738.单调递增的数字、968.监控二叉树、贪心算法总结 | Python | 个人记录向

738.单调递增的数字

代码随想录：738.单调递增的数字
Leetcode：738.单调递增的数字

做题

无思路。

看文章

例如：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.监控二叉树
Leetcode：968.监控二叉树

做题

每隔一层放一个摄像头，同时记录两个方案（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。
心得：贪心算法多想想。

​