代码随想录算法训练营Day27 | Leetcode 56. 合并区间、738.单调递增的数字、968.监控二叉树

代码随想录算法训练营Day27 | Leetcode 56.合并区间、738.单调递增的数字、968.监控二叉树

一、合并区间

相关题目：Leetcode56
文档讲解：Leetcode56
视频讲解：Leetcode56

1. Leetcode56. 合并区间

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

• 思路：

  • 本质其实还是判断重叠区间问题，先排序（按左边界或右边界排序都可以），让所有的相邻区间尽可能的重叠在一起。若按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即 intervals[i] 的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（题目指出相邻区间也算重叠，所以是 <=）。如图（按照左边界排序）：
    
  • 相当于用合并区间后的左边界和右边界，作为一个新的区间，加入到 result 数组。如果判断出重叠区间则更新 result 数组中最后的元素的右边界，如果没有合并就把原区间加入到 result 数组。

• 贪心

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

二、单调递增的数字

相关题目：Leetcode738
文档讲解：Leetcode738
视频讲解：Leetcode738

1. Leetcode738.单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
说明: N 是在 [0, 10^9] 范围内的一个整数。

• 思路：

  • 贪心算法：
    • 一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先让 strNum[i - 1]–，然后 strNum[i] 赋值9，倒序从后向前遍历（从前向后遍历无法保证递增）即可。

• 暴力

class Solution:def checkNum(self, num):max_digit = 10while num:digit = num % 10if max_digit >= digit:max_digit = digitelse:return Falsenum //= 10return Truedef monotoneIncreasingDigits(self, N):for i in range(N, 0, -1):if self.checkNum(i):return ireturn 0

• 贪心

##贪心（版本一）
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:# 将整数转换为字符串strNum = str(n)# flag用来标记赋值9从哪里开始# 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行flag = len(strNum)# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:flag = i  # 更新flag的值，记录需要修改的位置# 将前一个字符减1，以保证递增性质strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]# 将flag位置及之后的字符都修改为9，以保证最大的递增数字for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' + strNum[i + 1:]# 将最终的字符串转换回整数并返回return int(strNum)##贪心（版本二）
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:# 将整数转换为字符串strNum = list(str(n))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质for j in range(i, len(strNum)):strNum[j] = '9'# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))##贪心（版本三）
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:# 将整数转换为字符串strNum = list(str(n))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质strNum[i:] = '9' * (len(strNum) - i)# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))##贪心（版本四）精简
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:strNum = str(n)        for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:# 将前一个字符减1，以保证递增性质# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)       return int(strNum)

三、监控二叉树

相关题目：Leetcode968
文档讲解：Leetcode968
视频讲解：Leetcode968

1. Leetcode968.监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其 父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
提示：

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

• 思路：

  • 叶子节点不放摄像头：摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就会浪费一层的覆盖。
  • 从下（叶子结点）往上判断：头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
  • 贪心算法：
    • 局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
    • 整体最优：全部摄像头数量所用最少
  • 大致思路：从下至上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
  • 确定遍历顺序：可以使用后序遍历（左右中），这样就可以在回溯的过程中从下到上进行推导了。
  • 隔两个节点放一个摄像头：有三种不同的情况（可以利用三个数字分别表示）：
    • 本节点无覆盖（0：本节点无覆盖）
    • 本节点有摄像头（1：本节点有摄像头）
    • 本节点有覆盖（2：本节点有覆盖）
  • 空节点的情况：空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了。
  • 递归三部曲：
    • 递归函数的参数与返回值：参数为当前叶节点，返回0,1，2（表示状态）。
    • 终止条件：遇到了空节点，此时应该返回2（有覆盖）。
    • 单层逻辑处理：
      • 情况1（左右节点都有覆盖）：左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
        
      • 情况2（左右节点至少有一个无覆盖）：有一个孩子没有覆盖，父节点就应该放摄像头，此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。
      • 情况3（左右节点至少有一个有摄像头）：其实就是左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）。
      • 情况4（头结点没有覆盖）：递归结束之后，还要判断根节点，如果没有覆盖，result++。
        

• 贪心

class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0]  # 用于记录摄像头的安装数量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left == 2 and right == 2:return 0# 情况2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点无覆盖，右节点有摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖if left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头if left == 1 or right == 1:return 2

• 贪心（利用 elif 精简代码）

class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0]  # 用于记录摄像头的安装数量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left == 2 and right == 2:return 0# 情况2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点无覆盖，右节点有摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖elif left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头else:return 2