代码随想录算法训练营 Day 27

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        
        # 按照起始位置正序排列，这样第一个起始位置才会在最左边
        intervals.sort(key=lambda x:x[0])

        res = []
        left = intervals[0][0]
        right = intervals[0][1]

        for i in range(1, len(intervals)):
            if intervals[i][0] > right:
                res.append([left, right])
                left = intervals[i][0]
                right = intervals[i][1]
            else:
                right = max(right, intervals[i][1])
        
        res.append([left, right])

        return res

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        str_n = list(str(n))
        l = len(str_n)

        for i in range(l - 1, 0, -1):
            if str_n[i - 1] > str_n[i]:
                str_n[i - 1] = str(int(str_n[i - 1]) - 1)
                # 修改前一位数字可能会影响单调性（特殊情况：1001）
                str_n[i:] = '9' * (l - i)
        
        return int(''.join(str_n))

class Solution:
    def __init__(self):
        self.res = 0
    
    # 定义三种状态：0 - 未被覆盖；1 - 摄像头；2 - 被覆盖
    def postTraversal(self, node):
        if not node:
            return 2
        left_status = self.postTraversal(node.left)
        right_status = self.postTraversal(node.right)

        # 左右都是被覆盖的情况（达到覆盖的最大范围），当前节点设置为未被覆盖
        if left_status == 2 and right_status == 2:
            return 0
        
        # 有一个孩子未被覆盖，必须得在当前设置摄像头
        if left_status == 0 or right_status == 0:
            self.res += 1
            return 1
        
        # 有一个孩子设置了摄像头，当前节点处于覆盖状态
        if left_status == 1 or right_status == 1:
            return 2
        
        return -1

    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        # 还需要判断根节点的状态
        if(self.postTraversal(root) == 0):
            self.res += 1

        return self.res