临沂网站建设对实体企业,爱是做的电影网站吗,贵港网站制作,小程序开发需要多少钱738.单调递增的数字
题目
738. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字#xff0c;且数字呈 单调递增 。
解析
从后向前遍历#xf…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;}
}
