738.单调递增的数字

思路：

1.一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

2.向后遍历

从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

e.g:332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

​ 后向前遍历332的数值变化为：332 -> 329 -> 299

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

968.监控二叉树

思路：

让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

可以使用后序遍历的方式遍历二叉树的节点，这样就可以优先遍历叶子节点。

对于每个节点，利用贪心思想，可以确定三种状态：

• 第一种状态：该节点无覆盖
• 第二种状态：该节点已经装上了摄像头
• 第三种状态：该节点已经覆盖

为了让摄像头数量最少，要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。对此应当分析当前节点和左右两侧子节点的覆盖情况。

• 情况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 左节点覆盖，右节点无覆盖

这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。

此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

# Case 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 += 1
return 1

• 情况3：左右节点至少有一个有摄像头，如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

  • left == 1 && right == 2 左节点有摄像头，右节点有覆盖

  • left == 2 && right == 1 左节点有覆盖，右节点有摄像头

  • left == 1 && right == 1 左右节点都有摄像头

# Case 3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头
if left == 1 or right == 1:return 2

• 情况4：头结点没有覆盖，以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：

if traversal(root) == 0:result += 1

class Solution:def minCameraCover(self, root: TreeNode) -> int:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖result = 0# 从下往上遍历：后序（左右中）def traversal(curr: TreeNode) -> int:nonlocal resultif not curr: return 2left = traversal(curr.left)right = traversal(curr.right)# Case 1:# 左右节点都有覆盖if left == 2 and right == 2:return 0# Case 2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点有无覆盖，右节点摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖elif left == 0 or right == 0:result += 1return 1# Case 3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头elif left == 1 or right == 1:return 2# 其他情况前段代码均已覆盖if traversal(root) == 0:result += 1return result

太原家教网