738. 单调递增的数字
暴力模拟，超时。从后往前遍历，每遇到一个数字就判断是否是单调递增数字。
class Solution {
public int monotoneIncreasingDigits(int n) {
for (int i = n; i > 0; i--) {
int x = i;
// 前一位数
int prev = x % 10;
while (x > 0) {
// 当前位数
int b = x % 10;
if (b > prev) break;
x /= 10;
prev = b;
}
if (x == 0) return i;
}
// 如果 i 是 0 的话，直接返回 0
return 0;
}
}从后往前遍历，当发现前一个数字比当前数字大时，让前一个数字 -1，当前数字变为 9，如果某个数字变成了 9，那么这个数字后面的数字都应该是 9，因此可以立一个 flag，从 flag 开始后面的数字都要变成 9。这里采用字符数组的方式，便于操作每位数字。
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] arr = Integer.toString(n).toCharArray();
// flag 用于标志从哪个下标开始，后面所有的数字都变成 9
// flag 初始化为 arr.length，这样即便没进入第一个 for，没修改 flag，也不会进入第二个 for
int flag = arr.length;
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i - 1] > arr[i]) {
arr[i - 1]--;
flag = i;
}
}
for (int i = flag; i < arr.length; i++) {
arr[i] = '9';
}
return Integer.parseInt(new String(arr));
}
}968. 监控二叉树
贪心思路：摄像头尽量放在中间节点上，这样覆盖的节点是最多的，于是叶子节点不放摄像头，往其父节点放，因此本题采用后序遍历，通过判断左右孩子的状态决定当前节点的状态。
判断的顺序很重要！先判断左右孩子有没有没被覆盖的，有的话就得在当前节点安装摄像头；如果都被覆盖了那还得判断有没有安装摄像头，有安装的话，当前节点就不需要安装了，但是是被覆盖的状态，如果左右孩子都没安装，但是左右孩子已被覆盖，那么当前节点不能安装摄像头，但是需要被覆盖（交由父级处理）。
class Solution {
// 0: 有摄像头
// 1: 无摄像头，但已被覆盖
// 2: 无摄像头，但未被覆盖
int count = 0;
public int minCameraCover(TreeNode root) {
// 如果 root 需要被覆盖，那再加一个摄像头
if (helper(root) == 2) {
count++;
}
return count;
}
// 判断当前节点的状态
public int helper(TreeNode root) {
// 空节点被当作无摄像头，但已被覆盖
// 才可以保证叶子节点是无摄像头，但未被覆盖
if (root == null) return 1;
int left = helper(root.left);
int right = helper(root.right);
// 共有 00 01 02 11 12 22 六种状态
// 先判断左右孩子有没有没覆盖的
// 02 12 22
// 左右孩子有未被覆盖的，需要覆盖，所以安装摄像头
if (left == 2 || right == 2) {
count++;
return 0;
}
// 左右孩子都覆盖了，当前节点就不需要安装摄像头，下面两个判断顺序无所谓，只需要决定当前节点是啥状态就可以
// 11
// 左右孩子都被覆盖了，当前节点不用安装摄像头，但是需要被（父节点）覆盖
if (left == 1 && right == 1) {
return 2;
}
// 00 01
// 左右孩子有人安装了摄像头，那么当前节点不需要安装，且已被覆盖
if (left == 0 || right == 0) {
return 1;
}
return -1;
}
}