Day37 56合并区间 738单调递增的数字 968监控二叉树
56 合并区间
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};
本题主要技巧是在result数组里面进行重叠操作,而不是在原数组里面进行合并。
738 单调递增的数字
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)
示例 1:
- 输入: N = 10
- 输出: 9
示例 2:
- 输入: N = 1234
- 输出: 1234
示例 3:
- 输入: N = 332
- 输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数
本题如果使用暴力解法,从后往前一个数一个数的遍历,一定会超时,所以采用贪心算法:
如果前一个数比后一个数大,就将后一个数变成9,前一个数减1,从后往前遍历即可,同时,在处理变成9的时候不要直接处理,而是利用一个flag标志记录此时的位置,最后flag后面的所有数一起变成9,例如1000,如果不用flag的话,最后两个00是不会变的:
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值,为了防止第二个for循环在flag没有被赋值的情况下执行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:
- 输入:[0,0,null,0,0]
- 输出:1
- 解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
- 输入:[0,0,null,0,null,0,null,null,0]
- 输出:2
- 解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示:
- 给定树的节点数的范围是 [1, 1000]。
- 每个节点的值都是 0。
本题要求的是最少的摄像头,所以尽量让叶子节点的父节点为摄像头,每隔两层安装一个新的摄像头。于是本题采用后序遍历。
本题分别用数字代表此时的状态:0代表这个点没有被覆盖,1代表本节点有摄像头,2代表本节点被摄像头覆盖。
一共有四种不同情况:代码如下:
class Solution {
private:int result;int traversal(TreeNode* cur) {// 空节点,该节点有覆盖if (cur == NULL) return 2;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右// 情况1// 左右节点都有覆盖if (left == 2 && right == 2) return 0;// 情况2// 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// left == 1 && right == 2 左节点有摄像头,右节点有覆盖// left == 2 && right == 1 左节点有覆盖,右节点有摄像头// left == 1 && right == 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if (left == 1 || right == 1) return 2;// 以上代码我没有使用else,主要是为了把各个分支条件展现出来,这样代码有助于读者理解// 这个 return -1 逻辑不会走到这里。return -1;}public:int minCameraCover(TreeNode* root) {result = 0;// 情况4if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};
相关文章:

Day37 56合并区间 738单调递增的数字 968监控二叉树
56 合并区间 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. class Solution { public:vector<vector<int>>…...

【Android】在WSA安卓子系统中进行新实验性功能试用与抓包(2311.4.5.0)
前言 在根据几篇22和23的WSA抓包文章进行尝试时遇到了问题,同时发现新版Wsa的一些实验性功能能优化抓包配置时的一些步骤,因而写下此篇以作记录。 Wsa版本:2311.40000.5.0 本文出现的项目: MagiskOnWSALocal MagiskTrustUserCer…...

【服务器】服务器的管理口和网口
服务器通常会有两种不同类型的网络接口,即管理口(Management Port)和网口(Ethernet Port),它们的作用和用途不同。 一、管理口 管理口通常是用于服务器管理的网络接口,也被称为外带网卡或带外接…...

一个小例子,演示函数指针
结构体里经常看到函数指针的写法,函数指针其实就是函数的名字。但是结构体里你要是直接把一个函数摆上去,那就变成成员变量,就会发生混乱 1. 函数指针 #include <unistd.h> #include <stdio.h>struct Kiwia{void (*func)(int )…...

python12-Python的字符串之使用input获取用户输入
input()函数用于向用户生成一条提示,然后获取用户输入的内容。由于input0函数总会将用户输入的内容放入字符串中,因此用户可以输入任何内容,input()函数总是返回一个字符串。例如如下程序。 # !/usr/bin/env python# -*- coding: utf-8 -*-# @Time : 2024/01# @Author : Lao…...

【代码随想录-数组】移除元素
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 jav…...

springboot事务管理
/*spring事务管理注解:Transactional位置:业务(service)层的方法上、类上、接口上作用:将当前方法交给spring进行事务管理,方法执行前,开启事务:成功执行完毕,提交事务:出现常,回滚事务需要在配置文件是加上开启spring事务yml文件…...

数据结构——链式二叉树(2)
目录 🍁一、二叉树的销毁 🍁二、在二叉树中查找某个数,并返回该结点 🍁三、LeetCode——检查两棵二叉树是否相等 🌕(一)、题目链接:100. 相同的树 - 力扣(LeetCode&a…...

spring-boot-starter-validation常用注解
文章目录 一、使用二、常用注解三、Valid or Validated ?四、分组校验1. 分组校验的基本概念2. 定义验证组3. 应用分组到模型4. 在控制器中使用分组5. 总结 一、使用 要使用这些注解,首先确保在你的 Spring Boot 应用的 pom.xml 文件中添加了 spring-bo…...

AF700 NHS 酯,AF 700 Succinimidyl Ester,一种明亮且具有光稳定性的近红外染料
AF700 NHS 酯,AF 700 Succinimidyl Ester,一种明亮且具有光稳定性的近红外染料,AF700-NHS-酯,具有水溶性和 pH 值不敏感性 您好,欢迎来到新研之家 文章关键词:AF700 NHS 酯,AF 700 Succinimid…...

C#常见内存泄漏
背景 在开发中由于对语言特性不了解或经验不足或疏忽,往往会造成一些低级bug。而内存泄漏就是最常见的一个,这个问题在测试过程中,因为操作频次低,而不能完全被暴露出来;而在正式使用时,由于使用次数增加&…...

Xmind安装到指定目录
Xmind安装到指定目录 默认情况下安装包自动引导安装在C盘(注册表默认位置) T1:修改注册表,比较麻烦 T2:安装时命令行指定安装位置,快捷省事 1)下载安装包(exe可执行文件) 2)安装…...

[GXYCTF2019]BabyUpload1
尝试各种文件,黑名单过滤后缀ph,content-type限制image/jpeg 内容过滤<?,木马改用<script languagephp>eval($_POST[cmdjs]);</script> 上传.htaccess将上传的文件当作php解析 蚁剑连接得到flag...

SpringBoot之分页查询的使用
背景 在业务中我们在前端总是需要展示数据,将后端得到的数据进行分页处理,通过pagehelper实现动态的分页查询,将查询页数和分页数通过前端发送到后端,后端使用pagehelper,底层是封装threadlocal得到页数和分页数并动态…...

【shell-10】shell实现的各种kafka脚本
kafka-shell工具 背景日志 log一.启动kafka->(start-kafka)二.停止kafka->(stop-kafka)三.创建topic->(create-topic)四.删除topic->(delete-topic)五.获取topic列表->(list-topic)六. 将文件数据 录入到kafka->(file-to-kafka)七.将kafka数据 下载到文件-&g…...

【模型压缩】模型剪枝详解
参考链接:https://zhuanlan.zhihu.com/p/635454943 https 文章目录 1. 前言1.1 为什么要进行模型剪枝1.2 为什么可以进行模型剪枝2. 剪枝方式的几种分类2.1 结构化剪枝 和 非结构化剪枝2.1.1 结构化剪枝2.1.2 非结构化剪枝2.2 静态剪枝与动态剪枝2.2.1 静态剪枝2.2.2 动态剪枝…...

Log4j2-01-log4j2 hello world 入门使用
拓展阅读 Log4j2 系统学习 Logback 系统学习 Slf4j Slf4j-02-slf4j 与 logback 整合 SLF4j MDC-日志添加唯一标识 分布式链路追踪-05-mdc 等信息如何跨线程? Log4j2 与 logback 的实现方式 日志开源组件(一)java 注解结合 spring aop 实现自动输…...

Mysql-日志介绍 日志配置
环境部署 docker run -d -p 3306:3306 --privilegedtrue -v $(pwd)/logs:/var/lib/logs -v $(pwd)/conf:/etc/mysql/conf.d -v $(pwd)/data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD654321 --name mysql mysql:5.7运行指令的目录下新建好这些文件: 日志类型 日…...

计算机网络的体系结构的各层在整个过程中起到什么作用?
ps:本文章的图片内容来源都是来自于湖科大教书匠的视频,声明:仅供自己复习,里面加上了自己的理解 这里附上视频链接地址:1.6 计算机网络体系结构(4)—专用术语_哔哩哔哩_bilibili 目录 &#x…...

如何在业务代码中优雅的使用策略模式?
策略模式介绍 假设你正在开发一个电商平台,其中涉及到商品的折扣策略。优惠策略有很多种可能,如领取优惠券抵扣、返现促销、拼团优惠等。最初的实现可能会在购物车类中嵌入各种折扣逻辑,导致代码的可维护性和扩展性下降。 下面代码在业务开…...

“docker-credential-desktop.exe“: executable file not found in $PATH 错误解决
"docker-credential-desktop.exe": executable file not found in $PATH 错误解决 1. 错误信息和解决方法 1. 错误信息和解决方法 错误信息, error getting credentials - err: exec: "docker-credential-desktop.exe": executable file not …...

openssl3.2/test/certs - 055 - all DNS-like CNs allowed by CA1, no DNS SANs
文章目录 openssl3.2/test/certs - 055 - all DNS-like CNs allowed by CA1, no DNS SANs概述笔记END openssl3.2/test/certs - 055 - all DNS-like CNs allowed by CA1, no DNS SANs 概述 openssl3.2 - 官方demo学习 - test - certs 笔记 /*! * \file D:\my_dev\my_local_…...

长虹智能电视6000iD、6080iD、3000iD、U2系列等 ZLM61HiPJ机芯升级刷机方法,附刷机数据
机芯:ZLM61HiPJ 适用机型:UD39B6000iD、UD42B6000iD、UD50B6000iD、UD55B6000iD、UD42C6000iD、UD42C6080iD、UD49C6000iD、UD49C6080iD、UD55C6000iD、UD55C6080iD、UD50C6000iD、UD58C3000iD、42U2 LE42C19S-UD、LE50C29SD-UD、 UD49C6000iD(LJM2W)、…...

六、VTK创建平面vtkPlaneSource
vtkPlaneSource创建位于平面中的四边形数组 先看看效果图: vtkPlaneSource 创建一个 m x n 个四边形数组,这些四边形在平面中排列为规则平铺。通过指定一个原点来定义平面,然后指定另外两个点,这两个点与原点一起定义平面的两个轴。这些轴不必是正交的 - 因此您可以创建平行…...

LiveGBS流媒体平台GB/T28181常见问题-如何配置使用自己已有的redis服务替换redis版本升级redis版本
LiveGBS如何配置使用自己已有的redis服务替换redis版本升级redis版本 1、Redis服务2、如何切换REDIS?2.1、停止启动REDIS2.2、配置信令服务2.3、配置流媒体服务2.4、启动 3、搭建GB28181视频直播平台 1、Redis服务 在LivGBS中Redis作为数据交换、数据订阅、数据发布的高速缓存…...

stm32产品架构
文章目录 前言一、pandas是什么?二、使用步骤 1.引入库2.读入数据 总结 前言 起因是我在看野火的ucosiii,然后他是基于i.mx芯片。然后我就很疑惑i.mx是什么芯片,看了下好像是ARM-M7(或者叫ARMCM7)架构的芯片。然后我又疑惑ARM-M7又是什么架…...

数据结构——双链表
双链表中节点类型的描述: 双链表的初始化(带头结点) 、 双链表的插入操作 后插操作 InsertNextDNode(p, s): 在p结点后插入s结点 按位序插入操作: 思路:从头结点开始,找到某个位序的前驱结点ÿ…...

Git 对文件名大小写不敏感的问题解决方案
目录 一、Git 对文件名大小写不敏感1.1 问题描述1.2 原因分析1.3 解决方案方式一:使用git命令进行修改方式二:关闭git 忽略大小写配置 (可以当前项目设置,也可以全局设置 --global) 二、新的问题(重复的目录…...

Java复习系列之阶段三:框架原理
1. Spring 1.1 核心功能 1. IOC容器 IOC,全称为控制反转(Inversion of Control),是一种软件设计原则,用于减少计算机代码之间的耦合度。控制反转的核心思想是将传统程序中对象的创建和绑定由程序代码直接控制转移到…...

【Python】01快速上手爬虫案例一:搞定豆瓣读书
文章目录 前言一、VSCodePython环境搭建二、爬虫案例一1、爬取第一页数据2、爬取所有页数据3、格式化html数据4、导出excel文件 前言 实战是最好的老师,直接案例操作,快速上手。 案例一,爬取数据,最终效果图: 一、VS…...