代码随想录算法训练营第37天| Leetcode 738.单调递增的数字、968.监控二叉树

本文主要是介绍代码随想录算法训练营第37天| Leetcode 738.单调递增的数字、968.监控二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • Leetcode 738.单调递增的数字
    • Leetcode 968.监控二叉树

Leetcode 738.单调递增的数字

题目链接:Leetcode 738.单调递增的数字
题目描述: 当且仅当每个相邻位数上的数字 xy 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于n的最大数字,且数字呈单调递增 。
思路: 本题数据范围太大了,暴力解法肯定会超时,因此需要借助贪心思想优化。

  1. 如果是0~9的话返回其本身,也就是不需要任何操作
  2. 如果是10~99,我们可以判断十位数字与个位数字的大小,比如73,我们需要做的操作就是7--,然后3变成9,结果为69
  3. 对于三位数及以上数字,可以从后两位开始判断,将其变为单调递增数字(局部最优),再逐渐判断更高一位的数字,最终数字整体变成单调递增数字(全局最优)。

基于以上思路,我们可以发现从后向前遍历数字更适合。这里还有一个小技巧:可以将数字转换成字符串,这样可以轻松获得每一位上的数字。 尽管这样增加了空间复杂度,但是代码更好写了。

代码如下:

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);//字符串更方便操作每一位上的数字//用flag标记从哪个位置之后全赋值为9int flag = s.size();for (int i = s.size() - 1; i > 0; i--) {if (s[i - 1] > s[i]) {flag = i;s[i - 1]--;}}for (int i = flag; i < s.size(); i++) {s[i] = '9';}return stoi(s);}
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

Leetcode 968.监控二叉树

题目链接:Leetcode 968.监控二叉树
题目描述: 给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象

计算监控树的所有节点所需的最小摄像头数量。

思路: 本题可以利用贪心思想,由于二叉树自上向下的节点个数是以指数级别增长,也就是说我们需要尽可能的让摄像头向上放而不聚集在叶子节点,这样可以节省大量摄像头数量,对应的我们需要利用二叉树的后序遍历,只有这样才是从下向上的判断是否需要添加摄像头。

代码如下:

class Solution {
public:int result; //统计摄像头数量// 0代表无覆盖,1代表摄像头,2代表有覆盖int traversal(TreeNode* cur) {//空节点,假设为有覆盖if (cur == nullptr)return 2;int left = traversal(cur->left);int right = traversal(cur->right);//(1)左右孩子都为2,则父节点为0if (left == 2 && right == 2)return 0;//(2)左右孩子至少有一个为0,则父节点为1// left == 0 && right == 0 左右节点无覆盖// left == 1 && right == 0 左节点有摄像头,右节点无覆盖// left == 0 && right == 1 左节点有无覆盖,右节点摄像头// left == 0 && right == 2 左节点无覆盖,右节点覆盖// left == 2 && right == 0 左节点覆盖,右节点无覆盖if (left == 0 || right == 0) {result++;return 1;}//(3)左右孩子至少有一个为1,则父节点为2if (left == 1 || right == 1)return 2;//所有情况已经讨论结束,但是没有这段代码leetcode编译不过return -1;}int minCameraCover(TreeNode* root) {result = 0;//不要漏掉这里:(4)回溯到最后可能根节点未被覆盖if (traversal(root) == 0)result++;return result;}
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

这道题官方题解是动态规划,代码执行的行为类似,不过我感觉还是这种分类讨论+贪心的方法好理解。


总结: 贪心类题目多积累吧,遇到新题目没思路确实不好搞。

最后,如果文章有错误,请在评论区或私信指出,让我们共同进步!

这篇关于代码随想录算法训练营第37天| Leetcode 738.单调递增的数字、968.监控二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/737476

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义