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

738.单调递增的数字

题目

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

解析

从后向前遍历，就可以重复利用上次比较得出的结果，

出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先让strNum[i - 1]--，然后strNum[i]赋9

Java代码实现

public int monotoneIncreasingDigits(int n) {String[] str = String.valueOf(n).split("");int startFlag = str.length;for (int i = str.length - 1; i > 0; i--) {if (Integer.parseInt(str[i]) < Integer.parseInt(str[i - 1])) {str[i - 1] = String.valueOf(Integer.parseInt(str[i - 1]) - 1);startFlag = i;}}for (int i = startFlag; i < str.length; i++) {str[i] = "9";}return Integer.parseInt(String.join("", str));
}

968.监控二叉树

题目

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

解析

头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

Java代码实现

int result = 0;
/***  节点的状态值：*    0 表示无覆盖*    1 表示 有摄像头*    2 表示有覆盖* @param root 二叉树* @return 最小摄像头数*/
public int minCameraCover(TreeNode root) {if(treeCam(root)==0){result++;}return result;
}private int treeCam(TreeNode root) {if (root == null) {return 2;}int left = treeCam(root.left);int right = treeCam(root.right);if (left == 2 && right == 2) {return 0;} else if (left == 0 || right == 0) {result++;return 1;} else {// 此时至少一个摄像头return 2;}
}