【代码随想录算法训练营第三十七天|56.合并区间、738.单调递增的数字、968.监控二叉树】

56.合并区间

先按照右边界对数组排序，然后判断前一个区间的右边界是否大于该区间的左边界，大于的话就说明上一个区间的右边界在该区间内，两个区间有交集，因此把两个区间取成交集后再放回数组中，如果区间没有交集那就放到输出中。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[1])
        new_intervals = []
        while len(intervals)>1:
            if intervals[-1][0] > intervals[-2][1]:
                new_intervals.append(intervals.pop())
            else:
                intervals[-2][1] = intervals[-1][1]
                intervals[-2][0] = min(intervals[-2][0], intervals[-1][0])
                intervals.pop()
        new_intervals.append(intervals[0])
        return new_intervals

738.单调递增的数字

一种是按照贪心的方法，从后往前找，如果前面的值大于当前的值就把前值减1，并设置一个flag为当前的索引，在遍历完毕后把flag及后面的值都赋值为9.
另一种从前往后，找到当前值大于后面值的就设置当前索引为flag，然后需要判断前值是否与当前值相等，一直要找到第一个相等的值的位置，让这个位置的值-1，并把flag设置在那个位置，然后把flag及后面的值都赋值为9.

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

968.监控二叉树

二叉树在添加相机的过程中一共可能有三种状态，第一种是已经被相机监控了，一种是不在监控范围，一种是放了相机。如果子结点都是被监控的，那么该节点就是在监控范围外，返回0，如果子节点有一个没被监控，那就要在这个节点上放上相机，其余情况下都是返回被监控状态。但是根节点如果是0，那就没办法在往上放相机，所以要再外部判断根节点是否为0，为0的话再放一个相机。

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.cam = 0
        if self.traversal(root) == 0:
            self.cam += 1
        return self.cam
    def traversal(self, root):
        if root == None:
            return 2
        left = self.traversal(root.left)
        right = self.traversal(root.right)
        if left == 2 and right == 2:
            return 0
        if left == 0 or right == 0:
            self.cam += 1
            return 1
        return 2