Day37 贪心算法 part06 738. 单调递增的数字 968. 监控二叉树

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

贪心算法 part06 738. 单调递增的数字 968. 监控二叉树

738. 单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int tag = strNum.size();
        for(int i = strNum.size()-1; i>=1; i--){
            if(strNum[i]<strNum[i-1]){ //不是递增情况,后一位修改成9,前一位-1
                tag =i;
                strNum[i] = '9';
                strNum[i-1]--;
            }
        }
        for(int i = tag; i<strNum.size();i++){ //如果时100的情况,这要有一个标记 否则就是90的错误输出
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

968. 监控二叉树

建议二刷巩固文章来源地址https://www.toymoban.com/news/detail-818369.html

class Solution { //0:无覆盖 1:有摄像头 2:有覆盖
    int result;
    int traversal(TreeNode* cur) { 
    if (cur == nullptr) return 2; // 空节点,该节点有覆盖,方便叶子节点取值
    int left = traversal(cur->left);    // 左
    int right = traversal(cur->right);  // 右
    // 中
    if (left == 2 && right == 2) return 0; //左右节点有覆盖,表示此节点应该为无覆盖
    if (left == 0 || right == 0) { //一旦叶子节点无覆盖,该处添加摄像头
            result++;
            return 1;
    }
    if (left == 1 || right == 1) return 2;  //叶子节点有摄像头,此节点状态为覆盖状态          
    return -1;
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖,非常难想到的特殊情况
            result++;
        }
        return result;
    }
};

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

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

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

相关文章

  • Day37 贪心算法part06

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

    2024年02月19日
    浏览(45)
  • 力扣第738题 单调递增的数字 c++ 暴力超时 贪心优化

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

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

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

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

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

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

    题目描述 解法

    2024年02月13日
    浏览(36)
  • 【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)
  • leetcode 738. 单调递增的数字

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

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

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

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

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

    2024年02月08日
    浏览(40)
  • 算法记录 | Day37 贪心算法

    思路: 1.一旦出现strNum[i - 1] strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。 2.向后遍历 从前向后遍历的话,遇到strNum[i - 1] strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能

    2023年04月22日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包