代码随想录算法训练营-贪心算法-5|56. 合并区间、738. 单调递增的数字、968. 监控二叉树-526互联

时间复杂度: O(nlogn)
空间复杂度: O(logn)，排序需要的空间开销

 1 class Solution:
 2     def merge(self, intervals):
 3         result = []
 4         if len(intervals) == 0:
 5             return result  # 区间集合为空直接返回
 6 
 7         intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序
 8 
 9         result.append(intervals[0])  # 第一个区间可以直接放入结果集中
10 
11         for i in range(1, len(intervals)):
12             if result[-1][1] >= intervals[i][0]:  # 发现重叠区间
13                 # 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的
14                 result[-1][1] = max(result[-1][1], intervals[i][1])
15             else:
16                 result.append(intervals[i])  # 区间不重叠
17 
18         return result

738. 单调递增的数字

1. 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

2. 从后往前遍历，两位两位进行比较，第一位减1，第二位取最大。

3. flag：标记从哪一位开始后面都变成9。如果没有flag的话，例如1000，会得到900。flag初始值为数组长度-1，要不然样例本身就符合1234，会被9999覆盖。

 1 class Solution:
 2     def monotoneIncreasingDigits(self, N: int) -> int:
 3         # 将整数转换为字符串
 4         strNum = list(str(N))
 5 
 6         # 从右往左遍历字符串
 7         for i in range(len(strNum) - 1, 0, -1):
 8             # 如果当前字符比前一个字符小，说明需要修改前一个字符
 9             if strNum[i - 1] > strNum[i]:
10                 strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1
11                 # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
12                 for j in range(i, len(strNum)):
13                     strNum[j] = '9'
14 
15         # 将列表转换为字符串，并将字符串转换为整数并返回
16         return int(''.join(strNum))

968. 监控二叉树

1. 四种情况。

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution:
 8          # Greedy Algo:
 9         # 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优
10         # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head
11         # 0: 该节点未覆盖
12         # 1: 该节点有摄像头
13         # 2: 该节点有覆盖
14     def minCameraCover(self, root: TreeNode) -> int:
15         # 定义递归函数
16         self.result = 0  # 用于记录摄像头的安装数量
17         if self.traversal(root, self.result) == 0:
18             self.result += 1
19 
20         return self.result
21 
22         
23     def traversal(self, cur: TreeNode, result: List[int]) -> int:
24         if not cur:
25             return 2
26 
27         left = self.traversal(cur.left, result)
28         right = self.traversal(cur.right, result)
29 
30         # 情况1: 左右节点都有覆盖
31         if left == 2 and right == 2:
32             return 0
33 
34         # 情况2:
35         # left == 0 && right == 0 左右节点无覆盖
36         # left == 1 && right == 0 左节点有摄像头，右节点无覆盖
37         # left == 0 && right == 1 左节点无覆盖，右节点有摄像头
38         # left == 0 && right == 2 左节点无覆盖，右节点覆盖
39         # left == 2 && right == 0 左节点覆盖，右节点无覆盖
40         if left == 0 or right == 0:
41             self.result += 1
42             return 1
43 
44         # 情况3:
45         # left == 1 && right == 2 左节点有摄像头，右节点有覆盖
46         # left == 2 && right == 1 左节点有覆盖，右节点有摄像头
47         # left == 1 && right == 1 左右节点都有摄像头
48         if left == 1 or right == 1:
49             return 2