计量检测网站平台建设方案,我国空间站建造,扫码点餐小程序,网站上传空间的ip地址吗算法题
Leetcode 738.单调递增的数字
题目链接:738.单调递增的数字 大佬视频讲解#xff1a;单调递增的数字视频讲解 个人思路 这个题目就是从例子中找规律#xff0c;例如 332#xff0c;从后往前遍历#xff0c;32不是单调递增将2变为9,3减1#xff0c;变成了329… 算法题
Leetcode 738.单调递增的数字
题目链接:738.单调递增的数字 大佬视频讲解单调递增的数字视频讲解 个人思路 这个题目就是从例子中找规律例如 332从后往前遍历32不是单调递增将2变为9,3减1变成了329遍历到2,32不是递增将2变为9,3减1变成299符合题目条件打印输出。 解法
贪心法
这道题只能从后往前遍历因为如果是从前向后遍历的话拿例子332看第一步变成了292第二步变成了289并不是真正的结果299。
而从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299确定了遍历顺序之后发现局部最优就可以推出全局可以用贪心 class Solution {public int monotoneIncreasingDigits(int n) {String s String.valueOf(n);//int变为字符串char[] chars s.toCharArray();//转为字符数组int start s.length();//从后往前遍历 for (int i s.length() - 2; i 0; i--) {if (chars[i] chars[i 1]) {//不符合单调递增 chars[i]--;//元素减一start i1;//更改需要变为9的位置}}for (int i start; i s.length(); i) {chars[i] 9;}return Integer.parseInt(String.valueOf(chars));//转为integer类型}
} 时间复杂度:O(n)遍历字符串中的每个字符 空间复杂度:O( 1);无动态使用空间 Leetcode 968.监控二叉树
题目链接:968.监控二叉树
大佬视频讲解监控二叉树视频讲解 个人思路
一整个难住看看题解... 解法
贪心法
根据题目所给例子知道摄像头不能安装到叶子节点因为这样会浪费一层监控空间所以安装摄像头从下往上考虑先给叶子节点父节点放个摄像头然后隔两个节点放一个摄像头直至到二叉树头结点. 下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少局部最优可以推出全局最优找不出反例用贪心 1.确定遍历顺序 二叉树从低向上推导可以使用后序遍历左右中 在遍历时取了左孩子的返回值右孩子的返回值 以便推导中间节点的状态 2.隔两个节点放一个摄像头状态分析
每个节点可能有如下三种状态可以分别有三个数字来表示
该节点无覆盖 - 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 左节点覆盖右节点无覆盖 有一个孩子没有覆盖父节点就应该放摄像头摄像头的数量要加一并且return 1代表中间节点放摄像头。 情况3左右节点至少有一个有摄像头
如果是以下情况其实就是 左右孩子节点有一个有摄像头了那么其父节点就为2覆盖的状态
left 1 right 2 左节点有摄像头右节点有覆盖left 2 right 1 左节点有覆盖右节点有摄像头left 1 right 1 左右节点都有摄像头 情况4头结点没有覆盖
递归结束之后可能头结点 还有一个无覆盖的情况如下图所以递归结束之后还要判断根节点如果没有覆盖result class Solution {int res0;public int minCameraCover(TreeNode root) {if(minCame(root)0){// 情况4对根节点的状态做检验res;}return res;}public int minCame(TreeNode root){if(rootnull){ // 空节点默认为 有覆盖状态避免在叶子节点上放摄像头return 2;}int leftminCame(root.left);int rightminCame(root.right);// 情况1如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头if(left2right2){:return 0;}else if(left0||right0){//情况2 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头res;return 1;// 状态值为 1 摄像头数 ;}else{// 情况3左右节点至少存在 1个摄像头那么本节点就是处于被覆盖状态return 2;}}
} 时间复杂度:O(n )遍历整棵树 空间复杂度:O(n);数的高度最差情况下为n 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
