代码随想录算法营Day36 ｜ 56. 合并区间，738. 单调递增的数字，968. 监控二叉树

56. 合并区间

每当遇到不重叠的区间就append到结果数组里，遇到重叠的就更新结果数组最后一位的区间的end值。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()res = []for start,end in intervals:if len(res) != 0 and start <= res[-1][-1]:res[-1][-1] = max(end,res[-1][-1])else:res.append([start,end])return res

738. 单调递增的数字

这道题先将数字转成字符列表，然后从后向前遍历该列表，如果i-1的数字大于i的值，我们就对j-1上的数字减去1并且将i更新为新的flag，最后将flag及之后的数字都改成9以维护最大递增的性质。

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

968. 监控二叉树

这道题要让监控最小就是要让那些叶子节点的父节点上安装摄像头。如此我们会有三种节点状态：未覆盖uncovered（0），有摄像头hasMoniter（1），覆盖covered（2）。为了让我们由下至上的去处理节点，我们选用后序遍历左右中，根据左右节点的情况来判断当前节点的情况，如果左右节点有一个是未覆盖状态，那么当前节点就该有摄像头并且增加摄像头数量，如果左右节点有一个有摄像头，那么当前节点就应该是覆盖状态，如果左右节点都是覆盖状态，那么当前节点就应当为未覆盖状态。最后判断一下根节点的状态是否为未覆盖状态，如果是则摄像头数量加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 minCameraCover(self, root: Optional[TreeNode]) -> int:res = 0uncovered = 0hasMoniter = 1covered = 2def traverse(cur):nonlocal resif not cur:return coveredleft = traverse(cur.left)right = traverse(cur.right)if left == uncovered or right == uncovered:res += 1return hasMoniterif left == hasMoniter or right == hasMoniter:return coveredif left == covered and right == covered:return uncoveredif traverse(root) == uncovered:res += 1return res