【随想录】Day37—第八章贪心算法 part06

本文主要是介绍【随想录】Day37—第八章贪心算法 part06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1: 单调递增的数字

题目链接：738. 单调递增的数字

1- 思路

1. 转 String：将 int 类型的数转为 String 类型，之后通过
2. 逆向遍历：从后往前遍历 String
3. 处理思路：从 size()-2 遍历到 i >= 0
- 处理情况：当当前元素 i 的元素值大于后一位 i+1 ，此时需要处理
- 处理逻辑：令 i 的元素值为当前元素值减一，同时定义 start 记录 i 的位置

2- 题解

⭐ 单调递增的数字——题解思路

在这里插入图片描述

class Solution {public int monotoneIncreasingDigits(int n) {String str = Integer.toString(n);char[] chars = str.toCharArray();int start = str.length();for (int i = str.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for(int i = start ; i<chars.length ;i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

题目2: 监控二叉树

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

1- 思路

贪心思路

通过从下网上遍历的方式，则采取二叉树的 后序遍历 ，即左右中方式
在叶子结点的上一个结点放摄像头，每隔两个结点放一个摄像头，直到遍历到根节点为止

定义结点状态

0 代表这个结点没覆盖
1 代表这个结点有摄像头
2 代表当前这个结点有覆盖的状态
空节点一定是有覆盖状态，才能满足叶子结点的父节点是有摄像头

后续遍历逻辑

情况1：左右孩子都有覆盖 ——> 父节点只能是状态0，等待父节点的父节点装摄像头
情况2：左右孩子至少有一个无覆盖 ——> 此时父节点必须要装一个摄像头，只有父节点装了摄像头才能将当前结点的另一个孩子给覆盖
情况3：左右孩子有一个有摄像头 ——> 此时父节点一定是覆盖状态
情况4：根节点无覆盖 ——> 此时要对根节点加一个摄像头

2- 题解

⭐ 监控二叉树——题解思路

在这里插入图片描述

class Solution {int res = 0;public int minCameraCover(TreeNode root) {if(Traversal(root)==0){res++;}return res;}public int Traversal(TreeNode root){if(root== null){return 2;}int left = Traversal(root.left);int right = Traversal(root.right);// 左右孩子都覆盖if(left==2 && right==2){return 0;}// 左右至少有一个无覆盖if(left==0 || right==0){res++;return 1;}// 左右有一个摄像头，当前被覆盖if(left==1 || right==1){return 2;}return -1;}
}