Day33第八章贪心算法part06

一. 学习文章及资料 738.单调递增的数字 968.监控二叉树 总结 二. 学习内容

1. 单调递增的数字

(1) 解题思路：

题目要求小于等于N的最大单调递增的整数，那么我们通过识别需要调整的位置，并将后续的数字设置为 9，从而构造出满足条件的最大数字

(2) 解题步骤：

       class Solution { public int monotoneIncreasingDigits(int n) { String s=String.valueOf(n); // 将整数转换为字符串 char[] c=s.toCharArray(); int start=s.length(); // 初始化起始位置 // 从后往前遍历，找到需要调整的位置 for(int i=s.length()-2;i>=0;i--){ if(c[i]>c[i+1]){ c[i]--; // 当前字符减1 start=i+1; // 记录后续需要设置为9的起始位置 } } // 将起始位置到末尾的字符设置为9 for(int i=start;i<s.length();i++){ c[i]='9'; } return Integer.parseInt(String.valueOf(c)); } }

2. 监控二叉树

(1) 解题思路：

用于解决“为二叉树安装最少的摄像头，使得所有节点都被监控到”的问题。代码的逻辑是通过递归遍历二叉树，并根据节点的状态（有无覆盖、是否有摄像头）来决定如何放置摄像头。

(2) 解题步骤：

             

class Solution { int result=0;// 用于记录摄像头的数量 // 递归函数，返回当前节点的状态 int traversal(TreeNode cur){ // 空节点，有覆盖 if(cur==null) return 2; int left=traversal(cur.left); // 处理左子节点 int right=traversal(cur.right);// 处理右子节点 // 情况1：左右子节点都被覆盖（2） if(left==2&&right==2) return 0;// 当前节点未被覆盖 // 情况2：左右子节点至少有一个未被覆盖（0） if(left==0||right==0){ result++; return 1;// 安装后返回状态1 } // 情况3：左右子节点至少有一个安装了摄像头（1） if(left==1||right==1) return 2; return -1;// 当前节点被覆盖 } public int minCameraCover(TreeNode root) { // 处理根节点的情况 if(traversal(root)==0){ result++;// 根节点未被覆盖，需要安装摄像头 } return result; // 不会走到这里，代码中的逻辑已经覆盖了所有情况 } }

3. 总结