代码随想录算法训练营Day31

力扣738.单调递增的数字【medium】
力扣968.监控二叉树【hard】

一、力扣738.单调递增的数字【medium】

题目链接：力扣738.单调递增的数字

视频链接：代码随想录

1、思路

• 先将整数转为字符串变成可迭代对象，再转为列表
• 从后向前遍历，才可以重复使用之前的结果
• 当遍历的数比前一个数小，我们就将前一个数-1，后面的数都赋值为9
• 最后返还结果先转为字符串再转为整数型
• 时间复杂度：$O(n)$

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)strNum[i: ] = '9' * (len(strNum) - i)return int(''.join(strNum))

3、代码问题

• = list(str(n))：这边这一步是必须的，因为整数不是可迭代对象，无法自动切割为列表，但是字符串可以
• strNum[i-1] = str(int(strNum[i-1]) - 1) ：这边这个也不可以直接对字符串-1操作，因为字符串是无法进行算术运算，必须先转为整数型
• 而if语句里直接对字符串进行判断行得通的原因是：本质是比较它们的 ASCII 码值

---

二、力扣968.监控二叉树【hard】

题目链接：力扣力扣968.监控二叉树

视频链接：代码随想录

1、思路

• 

• 这边要注意情况2必须考虑在情况3前，否则将会遗漏camera的数量，可以举个例子试试

• 

• 时间复杂度：$O(n)$

2、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: Optional[TreeNode]) -> int:result = [0]if self.traversal(root,result) == 0:result[0] += 1return result[0]def traversal(self, cur:Optional[TreeNode], result = List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)if left == 2 and right == 2:return 0elif left == 0 or right == 0:result[0] += 1return 1else:return 2

3、代码问题

• result = [0] ：使用列表是为了绕过Python对不可变类型的传值限制，确保递归过程中所有调用共享同一计数器。
  • 这是Python中处理递归共享状态的常见技巧。如果追求代码清晰，类成员变量也是一种可选方案，但需注意副作用。
  • 

---