Day37 贪心part06
738.单调递增的数字
leetcode题目链接：738. 单调递增的数字 - 力扣（LeetCode）
思路：遍历数组，如果前一位i-1比后一位i的数值大，那前一位要-1，这样才能有比后一位小的可能，同时后一位取能取到的最大值，比如9
所以是从前往后还是从后往前
这道题看起来是要从前往后遍历，但是会出现以下问题：例如332，一开始33是符合的，但是到后面的32就不符合了，会变成329，这是这样又需要修改前一位了；所以这样遍历会造成之前的还需要重新变动
这里还有一个小技巧，虽然题目给出的是int类型，但是还是转化为str就可以逐位操作了，这样出现首位0的情况也不用担心，最终再转化位int即可
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
n = str(n)
flag = len(n) # 记录一下从哪一位开始要标记位9
for i in range(len(n)-1, 0, -1):
if n[i] < n[i-1]:
#这里修改不像c++的ascii是连续的 n[i-1] -= 1
n = n[:i-1]+ str(int(n[i-1])-1)+n[i:]
flag = i
i = flag
while i <len(n):
# print(i, n, len(n))
n = n[:i]+ '9'+ n[i+1:]
i+=1
return int(n)
968.监控二叉树
leetcode题目链接：. - 力扣（LeetCode）
思路：
1、贪心思路：发现题目示例中的摄像头都没有放在叶子节点上！这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
2、二叉树的遍历顺序：所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！所以应该是后序遍历（左右中）
**3、**情况处理，如何间隔两个节点放一个摄像头：节点状态表示
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
情况判断：
- 如果两个孩子都是0或者又1个为0，那么父节点一定是1
- 如果两个孩子都是2，那么父节点是0
- Null节点是2
- 左右孩子节点有1个摄像头1，父节点是2
- 最后就是头节点root要是没有覆盖，也应该放置摄像头1
# 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:
def __init__(self):
self.res = 0
def traversal(self, node):
if node is None:
return 2
left = self.traversal(node.left)
right = self.traversal(node.right)
if left==0 or right == 0:
self.res+=1
return 1
elif left==2 and right == 2:
return 0
elif left==1 or right == 1:
return 2
def minCameraCover(self, root: Optional[TreeNode]) -> int:
value = self.traversal(root)
if value ==0:
self.res+=1
return self.res
还是要再复习一下二叉树
