算法训练营第三十九天 | LeetCode 738 单调递增的数字、LeetCode 968 监控二叉树
LeetCode 738 单调递增的数字
这题类似模拟,可以找出如下规律:
先将数字按位数从高位到低位存到一个整型数组中。在这个数组中,从左往右遍历,如果遇到一个两数相等,并且记录的这个变量之前没有赋过值,那么将前一个数的下标存放到该变量中。这是为了处理后一个数字需要减小造成前一个数字再次比后一个数字大的情况。当然,如果后面有一个数字比这两个数字都要大,那么这个变量就可以再次赋为-1了。如果在赋为前一个数下标之前,该变量已经被赋过值,这说明前面还有数和这两个数一样大,那么该变量的值不变就好。
上述的处理其实有些冗余,但都是方便我们在遇到前一个数大于后一个数时,能够放心地减一,并把后面的数全部置为9,这就是我们找到的规律。感兴趣的小伙伴也可以自行去推导前面一段的推导过程。
代码如下:
class Solution {public int monotoneIncreasingDigits(int n) {if (n == 0) return 0;if (n / 10 == 0 ) return n;int res = 0;int w = 0;int temp = n;while (n > 0) {n /= 10;w++;}n = temp;int[] c = new int[w];int i = w;while (n > 0) {c[i - 1] = n % 10;n/=10; i--;}int index = -1;for (i = 0; i < w; i++) {if (i + 1 < w && c[i + 1] == c[i]) {if (index == -1) index = i;}if (i + 1 < w && c[i + 1] > c[i]) {if (index != -1) index = -1;} if (i + 1 < w && c[i + 1] < c[i]) {if (index != -1) {if (c[i] > c[index]) {c[i]--;while (i + 1 < w) {c[++i] = 9;}} else {c[index]--;i = index + 1;while (i < w) {c[i++] = 9;}}} else {c[i]--;while (i + 1 < w) {c[++i] = 9;}}}}for (i = 0; i < w; i++) {res *= 10;res += c[i];}return res;}
}
LeetCode 968 监控二叉树
本题大致意思是从底往上推,若是从上往下推能节省的数目其实不大。之所以用贪心也是因为这个原因。
一个节点状态去我们分为3种:为0表示无监控也无覆盖,为1表示有覆盖,为2表示是监控。
空姐点视作有覆盖,叶子节点视作无覆盖。
分情况讨论:
左右节点其中一个为0,则当前节点必须要有监控;
左右节点都为1,当前节点无覆盖,等上层节点设监控
左右节点其中一个为2,当前节点有覆盖,返回1
.最后由于上面第二种情况和一些特别的情况,最后根节点还要再判断下。
代码如下:
class Solution {int sum = 0;
public:int state(TreeNode* root) {if (!root) return 1;if (!root->left && !root->right) return 0;int left = state(root->left);int right = state(root->right);if (left == 0 || right == 0) {sum++;return 2;}if (left == 1 && right == 1) return 0;if (left == 2 || right == 2) return 1;return 0;}int minCameraCover(TreeNode* root) {if (!root) return 0;int left = state(root->left);int right = state(root->right);if (left == 0 || right == 0) {sum++; }if (left == 1 && right == 1) sum++;return sum;}
};
相关文章:
算法训练营第三十九天 | LeetCode 738 单调递增的数字、LeetCode 968 监控二叉树
LeetCode 738 单调递增的数字 这题类似模拟,可以找出如下规律: 先将数字按位数从高位到低位存到一个整型数组中。在这个数组中,从左往右遍历,如果遇到一个两数相等,并且记录的这个变量之前没有赋过值,那么…...
Hive语法学习总结
Hive SQL语法学习总结 hive参数库操作1.创建库2.具体案例3.库的其他操作 表和库的路径演示表的操作创建表插入数据 hive参数 一 hive常用交互命令hive -e sql语句hive -f sql文件 //文件中是sql语句二 参数的设置方式一:在客户端中设置参数(当次有效)set 参数名参…...
【Linux】TCP协议【中】{确认应答机制/超时重传机制/连接管理机制}
文章目录 1.确认应答机制2.超时重传机制:超时不一定是真超时了3.连接管理机制 1.确认应答机制 TCP协议中的确认应答机制是确保数据可靠传输的关键部分。以下是该机制的主要步骤和特点的详细解释: 数据分段与发送: 发送方将要发送的数据分成一…...
solidworks画螺母学习笔记
螺母 单位mm 六边形 直径16mm,水平约束,内圆直径10mm 拉伸 选择两侧对称,厚度7mm 拉伸切除 画相切圆 切除深度7mm,反向切除 拔模角度45 镜像切除 倒角 直径1mm 异形孔向导 螺纹线 偏移打勾,距离为2mm…...
WebGL的医学培训软件开发
开发基于WebGL的医学培训软件是一项复杂且技术性强的任务,需要结合医学专业知识和计算机图形学技术。以下是详细的开发流程和关键步骤。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1.需求分析与定义 目标用户…...
新时代AI浪潮下,程序员和产品经理如何入局AIGC领域?
当下,AI浪潮席卷全球,AIGC大模型技术已经成为当今技术领域的一个重要趋势,对于产品经理来说,掌握这项技术不仅能够增强他们的职业技能,还能在竞争激烈的职场中脱颖而出。 为什么呢? 把握AI时代的机遇 AI技…...
OWASP top10--SQL注入(一)
SQL注入式攻击技术,一般针对基于Web平台的应用程序.造成SQL注入攻击漏洞的原因,是由于程序员在编写Web程序时,没有对浏览器端提交的参数进行严格的过滤和判断。用户可以修改构造参数,提交SQL查询语句,并传递至服务器端…...
java —— 类与方法
一、访问修饰符 在类和方法中,均可使用访问修饰符以锁定该类或方法的被访问权限。访问修饰符有四种: (一)public 同一个项目中,对所有的类可见。 (二)protected 同一个项目中,对…...
【MySQL精通之路】InnoDB-启动选项和系统变量
系统变量可以在服务器启动时设置TRUE或FALSE启用禁用,也可以通过使用--skip前缀来禁用 例如: 要启用或禁用InnoDB自适应哈希索引,可以在命令行中使用--skip-innodb-adaptive-hash-index或--innodb-adaptive-hash-index,或者在配置…...
嵌入式linux系统中文件系统制作方法详解
第一:制作目的 1、掌握嵌入式Ubuntu系统的构建方法 2、熟悉嵌入式Ubuntu文件系统映射压缩打包方法 3、掌握RK3399linux系统单文件系统更新方法 Ubuntu根文件系统制作完成之后,把制作好的ubuntu文件系统映射文件在出厂系统的基础上替换原有的ubuntu根文件系统,即对 Linux 系统…...
AI爆文写作:要写文章爆,这47个爆文前缀少不了!
47个爆文前缀:很震惊很好用 这些前缀,虽然被用了无数次,但每个人看到还是会忍不住点进去。 可以借鉴这样强情绪的句式。 序号前缀1就在刚刚…2真相曝光…3震惊国人…4惊天秘密…5疯狂转发…6删前速看…7千万别吃…8还敢喝吗…9癌症前兆…10赶快扔了…11太可怕了…12大事不…...
javas-core VS java-object-diff
对照工具选择 javas-core 和 java-object-diff ,对比demo https://github.com/kofgame/objectdiff-vs-javers,都为同源对比,都支持嵌套对象。 使用JMH测试方法进行性能测试,使用题库的QuestionResponseVO对象来进行对照对比,进行…...
dirsearch指令大全
文章目录 基本用法主要参数和选项目标和URL设置--url URL--url-list FILE 扩展名--extensions EXTENSIONS 字典文件--wordlists WORDLIST 线程和性能--threads THREADS--timeout SECONDS--delay MILLISECONDS 忽略状态码代理和请求设置--proxy PROXY--headers HEADERS 保存结果…...
C++基础:构建者设计模式
#include <iostream> #include <string> using namespace std; //构建者设计模式-一种工厂只生产一种复杂的产品 class robot {public:string head;string upbody;string downbody; };class robotBuilder {private:robot *myRobot;public:robotBuilder() //构造函…...
Swift 请求用户授权以跟踪其跨应用或网站的活动
步骤1:导入框架 首先,需要在Swift文件中导入AppTrackingTransparency框架。 import AppTrackingTransparency import AdSupport步骤2:请求跟踪许可 在适当的地方请求用户的跟踪许可。通常,这个请求会在应用启动时或者在用户执行…...
最新版npm详解
如:npm中搜索 jQuery image.png image.png 接地气的描述:npm 类似于如下各大手机应用市场 image.png image.png 查看本地 node 和 npm 是否安装成功 image.png image.png 或 npm install -g npm image.png image.png image.png image.png image.…...
超值分享50个DFM模型格式的素人直播资源,适用于DeepFaceLive的DFM合集
50直播模型:点击下载 作为直播达人,我在网上购买了大量直播用的模型资源,包含男模女模、明星脸、大众脸、网红脸及各种稀缺的路人素人模型。现在,我将这些宝贵的资源整理成合集分享给大家,需要的朋友们可以直接点击下…...
Python——一维二维字典数据转化为DataFrame的方法
import pands as pddf pd.DataFrame(dict)...
unity中如何插入网页
在Unity中插入自己的网页通常是通过使用Unity的WebGL构建目标和HTML页面来实现的。以下是一些步骤: 构建你的Unity项目为WebGL:在Unity中,选择Build Settings(构建设置),将Platform(平台&#x…...
【负载均衡在线OJ项目日记】引入网络库和客户端用户路由功能
目录 引入cpp-httplib库 将编译与运行服务打包 代码 客户端用户路由功能 采用MVC结构进行设计 用户路由功能 路由功能代码 引入cpp-httplib库 对于后端编译与运行模块基本已经设计完成,最后用户是通过网络传递代码等信息;我们就要将这个模块引入…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
rm视觉学习1-自瞄部分
首先先感谢中南大学的开源,提供了很全面的思路,减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接:https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架: 代码框架结构:readme有…...
leetcode73-矩阵置零
leetcode 73 思路 记录 0 元素的位置:遍历整个矩阵,找出所有值为 0 的元素,并将它们的坐标记录在数组zeroPosition中置零操作:遍历记录的所有 0 元素位置,将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...
初探用uniapp写微信小程序遇到的问题及解决(vue3+ts)
零、关于开发思路 (一)拿到工作任务,先理清楚需求 1.逻辑部分 不放过原型里说的每一句话,有疑惑的部分该问产品/测试/之前的开发就问 2.页面部分(含国际化) 整体看过需要开发页面的原型后,分类一下哪些组件/样式可以复用,直接提取出来使用 (时间充分的前提下,不…...
