算法训练营day31 贪心算法⑤56. 合并区间、738.单调递增的数字 、968.监控二叉树

        贪心算法的最后一篇博客！前面两道题都是比较简单的思路，重点理解一下最后一道题即可。有一说一，进入到贪心算法这一章节之后，我的博客里和代码注释里的内容明显少了很多，因为很多贪心的题目我觉得不需要很复杂的文字说明，很多题解都是很容易理解的内容，可能更多是一种思路的积累吧

56. 合并区间

        重叠问题，弄明白：1.如何判断重叠 2.区间修改逻辑

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        if len(intervals) == 0:
            return result
        intervals.sort(key = lambda x: x[0])# 默认升序
        result.append(intervals[0])
        for i in range(1, len(intervals)):# 左闭右开
            if result[-1][1] >= intervals[i][0]: # 发现重叠
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])
        return result

738.单调递增的数字

        举几个简单的例子：

• 32->29
• 3323->2999
• 1253463->1249999

        总结下来就是

1. 找到“flag”(前一个小于cur，前-1，cur设为9，前一个为flag，遍历查找flag)
2. 将“flag”后面的数字全部设置为9

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        strNum = str(n) # 转换为字符串
        flag = len(strNum)
        for i in range(len(strNum) -1, 0, -1):# 注意这里是0, 因为循环中会比较前一个位置上的元素
            if strNum[i - 1] > strNum[i]:
                flag = i
            # 切片为左闭右开
                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i :]
        for i in range(flag, len(strNum)):
            strNum = strNum[:i] + '9' + strNum[i + 1:]
        return int(strNum) 

968.监控二叉树

        这道题目应该优先从叶子节点开始思考，要尊重后序遍历，不要总是自顶（根节点）向下考虑

# 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:
    # 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优
    # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head
    # 0: 该节点未覆盖
    # 1: 该节点有摄像头
    # 2: 该节点有覆盖
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        result = [0]# 注意使用列表不使用int的原因：python中的参数传递机制
        # 之前博客中讲过，就不在赘述
        if self.traversal(root, result) == 0:# 这个地方可能想不到
            result[0] += 1
        return result[0]

    def traversal(self, cur:TreeNode, result: List[int]) -> int:
        if not cur:
            return 2 # none节点返回2, 才能正常在叶子节点的父节点安装摄像头
        left = self.traversal(cur.left, result)
        right = self. traversal(cur.right, result)

        # 情况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 左节点覆盖，右节点无覆盖
        if left == 0 or right == 0:
            result[0] += 1
            return 1
        
        # 情况3
        if left == 1 or right == 1:
            return 2