算法训练营第三十九天 | 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库 对于后端编译与运行模块基本已经设计完成,最后用户是通过网络传递代码等信息;我们就要将这个模块引入…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
