代码随想录算法训练营第32天—贪心算法06 | ● *738.单调递增的数字 ● *968.监控二叉树 ● 总结

本文主要是介绍代码随想录算法训练营第32天—贪心算法06 | ● *738.单调递增的数字 ● *968.监控二叉树 ● 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

*738.单调递增的数字

https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

考点
- 贪心算法
我的思路
- 暴力解法
视频讲解关键点总结
- 几个关键点
- 一，如果当前数位小于上一数位，如87，则应直接将上一数位减1，当前数位设为9，如79，因为这是满足题意的最大结果
- 二，如果直接在循环过程中进行上述修改操作，将会在某些情况下发生遗漏，如1000将被修改为900而不是999,1323将被修改为1293而不是1299；因此，应在循环过程中仅将不满足要求的上一数位减1，而记录最靠前的那个需要改为9的数位，并在循环之后将该数位之后全部改为9（这样才满足递增的要求）
我的思路的问题
- 时间复杂度超限
代码书写问题
- 直接修改字符串变量是不允许的，因此可以采用切片之后相加的方式生成新字符串
可执行代码

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:n = str(n)index = len(n)for i in range(len(n) - 1, 0, -1):if int(n[i]) < int(n[i - 1]):index = in = n[:i - 1] + str(int(n[i - 1]) - 1) + n[i:]n = n[:index] + ('9' * (len(n) - index))return int(n)

*968.监控二叉树

https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

考点
- 贪心算法
- 二叉树
我的思路
- 无思路
视频讲解关键点总结
- 关键点如下：
- 一、怎么放摄像头？应从底向上放（对应二叉树的后序遍历），因为从叶子节点向上遍历才能尽可能利用摄像头的上下覆盖特性，如果从根节点开始，由于根节点数目远少于叶子节点，其所使用的摄像头数目将超过从下向上遍历
- 二、怎么判断当前节点是否要放摄像头？利用子节点传上来的状态进行判断
  - 状态0，子节点没有被摄像头覆盖
  - 状态1，子节点有摄像头
  - 状态2，子节点被摄像头覆盖
  - 若两个子节点均被摄像头覆盖，则当前节点应返回状态0
  - 若两个子节点有至少其一没有被覆盖，则当前节点应返回状态1，同时结果计数加1
  - 若两个子节点有至少其一有摄像头，则当前节点应返回状态2
- 三、如果找到了空节点，应该将其设置为什么状态？空节点应设置为状态2，这样当前节点才会返回状态0
- 四、按照如上思路遍历完二叉树后，根节点有可能没有被摄像头覆盖，此时应判断二叉树的递归遍历函数返回值是否为0（即根节点为状态0），如果是，则应结果计数加1
我的思路的问题
- 无思路
代码书写问题
- 这里的结果变量不能直接定义一个整型变量，因为整型变量在python里为不可变类型，因此在递归遍历时对其进行的修改并没有改变原始变量的值，而是在递归函数里创建了一个新的局部变量，所以使用列表这种可变类型来进行代替
可执行代码

class Solution:def traversal(self, root, result):if root is None:return 2condition1 = self.traversal(root.left, result)condition2 = self.traversal(root.right, result)if condition1 == 2 and condition2 == 2:return 0elif condition2 == 0 or condition1 == 0:result[0] += 1return 1elif condition2 == 1 or condition1 == 1:return 2def minCameraCover(self, root: Optional[TreeNode]) -> int:result = [0]if self.traversal(root, result) == 0:result[0] += 1return result[0]