学校的网站是怎么建设的,官网是怎么做的,建设摩托车110报价大全,苏州做网站优化的随想录日记part29 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.28 主要内容#xff1a;今天是学习贪心算法最后一天#xff0c;接下来是针对题目的讲解#xff1a;1.单调递增的数字;2.监控二叉树; 3. 总结
738.单调递增的数字 968.监控二叉树 总结 To…随想录日记part29 t i m e time time 2024.03.28 主要内容今天是学习贪心算法最后一天接下来是针对题目的讲解1.单调递增的数字;2.监控二叉树; 3. 总结
738.单调递增的数字 968.监控二叉树 总结 Topic1单调递增的数字
题目 当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。 给定一个整数 n 返回小于或等于 n 的最大数字且数字呈 单调递增 。 输入 n 10 n 10 n10 输出 9 9 9
思路 思路简单直接看答案。 代码如下
class Solution {public int monotoneIncreasingDigits(int n) {if (n 0 n 9)return n;int count wei(n);int[] nums new int[count];int tem n;for (int i count - 1; i 0; i--) {nums[i] tem % 10;tem tem / 10;}int flag count;for (int i count - 1; i 0; i--) {if (nums[i] nums[i - 1]) {nums[i - 1]--;flag i;}}for (int i flag; i count; i) {nums[i] 9;}int sum 0;for (int i 0; i count; i) {sum sum * 10 nums[i];}return sum;}private int wei(int n) {if (n 10)return 1;int tem n;int result 0;while (tem ! 0) {result;tem tem / 10;}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n) Topic2监控二叉树
题目 给定一个二叉树我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。 输入 [ 0 , 0 , n u l l , 0 , 0 ] [0,0,null,0,0] [0,0,null,0,0] 输出 1 1 1 解释 如图所示一台摄像头足以监控所有节点
思路 从下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少局部最优推出全局最优找不出反例那么就按照贪心来 大体思路就是从低到上先给叶子节点父节点放个摄像头然后隔两个节点放一个摄像头直至到二叉树头结点。 此时这道题目还有两个难点 二叉树的遍历如何隔两个节点放一个摄像头 如何隔两个节点放一个摄像头: 每个节点可能有几种状态有如下三种 该节点无覆盖本节点有摄像头本节点有覆盖 分别有三个数字来表示 0该节点无覆盖 1本节点有摄像头 2本节点有覆盖 递归的终止条件 应该是遇到了空节点此时应该返回2。 单层逻辑处理 【情况1】左右节点都有覆盖 左孩子有覆盖右孩子有覆盖那么此时中间节点应该就是无覆盖的状态了。 【情况2】左右节点至少有一个无覆盖的情况 如果是以下情况则中间节点父节点应该放摄像头 left 0 right 0 左右节点无覆盖 left 1 right 0 左节点有摄像头右节点无覆盖 left 0 right 1 左节点有无覆盖右节点摄像头 left 0 right 2 左节点无覆盖右节点覆盖 left 2 right 0 左节点覆盖右节点无覆盖 【情况3】左右节点至少有一个有摄像头 如果是以下情况其实就是 左右孩子节点有一个有摄像头了那么其父节点就应该是2覆盖的状态 left 1 right 2 左节点有摄像头右节点有覆盖 left 2 right 1 左节点有覆盖右节点有摄像头 left 1 right 1 左右节点都有摄像头 【情况4】头结点没有覆盖 以上都处理完了递归结束之后可能头结点 还有一个无覆盖的情况 整体代码如下 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int result;public int minCameraCover(TreeNode root) {result 0;int tem reback(root);if (tem 0)result;return result;}private int reback(TreeNode root) {// 递归出口if (root null)return 2;int left reback(root.left);int right reback(root.right);// 【情况1】左右节点都有覆盖if (left 2 right 2) {return 0;}// 【情况2】左右节点至少有一个无覆盖的情况if (left 0 || right 0) {result;return 1;}// 【情况3】左右节点至少有一个有摄像头if (left 1 || right 1) {return 2;}return -1;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
