算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

这篇具有很好参考价值的文章主要介绍了算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  算法题

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 = i+1;//更改需要变为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:左右节点都有覆盖

左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。

如图:

算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树,算法,贪心算法,leetcode,数据结构,职场和发展

情况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++

算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树,算法,贪心算法,leetcode,数据结构,职场和发展

class Solution {
    int  res=0;
    public int minCameraCover(TreeNode root) {
        if(minCame(root)==0){// 情况4:对根节点的状态做检验
            res++;
        }
        return res;
    }
    
    public int minCame(TreeNode root){
        if(root==null){ // 空节点默认为 有覆盖状态,避免在叶子节点上放摄像头
            return 2;
        }

        int left=minCame(root.left);
        int  right=minCame(root.right);

        // 情况1:如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if(left==2&&right==2){:
            return 0;

        }else if(left==0||right==0){
            //情况2: 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            res++;
            return 1;// 状态值为 1 摄像头数 ++;

        }else{
            // 情况3:左右节点至少存在 1个摄像头,那么本节点就是处于被覆盖状态
            return 2;
        }
    }
}

时间复杂度:O(n );(遍历整棵树)

空间复杂度:O(n);(数的高度,最差情况下为n)


 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网文章来源地址https://www.toymoban.com/news/detail-852900.html

到了这里,关于算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣第738题 单调递增的数字 c++ 暴力超时 贪心优化

    738. 单调递增的数字 中等 相关标签 贪心  数学 当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数  n  ,返回  小于或等于  n  的最大数字,且数字呈  单调递增  。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 从N开始

    2024年02月08日
    浏览(37)
  • leetcode 738. 单调递增的数字

             这题用暴力法会超时,我就没试了,采用了个挺巧的方法,为了方便需要先将整数n转换为字符串的形式,然后从后向前遍历,当两个数字非递增时,将前一个数字--,后一个数字的位置记录在index中,之后需要将这个index以后的数字全赋为9。  为了防止将不需要赋

    2024年02月14日
    浏览(35)
  • 【Leetcode】 738. 单调递增的数字

    当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是 单调递增 的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 示例 1 : 输入 : n = 10 输出 : 9 示例 2 : 输入 : n = 1234 输出 : 1234 示例3 : 输入 : n = 332 输出 : 299 提示: AC : 需要注意的点

    2024年02月07日
    浏览(36)
  • DAY40:贪心算法(九)单调递增的数字(贪心的思路)

    本题暴力解法也需要看一下,虽然暴力解法超时了,但是这种思路是一种很基础的思路,需要了解 数字是没有办法直接采用下标遍历的 ,如果 要for循环遍历每个位置的数字,需要把数字转成字符串string 当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是

    2024年02月12日
    浏览(49)
  • 单调递增的数字——力扣738

    题目描述 解法

    2024年02月13日
    浏览(36)
  • 贪心算法学习——最长单调递增子序列

    目录 ​编辑 一,题目 二,题目接口 三,解题思路和代码 给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7]  是数组  [0,3,1,6,2,2,7]  的子序列。  

    2024年02月08日
    浏览(42)
  • Day32- 贪心算法part06

    题目一:738. 单调递增的数字  738. 单调递增的数字 当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数  n  ,返回  小于或等于  n  的最大数字,且数字呈  单调递增  。 从高位到低位遍历整数 n 的每一位数字,当

    2024年01月22日
    浏览(46)
  • LeetCode打卡 day58--单调栈

    单调栈的应用, 就是需要构建一个单调递增或者单调递减的栈, 去解决下一个大(小)的元素的问题 题目链接 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请

    2024年02月12日
    浏览(40)
  • 算法刷题Day 37 单调递增的数字+监听二叉树

    两个可能经常要用到的函数 字符串转数字: to_string() 数字转字符串: stoi() 利用树后续遍历,同时加上状态转移的方法,非常值得反复学习

    2024年02月13日
    浏览(35)
  • Day37 贪心算法part06

    前面都想到了,结果最后n[i]给写错了直接写成9了,得把后面的全都改成9才行 摄像头的覆盖范围是上中下 遇到叶子结点,放到叶子结点的父节点 每隔两个空节点放一个摄像头 所以要用后序遍历 把结点分为三个状态:0无覆盖1有摄像头2有覆盖 空节点要设置为有覆盖的状态

    2024年02月19日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包