LeetCodeCampsDay31贪心part05

本题目有个和二叉树结合的，值得注意

56. 合并区间

https://leetcode.cn/problems/merge-intervals/

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

贪心思路

和之前几个区间问题比较像，如果区间有重合就将区间合并；如果没有重合，则将上一个区间添加到res里

注意，合并区间时，需要改变区间i的左端点为i-1的左端点；而将i&i-1的右端点变成i&i-1右端点的最大值

贪心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 有重合就合并，没有重合则把上一个区间添加进结果
        res = list()
        intervals.sort(key = lambda x: (x[0], x[1]))

        L = len(intervals)
        for i in range(1, L):
            if intervals[i][0] <= intervals[i - 1][1]:
                intervals[i][0] = intervals[i - 1][0]
                intervals[i][1] = intervals[i - 1][1] = max(intervals[i][1], intervals[i - 1][1])
            else:
                res.append(intervals[i - 1])
        res.append(intervals[-1])
        return res

或者先将第一个区间添加到res里，然后每次只要比较res[-1]的右端点与intervals[i]的左端点就好，并且也只要更新res[-1]的右端点为两个区间右端点最大值

贪心代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 有重合就合并，没有重合则把上一个区间添加进结果
        res = list()
        intervals.sort(key = lambda x: (x[0], x[1]))

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

738. 单调递增的数字

https://leetcode.cn/problems/monotone-increasing-digits/

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

1
2
输入: n = 10
输出: 9

示例 2:

1
2
输入: n = 1234
输出: 1234

示例 3:

1
2
输入: n = 332
输出: 299

提示:

  • 0 <= n <= 109

贪心思路

本题目先将数字变成字符串，方便逐个比较；

以98为例； 若n[i - 1] > n[i] ，首先，令n[i - 1]设置为n[i - 1] - 1；并且将n[i]设置为9，会得到89

那么是从前向后遍历还是从后向前遍历？

如果是从前向后遍历，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

比如332，如果从前向后遍历，先得到329，此时2又小于3不满足情况；如果从后向前遍历，先得到329，再得到299；就对了

注意，在实现的时候，还需要设置个for循环，将9后面的所有数字都设置为9

比如100，会输出090，而不是99，因为最后一个0和倒数第二个0时不会进入if，而第二个0和1会输出090；所以需要记录第一个9出现的位置，再将其后面所有数字都设置为9

贪心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # 
        n_str = list(str(n))
        L = len(n_str)
        if L == 1:
            return n

        for i in range(L - 1, 0, -1):
            if n_str[i - 1] > n_str[i]:
                n_str[i - 1] = str(int(n_str[i - 1]) - 1)
                # 将修改位置后面的字符都设置为9
                # 比如100，会先变成090，（最后一个0和倒数第二个0时不会进入if）
                # 再用for循环将9后面所有数字变成9
                for j in range(i, L):
                    n_str[j] = "9"
        return int("".join(n_str))

或者使用个flag记录设置9的起点位置，省得增加时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # 从后向前遍历，以98为例； 若n[i - 1] > n[i] ，将n[i]设置为9并且令n[i - 1]设置为n[i - 1] - 1
        n_str = list(str(n))
        L = len(n_str)
        if L == 1:
            return n
        flag = L
        for i in range(L - 1, 0, -1):
            if n_str[i - 1] > n_str[i]:
                n_str[i - 1] = str(int(n_str[i - 1]) - 1)
                flag = i
                # 将修改位置后面的字符都设置为9
                # 比如100，会先变成090，（最后一个0和倒数第二个0时不会进入if）
                # 再用for循环将9后面所有数字变成9
        for j in range(flag, L):
            n_str[j] = "9"
        return int("".join(n_str))

968. 监控二叉树

https://leetcode.cn/problems/binary-tree-cameras/

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

img

1
2
3
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

img

1
2
3
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

  1. 给定树的节点数的范围是 [1, 1000]。
  2. 每个节点的值都是 0。

贪心思路

这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。

所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

那么有同学可能问了，为什么不从头结点开始看起呢，为啥要从叶子节点看呢？

因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

局部最优推出全局最优，找不出反例，那么就按照贪心来！

此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

此时这道题目还有两个难点：

  1. 二叉树的遍历
  2. 如何隔两个节点放一个摄像头

一个摄影头可以监控3个节点，并且最好从叶子节点倒着向root节点进行遍历（即使用后序遍历的方法）

此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！

来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：

我们分别有三个数字来表示：

  • 0：该节点无覆盖
  • 1：本节点有摄像头
  • 2：本节点有覆盖

大家应该找不出第四个节点的状态了。

一些同学可能会想有没有第四种状态：本节点无摄像头，其实无摄像头就是 无覆盖 或者 有覆盖的状态，所以一共还是三个状态。

因为在遍历树的过程中，就会遇到空节点，那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？

回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。

那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。

所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

接下来就是递推关系。

那么递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），原因上面已经解释过了。

主要有如下四类情况：

  • 情况1：左右节点都有覆盖

左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

img

  • 情况2：左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头，右节点无覆盖
  • left == 0 && right == 1 左节点有无覆盖，右节点摄像头
  • left == 0 && right == 2 左节点无覆盖，右节点覆盖
  • left == 2 && right == 0 左节点覆盖，右节点无覆盖

这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。

此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

  • 情况3：左右节点至少有一个有摄像头

如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

  • left == 1 && right == 2 左节点有摄像头，右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖，右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头
  • 情况4：头结点没有覆盖

以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：

img

最后，在main函数里，根据rootState判断是否需要再添加一个摄像头

贪心代码

  • 时间复杂度: O(n)，需要遍历二叉树上的每个节点
  • 空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 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 __init__(self):
        self.res = 0

    def foo(self, node):
        if not node:
            # 空节点应该是什么状态？默认把空节点当成被覆盖的状态
            # 目的是让叶子节点的父节点安装摄像头
            return 2
            
        leftState = self.foo(node.left)
        rightState = self.foo(node.right)

        # 左、右至少有一个是无覆盖
        if leftState == 0 or rightState == 0:
            self.res += 1
            return 1
        # 右、右都是有覆盖
        if leftState == 2 and rightState == 2:
            return 0
        # 左、右至少有一个是有摄像头的
        if leftState == 1 or rightState == 1:
            # 根节点被覆盖
            return 2

    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 
        self.root = root
        rootState = self.foo(root)
        # 最后一个情况，root如果还没有被覆盖
        if rootState == 0:
            self.res += 1
        return self.res