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 左右节点都有摄像头
-
文章来源：https://www.toymoban.com/news/detail-420793.html
# Case 3:
# left == 1 && right == 2 左节点有摄像头，右节点有覆盖
# left == 2 && right == 1 左节点有覆盖，右节点有摄像头
# left == 1 && right == 1 左右节点都有摄像头
if left == 1 or right == 1:
return 2
- 情况4：头结点没有覆盖，以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
文章来源地址https://www.toymoban.com/news/detail-420793.html
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 result
if not curr: return 2
left = 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 += 1
return 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 += 1
return result
到了这里，关于算法记录 | Day37 贪心算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
