Day 36 卡玛笔记

这是基于代码随想录的每日打卡

56. 合并区间

以数组 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] 可被视为重叠区间。

---

贪心

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x:x[0])res=[]# 初始化为第一个区间startIndex=intervals[0][0]	endIndex=intervals[0][1]for i in range(1,len(intervals)):# 如果当前遍历区间的左边界在上一个区间内，则重叠，更新右边界为最大值if intervals[i][0]<=endIndex:endIndex=max(endIndex,intervals[i][1])else:# 如果不在则存入结果且更新左右边界为新边界res.append([startIndex,endIndex])startIndex=intervals[i][0]endIndex=intervals[i][1]# 遍历完后将最后一次结果存入res.append([startIndex,endIndex])return res

运行结果

---

738. 单调递增的数字

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

贪心

class Solution:"""以32举例，由于第二个数无论取比2小的数：1，0，都不符合单调递增所以只能将第一位数降1，变成2，同时还要满足最大数字这个条件，所以第二位数取为9，变成29从右往左遍历，例如数字为1000时，按照上面的说法只能变为900，然鹅最大数字为999因此设置一个标志位，记录从哪里开始后面都变为9"""def monotoneIncreasingDigits(self, n: int) -> int:digits=list(str(n))flag=len(digits)# 不能从前往后调整，因为可能会破坏前面已调整好的部分for i in range(len(digits)-2,-1,-1):if int(digits[i])>int(digits[i+1]):digits[i]=str(int(digits[i])-1)flag=i+1for i in range(flag,len(digits)):digits[i]='9'return int(''.join(digits))

运行结果

---

968. 监控二叉树

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

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

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

示例 1：

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

示例 2：

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

---

贪心

# 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
"""
状态0表示无覆盖
状态1表示有摄像头
状态2表示有覆盖
局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
"""
class Solution:def __init__(self):self.res=0def minCameraCover(self, root: Optional[TreeNode]) -> int:root=self.traversal(root)# 如果根节点无覆盖，要多记录一个结果if root==0:self.res+=1return self.resdef traversal(self,root):# 递归终止条件，遇到空节点就返回状态2if root==None:return 2left=self.traversal(root.left)    # 左right=self.traversal(root.right)   # 右# 中的处理逻辑# 1.左右都有覆盖,则父节点无覆盖，返回状态0if left==2 and right==2:return 0# 2.左右至少有一个无覆盖,则父节点有摄像头，返回状态1if left==0 or right==0:# 包含左无覆盖，右无覆盖# 左无覆盖，右有摄像头；左无覆盖，右有覆盖# 左有摄像头，右无覆盖；左有覆盖，右无覆盖self.res+=1return 1# 3.左右至少有一个有摄像头，则父节点有覆盖，返回状态2if left==1 or right==1:# 包含左有摄像头，右有摄像头# 左有摄像头，右有覆盖# 左有覆盖，右有摄像头# 没有左有摄像头，右无覆盖和左无覆盖，右有摄像头情况，因为先走的是上面的逻辑，已经包含了return 2

运行结果