Day 37 贪心算法 6

这篇具有很好参考价值的文章主要介绍了Day 37 贪心算法 6。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

738. 单调递增的数字 

代码随想录 

1. 思路

从后向前判断,如果不呈现单调递增的状态,后一位变成9,前一位-1。这里局部最优是每两位的最优解,从后向前线性遍历能得到全局最优。

但是有一点没有想清楚。如果出现了上述的两位数倒序情况,之后的所有数字都应该变成9。例如52583,最小的递增数是49999。中间三位其实是递增的,但是在52调整成49后,后续的所有数都应该是9,因此应该是在从头开始最先出现倒序之后全部调整成9。

方法是记录flag。flag对于多重线性完成的任务有效果,先记录,最后再遍历一遍完成调整。

至于为什么从头开始最先出现倒序但不从头开始遍历,就是因为调整的过程依赖于后面的数字(如果倒序,前一位-1),因此必须从后向前遍历。

2. 方法

巧用to_string和stoi,并且,因为整数str的asc码也是连续的,因此'9'-1 = ‘8’。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strnum = to_string(n);
        int flag = strnum.size();
        for(int i = strnum.size()-1; i>0; i--){
            if(strnum[i-1]>strnum[i]){
                flag = i;
                strnum[i-1]--;
            }
        }
        for(int i=flag; i<strnum.size(); i++){
            strnum[i] = '9';
        }
        return stoi(strnum);
    }
};

 

968. 监控二叉树

1. 思路

本题的核心思路为,从叶子到源头进行二叉树搜索,满足下面的尽量不放摄像头这个原则。回溯至源头后,摄像头的个数就是最少的。严格的数学证明有些困难,也不必要。

如何判断是否该放置摄像头,可以通过叶子的状态来判断。分别是:

1-有摄像头,2-有覆盖,0-没有覆盖

(1)如果孩子都有覆盖,不放摄像头。注意它的前提是,可以被再往上的摄像头覆盖。因此头节点可能因为这种情况而丢失覆盖,因为没有再往上的节点了。因此,需要最后判断头节点有没有被覆盖。

(2)如果有一个孩子没有覆盖,放摄像头。

(3)如果有一个孩子有摄像头,不放摄像头,但改成被覆盖。

最后,叶子之下的空节点,由于不想让叶子被放摄像头,呈现没有被覆盖但没有摄像头的状态,因此将空节点调成全部被覆盖。注意不能在叶子节点下面放摄像头,因为想让叶子呈现空状态。

class Solution {
public:
    int result;
    int traversal(TreeNode* cur){
        if(cur==NULL) 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;
    }
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

 文章来源地址https://www.toymoban.com/news/detail-791105.html

到了这里,关于Day 37 贪心算法 6的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

    建议二刷巩固

    2024年01月23日
    浏览(44)
  • 【LeetCode题目详解】第八章 贪心算法 part06 738.单调递增的数字 968.监控二叉树 (day37补)

    当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 # 暴力解法 题意很简单,那么首先想的就是暴力解法了,来我替大家

    2024年02月10日
    浏览(41)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

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

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

    2024年02月13日
    浏览(36)
  • #算法记录 | Day33 贪心算法

    如果加油站提供的油总和大于等于消耗的汽油量,则必定可以绕环路行驶一周 假设先不考虑油量为负的情况,我们从「第 0 个加油站」出发,环行一周。记录下汽油量 gas[i] 和 cost[i] 差值总和 sum_diff,同时记录下油箱剩余油量的最小值 min_sum。 如果差值总和 sum_diff 0,则无论

    2023年04月18日
    浏览(41)
  • day27 贪心算法

    1.什么是贪心? 比如10张钞票,有1,5,20,100等面额,取五张,如何取得到数额最多的钱?每次取面额最大的那张钞票;就是每个阶段的局部最优;全局最优就是最后拿到的钞票数最大;局部最优推出全局最优; 题目描述 题目描述 题目描述 分析:摆动序列,就是前后相减保

    2024年02月16日
    浏览(34)
  • 贪心算法练习day.1

    贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即 贪心地做出局部的最优决策,以此得到全局的最优解, 例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要

    2024年04月27日
    浏览(36)
  • day 34 贪心算法

    1005.K次取反后最大化的数组和 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小 第二步:从前向后遍历,遇到负数将其变为正数,同时K– 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完 第四步:求和 134. 加油站 暴力求解, 从每一个位

    2024年02月11日
    浏览(36)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

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

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

    2024年02月12日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包