代码随想录算法训练营第三十一天 | 56.合并区间 738.单调递增的数字 968.监控二叉树

LeetCode 56.合并区间：

文章链接
题目链接：56.合并区间

思路：

① 合并所有重叠的区间，合并后的区间数组不重叠，因此下面两种多区间重叠，其中的区间都要进行合并
在这里插入图片描述
② 合并区间：因为情况2也算作是重叠区间，因此采用先按左端点顺序排列，再求重叠区间最大右端点的方式。（顺序的话判断重叠是左端点是否小于重叠的最大右端点；逆序排列的话是右端点是否大于重叠的最小左端点）
逆序如下图：
在这里插入图片描述
③ 具体代码实现

使用left和maxRight记录合并后区间的左端点和最大右端点，当下一个区间不重叠时将[left, maxRight]加入result中
需要注意的是： for循环遍历完成后，result中还有一个区间没有加入

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:if len(intervals) <= 0:return []intervals.sort(key=lambda x:x[0])   # 按左端点排序left = intervals[0][0] # 当前重叠区间合并后的左端点maxRight = intervals[0][1]    # 最大重叠区间右端点result = []for i in range(1, len(intervals)):if intervals[i][0] > maxRight:  # 不重叠result.append([left, maxRight])# 重置重叠区间左右端点left = intervals[i][0]maxRight = intervals[i][1]else:maxRight = max(maxRight, intervals[i][1])# 最后还有一个result.append([left, maxRight])return result

区间不重叠时直接将其加入result中，后面判断重叠的话再进行合并，合并方式是更新其最大右端点。数组是按照左端点排序的，因此区间的左端点就是最小左端点

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:if len(intervals) <= 0:return []intervals.sort(key=lambda x:x[0])   # 按左端点排序result = [intervals[0]] # 将第一个元素加入result中for i in range(1, len(intervals)):if intervals[i][0] <= result[-1][1]:    # 重叠result[-1][1] = max(result[-1][1], intervals[i][1]) # 更新右端点，左端点一定是最小的，因为是按照左端点排序else:result.append(intervals[i]) # 将区间加入列表中return result

感悟：

首先分析清楚需要的判断的重叠情况，然后根据排序遍历方式怎么判断是否重叠；最后记录的方式是使用两个额外的变量记录还是就使用result的最后一个元素记录。
只要是顺序排列（无论是按左端点还是右端点），从前往后遍历的话，都是判断新左端点是否小于重叠右端点。逆序遍历方式相同，判断重叠是新右端点是否大于重叠左端点

LeetCode 738.单调递增的数字：

文章链接
题目链接: 738.单调递增的数字

思路：

遇到 nums[i - 1] > nums[i]，将nums[i - 1] -= 1，然后num[i:]全部修改为9。
那么可以采用的遍历方式为从前往后和从后往前

从前往后
从前往后的话，如果nums[i] > nums[i + 1]，nums[i ] -= 1之后，可能导致nums[i - 1] > nums[i]，因此我们找到的解决办法为：
① 因为nums[i] -= 1之后如果出现nums[i - 1] > nums[i]的情况的话，只可能为nums[i]修改前，nums[i] == nums[i - 1]。
② 因此我们找到nums[i] > nums[i + 1]之后，从 i 开始向前找，直到nums[i] != nums[i - 1]，那么这个下标 i 对应的值就是 - 1的正确位置，nums[i:]都修改为9
③ 此处将后面修改为9的方式为，以333332举例，3*(10^5) - 1

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:if n < 10:return nnums = []count, newN = 0, n  # 记录nums元素个数，即n的位数while newN > 0:nums.append(newN % 10)newN = newN // 10count += 1nums = nums[::-1]# 找到修改的下标的正确位置index = 0while index < count - 1 and nums[index] <= nums[index + 1]:index += 1if index == count - 1:  # n是单调递增的return nelse:   # # 从index向前找，直到数字不相同while index > 0 and nums[index] == nums[index - 1]:index -= 1# 构造单调递增且小于n的最大整数res = 0for i in range(0, index + 1):res = res * 10 + nums[i]res *= pow(10, count - 1 - index)res -= 1    # 即nums[index] -= 1，nums[index:]全为9return res

从后向前遍历
从后向前遍历的话，nums[i - 1] > nums[i]，从而nums[i - 1] -= 1，再向前遍历时能够用到新的nums[i - 1]进行判断，同时使用flag记录修改为9的开始位置。

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:if n < 10:return nstrN = list(str(n))   # 将整数转换为字符串列表flag = len(strN)    # flag设置9从哪里开始，初始化为len(strN)防止flag没被赋值时循环赋9开始# 从后往前遍历for i in range(len(strN) - 1, 0, -1):if strN[i - 1] > strN[i]:flag = i    # 9开始的位置strN[i - 1] = str(int(strN[i - 1]) - 1)# 以flag开始的位置都赋值为9for i in range(flag, len(strN)):strN[i] = '9'# 将列表转换为字符串后再转换为整数res = int(''.join(strN))return res

感悟：

① 字符串可以通过索引访问，但是不能通过索引修改。如果想要修改的话，使用list()将其转换为列表后修改
② 从列表转换回字符串为’‘.join(list1)，join前面的’'的两个单引号之间的元素为将列表转换为字符串时，列表中每个元素之间衔接的元素
③ 整数转换为字符串，或者数字字符串转换为整数直接转换即可

LeetCode 968.监控二叉树：

文章链接
题目链接：968.监控二叉树

思路：

本道题很难，具体思路分为多个方面
1）用到了贪心：因为给一个节点放摄像头可以覆盖的范围有上中下，因此我们应当给叶子节点的parent节点放摄像头(为了覆盖叶子节点且摄像头覆盖范围更大)。那么接着继续向上推，此时，因为parent节点放了摄像头，因此parent.parent被覆盖了，为了摄像头数目更少，即摄像头覆盖范围更广，因此我们对放了摄像头parent向上间隔两个节点再放摄像头。
在这里插入图片描述
2）根据上面的贪心，二叉树的遍历方式应当为后序遍历。那么二叉树的节点一共有三种状态，分别为0：无覆盖，1：有摄像头，2：有覆盖。
3）那么后序遍历根据左右孩子的状态，那么parent节点应当为什么状态也有多种情况。

3.1 情况1：左右孩子均为有覆盖
那么parent节点应当为状态0，无覆盖的情况返回给上一层，从而上一层的parent节点会放置摄像头来覆盖。
3.2 情况2：左右孩子至少有一个无覆盖
那么parent节点应当被放置摄像头来覆盖到左右孩子，即parent节点为状态1
3.3情况3：左右孩子至少有一个有摄像头（且没有无覆盖的情况）
那么parent节点应当为状态2，有覆盖。
3.4情况4遍历完成后根节点无覆盖
因为我们的贪心思路是放置摄像头后隔两个节点再放置摄像头，那么对于下面这种情况。根节点在遍历完成后仍然是无覆盖的情况，此时需要在根节点也放置摄像头。

最后：采用的是递归的后序遍历，函数返回值为当前节点的状态，边界条件为空节点，那么空结点也需要对应的状态来返回。
- 如果空结点返回0，那么其parent节点如果是叶子节点的话，一定会被放置摄像头，与贪心相违背。
- 如果空结点返回1，那么其parent节点如果是叶子节点的话，状态为2（有覆盖），那么叶子节点的parent节点不会被放置摄像头，与贪心相违背
- 因此，空节点只能返回2，有覆盖，那么其parent节点如果为叶子节点不会被放置摄像头，但是叶子节点的parent节点会被放置摄像头；如果其parent节点不是叶子节点的话，parent节点能够根据其存在的孩子节点的状态确定自己的状态，并且不会收到空节点影响

# 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 minCameraCover(self, root: Optional[TreeNode]) -> int:self.result = 0if self.traversal(root) == 0:   # 情况4，遍历完成后根节点还是无覆盖self.result += 1return self.resultdef traversal(self, node):if not node:return 2left = self.traversal(node.left)    # 左right = self.traversal(node.right)  # 右# 根if left == 2 and right == 2:return 0if left == 0 or right == 0:self.result += 1return 1if left == 1 or right == 1:return 2return -1