*算法训练(leetcode)第二十七天 | 56. 合并区间、738. 单调递增的数字、968. 监控二叉树
刷题记录
- 56. 合并区间
- *738. 单调递增的数字
- *968. 监控二叉树
56. 合并区间
leetcode题目地址
排序后遇到有重合的区间选择最大的区间保存即可,结果集中保存的是离当前区间最近的区间,因此使用当前区间与结果集中的最后一个集合比较查看是否有重合,若有重合则将右区间扩大为两个区间中最大的右区间,若没有重合则将当前集合放入结果集中。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:static bool cmp(const vector<int> & a, const vector<int> & b){if(a[0]==b[0]) return a[1] > b[1];return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;sort(intervals.begin(), intervals.end(), cmp);for(int i=0; i<intervals.size(); i++){if(result.size()>0){int last = result.size()-1;if(intervals[i][0]<=result[last][1])result[last][1] = max(result[last][1], intervals[i][1]);else{result.emplace_back(intervals[i]);}}else{result.emplace_back(intervals[i]);}}return result;}
};
*738. 单调递增的数字
leetcode题目地址
一开始想着暴力求解,但超时了,然后就没思路了。
思路来源
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);int 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);}
};
*968. 监控二叉树
leetcode题目地址
借助后序遍历,每个结点三种状态:无覆盖、有监控、被覆盖,分别用0、1、2标识。
- 若孩子节点都是被覆盖,则当前节点没有被覆盖,返回0;
- 若孩子节点有一个未被覆盖,则当前节点需要加装监控,计数器+1,返回1;
- 若孩子节点有一个装了监控,则当前节点是被覆盖的状态,返回2;
空节点需要返回被覆盖状态,即2。
因为空节点的父结点可能是叶结点,若返回无覆盖状态,则会把监控装在叶结点,而正确的位置应该装在叶结点的父节点;若返回有监控,则会导致单分支节点未被覆盖。因此只能返回2.
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
// c++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*//*
三种状态:
无覆盖:0
当前节点有摄像头:1
当前节点有被覆盖:2
*/
class Solution {
public:int Traverse(TreeNode* root, int &result){if(!root) return 2;int left = Traverse(root->left, result);int right = Traverse(root->right, result);// 左右节点有一个未被覆盖 则当前节点需要加摄像头if(!left || !right){result++;return 1;}// 左右节点有监控 则当前节点被覆盖if(left == 1 || right == 1){return 2;}// 子节点都是覆盖 则当前节点未被覆盖if(left==2 && right==2) {return 0;}return -1;}int minCameraCover(TreeNode* root) {int result = 0;int res = Traverse(root, result);// 根节点未被覆盖if(!res) result++;return result;}
};
相关文章:
*算法训练(leetcode)第二十七天 | 56. 合并区间、738. 单调递增的数字、968. 监控二叉树
刷题记录 56. 合并区间*738. 单调递增的数字*968. 监控二叉树 56. 合并区间 leetcode题目地址 排序后遇到有重合的区间选择最大的区间保存即可,结果集中保存的是离当前区间最近的区间,因此使用当前区间与结果集中的最后一个集合比较查看是否有重合&…...
OpenJudge 奇数求和
目录 描述思路样例输入样例输出CodeCC 总时间限制: 1000ms 内存限制: 65536kB 描述 计算非负整数 m 到 n(包括m 和 n )之间的所有奇数的和,其中,m 不大于 n,且n 不大于300。例如 m3, n12, 其和则为:357911…...
【排序 - 快速排序】
快速排序(Quick Sort)是一种高效的排序算法,它基于分治(Divide and Conquer)的策略。这种排序算法的核心思想是选择一个基准元素,将数组分割成两部分,使得左边的元素都小于等于基准元素…...
pytest使用报错(以及解决pytest所谓的“抑制print输出”)
1. 测试类的类名问题 #codingutf-8import pytestclass TestClass1:def setup(self) -> None:print(setup)def test_01(self) -> None:print(test_01111111111111111111111)def test_02(self) -> None:print(test_02)以上述代码为例,如果类名是Test开头&am…...
开源项目编译harbor arm架构的包 —— 筑梦之路
GitHub - amy5200/harbor-arm64 先做个记录,空了再验证...
[笔记] SKF Enveloping FAQ 用户指南
文档编号:Application Note CM3013 1.名词解释: 1.1cavitationWhat Is Cavitation? | Pumps & Systems 叶片在液体中扰动形成的超声波 1.2 stiff machinehttps://suspensionlist.com/the-pros-and-cons-of-stiff-vs-soft-suspension-systems/ …...
宪法学学习笔记(个人向) Part.3
宪法学学习笔记(个人向) Part 3 3. 国家基本制度 3.1 国家性质 3.1.1 国家性质概述 国家性质的概念 国家性质也称国体,或国家的阶级本质,是指各个阶级在国家中的地位(哪个阶层是统治阶层,哪个阶层是被统治阶层,哪个…...
联想拯救者Y7000 IRX9 笔记本接口功能介绍
适用机型:Legion Y7000 IRX9; 83JJ; USB(3.2 Gen 1)Type-接口摄像头开关组合音频插孔 多用于USB Type-C接口 以太网接口 多用途USB Type-C接口(支持USB Power Delivery)HDMI接口USB(3.2 Gen 1&…...
【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网
SmartConfig一键配网 一、SmartConfig知识扫盲 在讲STA课程的时候,我们用的是代码里面固定的SSID和密码去连接热点,但实际应用中不可能这么弄,我们得有办法把家里的WiFi SSID和密码输入到设备里面去,对于带屏带输入设备还…...
MD5加密和注册页面的编写
MD5加密 1.导入包 npm install --save ts-md5 2.使用方式 import { Md5 } from ts-md5; //md5加密后的密码 const md5PwdMd5.hashStr("123456").toUpperCase(); 遇见的问题及用到的技术 注册页面 register.vue代码 <template><div class"wappe…...
【Android组件】封装加载弹框
📖封装加载弹框 ✅1. 构造LoadingDialog✅2. 调用LoadingDialog 效果: ✅1. 构造LoadingDialog 构造LoadingDialog类涉及到设计模式中的建造者模式,进行链式调用,注重的是构建的过程,设置需要的属性。 步骤一&#x…...
Spring源码二十:Bean实例化流程三
上一篇Spring源码十九:Bean实例化流程二中,我们主要讨论了单例Bean创建对象的主要方法getSingleton了解到了他的核心流程无非是:通过一个简单工厂的getObject方法来实例化bean,当然spring在实例化前后提供了扩展如:bef…...
前端导出文件时,后端代码出错如何将错误信息返回给前端展示
功能说明:前端导出excel时,后端出现异常,比如sql异常,或者创建excel时出现的异常,希望将这些异常信息返回给前端查看。 框架:vue3 axios Springboot 实现难度分析:前端导出excel,…...
解决Spring Boot应用中的内存优化问题
解决Spring Boot应用中的内存优化问题 大家好,我是微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 1. Spring Boot应用的内存管理 在开发和部署Spring Boot应用时,有效地管理内存是确保应用性能和稳…...
shark云原生-日志体系-filebeat高级配置(适用于生产)-更新中
文章目录 1. filebeat.inputs 静态日志收集器2. filebeat.autodiscover 自动发现2.1. autodiscover 和 inputs2.2. 如何配置生效2.3. Providers 提供者2.4. Providers kubernetes2.5. 配置 templates2.5.1. kubernetes 自动发现事件中的变量字段2.5.2 配置 templates 2.6. 基于…...
响应式设计的双璧:WebKit 支持 CSS Flexbox 和 Grid 布局深度解析
响应式设计的双璧:WebKit 支持 CSS Flexbox 和 Grid 布局深度解析 在现代网页设计中,响应式布局是实现跨设备兼容性的关键。CSS Flexbox 和 Grid 作为 CSS 布局的两大支柱,提供了强大的工具来构建灵活和复杂的用户界面。WebKit,作…...
Linux软件包管理
一、软件包管理 1.什么是软件包 一般在window系统的.exe是软件按转包 2.linux系统下的软件包安装方式 PRM 软件包安装 软件名称.rpmYUM 包管理工具 yum intall 软件名称 -y源码安装 下载源代码---编译---安装 很麻烦,稳定 3.二进制软件包 二进制 4.获取*.rpm…...
如何分辨AI生成的内容?AI生成内容检测工具对比实验
检测人工智能生成的文本对各个领域的组织都提出了挑战,包括学术界和新闻界等。生成式AI与大语言模型根据短描述来进行内容生成的能力,产生了一个问题:这篇文章/内容/作业/图像到底是由人类创作的,还是AI创作的?虽然 LL…...
Clion中怎么切换不同的程序运行
如下图,比如这个文件夹下面有那么多的项目: 那么我想切换不同的项目运行怎么办呢?如果想通过下图的Edit Configurations来设置是不行的: 解决办法: 如下图,选中项目的CMakeLists.txt,右键再点击…...
【C++初阶】C++入门(下)
【C初阶】C入门(下) 🥕个人主页:开敲🍉 🥕所属专栏:C🥭 🌼文章目录🌼 6. 引用 6.1 引用的概念 6.2 引用特性 6.3 常引用 6.4 使用场景 6.5 传值、传引用效率…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
