目录
任务
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
思路
按照左区间排序，判断重叠区间，扩展重叠区间（重叠时修改result，不重叠时扩展result)。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
intervals.sort(key=lambda x: x[0]) #按照区间左区间排序
result.append(intervals[0])
for i in range(1,len(intervals)):
if intervals[i][0] <= result[-1][1]: #重叠
result[-1][1] = max(intervals[i][1],result[-1][1])
else:
result.append(intervals[i])
return result
738. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
思路
从低位到高位依次比较，不满足要求时，高位-1，当前高位之后的低位都变成9。
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
nstr = str(n)
flag = len(nstr)
for i in range(len(nstr)-2,-1,-1):
if nstr[i+1] < nstr[i]:
flag = i+1
nstr = nstr[:i] + str(int(nstr[i])-1) + nstr[i+1:]
for i in range(flag,len(nstr)):
nstr = nstr[:i] + '9' + nstr[i+1:]
return int(nstr)
968. 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
思路
节点状态分为3种情况，0.无覆盖 1.有摄像头 2.有覆盖，遍历过程中给节点赋予正确的状态。 当节点是摄像头状态时，计数。
- 为什么空节点的状态为2呢，这是因为我们不会在叶子节点放摄像头，而要在叶子节点的父节点放摄像头，如果默认空节点状态为0，则叶子节点必须为1，如果默认空节点状态为1，则叶子节点的父节点就不能放摄像头。所以空节点的状态设为2.
- 注意根节点的特殊处理，即设置完状态后，如果根节点的状态是无覆盖，则还需要在根节点设置摄像头。
class Solution:
def __init__(self) -> None:
self.result = 0
def minCameraCover(self, root: Optional[TreeNode]) -> int:
if self.dfs(root) == 0:
self.result+=1
return self.result
def dfs(self,node: Optional[TreeNode]): # 0.无覆盖 1.有摄像头 2.有覆盖
if not node: return 2
left = self.dfs(node.left)
right = self.dfs(node.right)
if left==2 and right==2: #1.左右孩子都有覆盖
return 0
if left==0 or right==0: #2.左右孩子至少有一个无覆盖
self.result+=1
return 1
if left==1 or right==1: #3.左右孩子至少有一个有摄像头
return 2
return -1 #不会走到这里