时光慢网站建设方案论文,手机ppt在哪个网站做,遵义创意网站设计,2014年沈阳建设银行网站今日任务#xff1a; 1#xff09;738.单调递增的数字 2#xff09;968.监控二叉树 738.单调递增的数字
题目链接#xff1a;738. 单调递增的数字 - 力扣#xff08;LeetCode#xff09;
文章讲解#xff1a;代码随想录 (programmercarl.com)
视频讲解#xff1a;贪… 今日任务 1738.单调递增的数字 2968.监控二叉树 738.单调递增的数字
题目链接738. 单调递增的数字 - 力扣LeetCode
文章讲解代码随想录 (programmercarl.com)
视频讲解贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字哔哩哔哩bilibili
思路 这个问题的解题思路是通过从右往左遍历数字找到第一个比右边数字大的位置 i然后将位置 i 上的数字减一并将位置 i 右侧的所有数字都变成9。这样可以保证最终得到的数字是小于或等于原始数字的最大单调递增数字。 具体的步骤如下 将整数转换为数字列表便于按位处理。从倒数第二个位置开始向左遍历字符串列表直到第一个位置。在遍历过程中如果当前数字比后一个数字大说明需要将当前数字减一并将后面的数字全部置为9。最后将列表转换为整数并返回。 通过这样的操作可以确保得到的数字是小于或等于原始数字的最大单调递增数字。 class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:# 如果区间集合为空返回0if not intervals:return 0intervals.sort(keylambda x: x[0])# 初始化移除区间的数量为0remove_count 0# 初始化上一个不重叠区间的结束位置为第一个区间的结束位置end intervals[0][1]for i in intervals[1:]:# 存在重叠区间if i[0] end:# 更新重叠区间的右边界:选一个结束位置小的区间减少重叠end min(i[1],end)remove_count 1else:end i[1]return remove_count 968.监控二叉树
题目链接968. 监控二叉树 - 力扣LeetCode
文章讲解代码随想录 (programmercarl.com)
视频讲解贪心算法二叉树与贪心的结合有点难...... LeetCode:968.监督二叉树哔哩哔哩bilibili
思路 对于每个节点考虑其三种状态 状态0表示当前节点没有被覆盖。状态1表示当前节点有摄像头。状态2表示当前节点被覆盖但没有摄像头。 采用后序遍历左-右-根的方式遍历二叉树 左右节点至少有一个无覆盖的情况如果左子节点或右子节点的状态为0未被覆盖则当前节点需要放置摄像头状态1。左右节点至少有一个有摄像头如果左子节点或右子节点的状态为1有摄像头则当前节点已经被覆盖状态2。 left 1 right 2 左节点有摄像头右节点有覆盖left 2 right 1 左节点有覆盖右节点有摄像头left 1 right 1 左右节点都有摄像头左右节点都有覆盖如果左子节点且右子节点的状态为2被覆盖但没有摄像头则当前节点不需要放置摄像头但需要标记为未被覆盖状态0。 对于根节点如果其状态为0则需要额外放置一个摄像头状态1。 统计放置的摄像头数量即为所需的最小摄像头数量。 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
感想
有点难情况比较多。仅理解。
