当前位置: 首页 > news >正文

*算法训练(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题目地址 排序后遇到有重合的区间选择最大的区间保存即可&#xff0c;结果集中保存的是离当前区间最近的区间&#xff0c;因此使用当前区间与结果集中的最后一个集合比较查看是否有重合&…...

OpenJudge 奇数求和

目录 描述思路样例输入样例输出CodeCC 总时间限制: 1000ms 内存限制: 65536kB 描述 计算非负整数 m 到 n&#xff08;包括m 和 n &#xff09;之间的所有奇数的和&#xff0c;其中&#xff0c;m 不大于 n&#xff0c;且n 不大于300。例如 m3, n12, 其和则为&#xff1a;357911…...

【排序 - 快速排序】

快速排序&#xff08;Quick Sort&#xff09;是一种高效的排序算法&#xff0c;它基于分治&#xff08;Divide and Conquer&#xff09;的策略。这种排序算法的核心思想是选择一个基准元素&#xff0c;将数组分割成两部分&#xff0c;使得左边的元素都小于等于基准元素&#xf…...

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)以上述代码为例&#xff0c;如果类名是Test开头&am…...

开源项目编译harbor arm架构的包 —— 筑梦之路

GitHub - amy5200/harbor-arm64 先做个记录&#xff0c;空了再验证...

[笔记] SKF Enveloping FAQ 用户指南

文档编号&#xff1a;Application Note CM3013 1.名词解释&#xff1a; 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 国家性质概述 国家性质的概念 国家性质也称国体&#xff0c;或国家的阶级本质&#xff0c;是指各个阶级在国家中的地位&#xff08;哪个阶层是统治阶层&#xff0c;哪个阶层是被统治阶层&#xff0c;哪个…...

联想拯救者Y7000 IRX9 笔记本接口功能介绍

适用机型&#xff1a;Legion Y7000 IRX9; 83JJ&#xff1b; USB&#xff08;3.2 Gen 1&#xff09;Type-接口摄像头开关组合音频插孔 多用于USB Type-C接口 以太网接口 多用途USB Type-C接口&#xff08;支持USB Power Delivery&#xff09;HDMI接口USB&#xff08;3.2 Gen 1&…...

【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网

SmartConfig一键配网 一、SmartConfig知识扫盲 在讲STA课程的时候&#xff0c;我们用的是代码里面固定的SSID和密码去连接热点&#xff0c;但实际应用中不可能这么弄&#xff0c;我们得有办法把家里的WiFi SSID和密码输入到设备里面去&#xff0c;对于带屏带输入设备还…...

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组件】封装加载弹框

&#x1f4d6;封装加载弹框 ✅1. 构造LoadingDialog✅2. 调用LoadingDialog 效果&#xff1a; ✅1. 构造LoadingDialog 构造LoadingDialog类涉及到设计模式中的建造者模式&#xff0c;进行链式调用&#xff0c;注重的是构建的过程&#xff0c;设置需要的属性。 步骤一&#x…...

Spring源码二十:Bean实例化流程三

上一篇Spring源码十九&#xff1a;Bean实例化流程二中&#xff0c;我们主要讨论了单例Bean创建对象的主要方法getSingleton了解到了他的核心流程无非是&#xff1a;通过一个简单工厂的getObject方法来实例化bean&#xff0c;当然spring在实例化前后提供了扩展如&#xff1a;bef…...

前端导出文件时,后端代码出错如何将错误信息返回给前端展示

功能说明&#xff1a;前端导出excel时&#xff0c;后端出现异常&#xff0c;比如sql异常&#xff0c;或者创建excel时出现的异常&#xff0c;希望将这些异常信息返回给前端查看。 框架&#xff1a;vue3 axios Springboot 实现难度分析&#xff1a;前端导出excel&#xff0c…...

解决Spring Boot应用中的内存优化问题

解决Spring Boot应用中的内存优化问题 大家好&#xff0c;我是微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 1. Spring Boot应用的内存管理 在开发和部署Spring Boot应用时&#xff0c;有效地管理内存是确保应用性能和稳…...

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 布局深度解析

响应式设计的双璧&#xff1a;WebKit 支持 CSS Flexbox 和 Grid 布局深度解析 在现代网页设计中&#xff0c;响应式布局是实现跨设备兼容性的关键。CSS Flexbox 和 Grid 作为 CSS 布局的两大支柱&#xff0c;提供了强大的工具来构建灵活和复杂的用户界面。WebKit&#xff0c;作…...

Linux软件包管理

一、软件包管理 1.什么是软件包 一般在window系统的.exe是软件按转包 2.linux系统下的软件包安装方式 PRM 软件包安装 软件名称.rpmYUM 包管理工具 yum intall 软件名称 -y源码安装 下载源代码---编译---安装 很麻烦&#xff0c;稳定 3.二进制软件包 二进制 4.获取*.rpm…...

如何分辨AI生成的内容?AI生成内容检测工具对比实验

检测人工智能生成的文本对各个领域的组织都提出了挑战&#xff0c;包括学术界和新闻界等。生成式AI与大语言模型根据短描述来进行内容生成的能力&#xff0c;产生了一个问题&#xff1a;这篇文章/内容/作业/图像到底是由人类创作的&#xff0c;还是AI创作的&#xff1f;虽然 LL…...

Clion中怎么切换不同的程序运行

如下图&#xff0c;比如这个文件夹下面有那么多的项目&#xff1a; 那么我想切换不同的项目运行怎么办呢&#xff1f;如果想通过下图的Edit Configurations来设置是不行的&#xff1a; 解决办法&#xff1a; 如下图&#xff0c;选中项目的CMakeLists.txt&#xff0c;右键再点击…...

【C++初阶】C++入门(下)

【C初阶】C入门&#xff08;下&#xff09; &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f955;所属专栏&#xff1a;C&#x1f96d; &#x1f33c;文章目录&#x1f33c; 6. 引用 6.1 引用的概念 6.2 引用特性 6.3 常引用 6.4 使用场景 6.5 传值、传引用效率…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...