代码随想录第31天

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda p: p[0])  # 按照左端点从小到大排序ans = []for p in intervals:if ans and p[0] <= ans[-1][1]:  # 可以合并ans[-1][1] = max(ans[-1][1], p[1])  # 更新右端点最大值else:  # 不相交，无法合并ans.append(p)  # 新的合并区间return ans

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:nums = list(str(N))length = len(nums)begin = 0# N 是否符合条件is_result = Truemax_num = float('-inf')# 从前往后观察for i in range(1, length):num = int(nums[i])pre_num = int(nums[i - 1])# 记录最大值if pre_num > max_num:begin = i - 1max_num = pre_numif pre_num > num:is_result = Falsebreak# 如果 N 本身符合条件，直接返回 Nif is_result:return N# begin 位置减去 1，后面全部替换为 9nums[begin] = str(int(nums[begin]) - 1)for i in range(begin + 1, length):nums[i] = '9'return int("".join(nums))

class Solution:def minCameraCover(self, root: Optional[TreeNode]) -> int:def dfs(node):if node is None:return inf, 0, 0  # 空节点不能安装摄像头，也无需被监控到l_choose, l_by_fa, l_by_children = dfs(node.left)r_choose, r_by_fa, r_by_children = dfs(node.right)choose = min(l_choose, l_by_fa) + min(r_choose, r_by_fa) + 1by_fa = min(l_choose, l_by_children) + min(r_choose, r_by_children)by_children = min(l_choose + r_by_children, l_by_children + r_choose, l_choose + r_choose)return choose, by_fa, by_childrenchoose, _, by_children = dfs(root)  # 根节点没有父节点return min(choose, by_children)