LeetCodeCampsDay31贪心part05
本题目有个和二叉树结合的，值得注意
56. 合并区间
https://leetcode.cn/problems/merge-intervals/
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
贪心思路
和之前几个区间问题比较像，如果区间有重合就将区间合并；如果没有重合，则将上一个区间添加到res里
注意，合并区间时，需要改变区间i的左端点为i-1的左端点；而将i&i-1的右端点变成i&i-1右端点的最大值
贪心代码
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]的右端点为两个区间右端点最大值
贪心代码二
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 res738. 单调递增的数字
https://leetcode.cn/problems/monotone-increasing-digits/
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9示例 2:
输入: n = 1234
输出: 1234示例 3:
输入: 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
贪心代码
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的起点位置，省得增加时间复杂度
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：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。提示：
- 给定树的节点数的范围是
[1, 1000]。 - 每个节点的值都是 0。
贪心思路
这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。
所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
那么有同学可能问了，为什么不从头结点开始看起呢，为啥要从叶子节点看呢？
因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！
局部最优推出全局最优，找不出反例，那么就按照贪心来！
此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
此时这道题目还有两个难点：
- 二叉树的遍历
- 如何隔两个节点放一个摄像头
一个摄影头可以监控3个节点，并且最好从叶子节点倒着向root节点进行遍历（即使用后序遍历的方法）
此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！
来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
我们分别有三个数字来表示：
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
大家应该找不出第四个节点的状态了。
一些同学可能会想有没有第四种状态：本节点无摄像头，其实无摄像头就是 无覆盖 或者 有覆盖的状态，所以一共还是三个状态。
因为在遍历树的过程中，就会遇到空节点，那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？
回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。
那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。
所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了
接下来就是递推关系。
那么递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），原因上面已经解释过了。
主要有如下四类情况：
- 情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
- 情况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：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
最后，在main函数里，根据rootState判断是否需要再添加一个摄像头
贪心代码
- 时间复杂度: O(n)，需要遍历二叉树上的每个节点
- 空间复杂度: O(n)
# 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- 文章作者:
- Lthero博客
- 版权声明:
- 本博客所有文章除特别声明外，均采用CC BY-NC-SA 4.0许可协议。转载请注明来自 Lthero博客！
