代码随想录算法训练营第三十二天|738.单调递增的数字，968.监控二叉树，总结

作者：从前慢现在也慢 | 2024-04-14 15:55:35

踩

系列文章目录

文章目录

系列文章目录
738.单调递增的数字
968.监控二叉树
总结

738.单调递增的数字

题目链接： 738.单调递增的数字
题目内容： 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增。
视频讲解： 贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字

思路：从后往前遍历数字的每一位，如果出现有不递增的情况，则将前一位减1，后一位换成9.

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
    
        strnum=str(n)# 设置为字符串长度，防止第二个for循环在flag没有被赋值的情况下执行
        flag=len(strnum)# flag用来标记赋值9从哪里开始
        
        for i in range(len(strnum)-1,0,-1):
            if strnum[i]<strnum[i-1]:
                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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

968.监控二叉树

题目链接： 968.监控二叉树
题目内容： 给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。
视频讲解： 贪心算法，二叉树与贪心的结合，有点难… LeetCode:968.监督二叉树

思路：

摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
要想实现隔两个节点放一个摄像头，需要在遍历节点的同时确定该节点的状态，在后续操作时，依次根据左右节点的状态来确定根节点的状态。

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] += 1

        return result[0]

        
    def traversal(self, cur: TreeNode, result: List[int]) -> int:
        if not cur:
            return 2

        left = 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] += 1
            return 1

        # 情况3:
        # left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        # left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        # left == 1 && right == 1 左右节点都有摄像头
        if left == 1 or right == 1:
            return 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

总结

贪心无套路，也没有框架之类的，需要多看多练培养感觉才能想到贪心的思路；
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/422893