算法训练(leetcode)第二十六天 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763. 划分字母区间
刷题记录
- 452. 用最少数量的箭引爆气球
- 思路一
- 思路二
- 435. 无重叠区间
- 763. 划分字母区间
452. 用最少数量的箭引爆气球
leetcode题目地址
思路一
先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中,遍历气球数组从交集数组中找交集,找到与当前集合相交的集合后将该集合的范围更新为两集合的交集(即左右区间取最小),最后返回交集数组的长度。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)
// 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];}int findMinArrowShots(vector<vector<int>>& points) {vector<vector<int>> arrows;sort(points.begin(), points.end(), cmp);for(int i=0; i<points.size(); i++){bool flag = true;for(int j=0; j<arrows.size(); j++){if(points[i][0]>=arrows[j][0] && points[i][0] <= arrows[j][1]){arrows[j][0] = min(arrows[j][0], points[i][0]);arrows[j][1] = min(arrows[j][1], points[i][1]);flag = false;break;}}if(flag){arrows.emplace_back(points[i]);}}return arrows.size();}
};
思路二
和思路一本质上是一样的,只是不再借助额外空间,也不再需要双层循环。排序后只查看当前气球的起始坐标小于上一个气球的结束坐标,是则说明有重叠,则缩小当前节点的结束坐标为交集的结束位置,反之没有重叠则箭数量+1。
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)
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];}int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0) return 0;sort(points.begin(), points.end());int result = 1;for(int i=1; i<points.size(); i++){if(points[i][0] > points[i-1][1]){result++;}else{points[i][1] = min(points[i-1][1], points[i][1]);}}return result;}
};
435. 无重叠区间
leetcode题目地址
本题可以说是和上一题换汤不换药,只不过上一题是统计不重叠的区间个数,本题是统计重叠区间。尽可能少的移除区间来保持剩余区间互不重叠,那每次出现重叠移除区间最大的那个即可。
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: 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];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {int result = 0;sort(intervals.begin(), intervals.end(), cmp);for(int i=1; i<intervals.size(); i++){if(intervals[i][0] < intervals[i-1][1]){// 把最大的区间移除intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);result++;}}return result;}
};
763. 划分字母区间
leetcode题目地址
记录每个字符出现的最远位置,子串截取到子串中出现的字符的最远位置。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:vector<int> partitionLabels(string s) {cin.tie(nullptr)->sync_with_stdio(false);int hash[26] = {0};for(int i=0; i<s.size(); i++){hash[s[i]-'a'] = i;}int left = 0;int right = 0;vector<int> result;for(int i=0; i<s.size(); i++){right = max(right, hash[s[i]-'a']);if(i==right){result.emplace_back(right-left+1);left = i+1;}}return result;}
};
相关文章:
算法训练(leetcode)第二十六天 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763. 划分字母区间
刷题记录 452. 用最少数量的箭引爆气球思路一思路二 435. 无重叠区间763. 划分字母区间 452. 用最少数量的箭引爆气球 leetcode题目地址 思路一 先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中,遍历气球数组从交集数组中找交集,找到与…...
Ubuntu 下 Docker安装 2024
Ubuntu 下 Docker安装 2024 安装1.卸载老版本2.更新apt包索引3.安装必要工具包4.添加Docker GPG秘钥5.配置仓库源6.安装Docker Engine7.启动docker 国内镜像源下架的解决办法1.修改文件 /etc/docker/daemon.json2.换源3.查看是否换源成功4.重启 安装 1.卸载老版本 sudo apt-ge…...
发送者的可靠性
这篇文章是了解MQ消息的可靠性,即:消息应该至少被消费者处理1次 那么问题来了: 我们该如何确保MQ消息的可靠性?如果真的发送失败,有没有其它的兜底方案? 首先,我们一起分析一下消息丢失的可能…...
Profibus_DP转ModbusTCP网关模块连马保与上位机通讯
Profibus转ModbusTCP网关模块(XD-ETHPB20)广泛应用于工业自动化领域。例如,可以将Profibus网络中的传感器数据转换为ModbusTCP协议,实现数据的实时监控和远程控制。本文介绍了如何利用Profibus转ModbusTCP网关(XD-ETHP…...
移动应用:商城购物类,是最常见的,想出彩或许就差灵犀一指
在移动应用中,商城购物类的非常常见,模式也非常成熟,想要设计的出彩也是有难度的,这次分享一些不同的。...
linux 查看历史命令列表来访问之前的内容的命令是:history
在Linux中,要查看历史命令列表以访问之前的内容,你可以使用history命令。这个命令会显示你当前shell会话(或者,如果你指定了参数,可能是所有会话)中执行过的命令列表。 基本用法 简单地输入history并按下…...
NAS免费用,鲁大师 AiNAS正式发布,「专业版」年卡仅需264元
7月10日,鲁大师召开新品发布会,正式发布旗下以“提供本地Ai部署和使用能力以及在线NAS功能”并行的复合软件产品:鲁大师 AiNAS。 全新的鲁大师 AiNAS将持续满足现如今大众对于数字化生活的全新需求,将“云存储”的便捷与NAS的大容…...
spring监听事件
1、spring-监听事件基本原理 Spring的事件监听机制和发布订阅机制是很相似的:发布了一个事件后,监听该类型事件的所有监听器会触发相应的处理逻辑 2、Spring 监听事件相关规范 在Spring中,事件监听机制主要涉及到了一下几个关键的规范&#x…...
微软发布E2 TTS: 一种简单但效果优秀的文本转语音技术
本文介绍了一种名为“Embarrassingly Easy Text-to-Speech(E2 TTS)”的文本转语音系统。 该系统通过将输入文本转换为填充标记字符序列,并基于音频填充值任务训练流匹配基mel频谱生成器,实现了人类水平的自然度和最先进的说话人相…...
python爬虫加入进度条
安装tqdm和requests库 pip install tqdm -i https://pypi.tuna.tsinghua.edu.cn/simplepip install requests -i https://pypi.tuna.tsinghua.edu.cn/simple带进度条下载 import time # 引入time模块,用于处理时间相关的功能 from tqdm import * # 从tqdm包中…...
力扣844.比较含退格的字符串
力扣844.比较含退格的字符串 栈模拟 class Solution {public:bool backspaceCompare(string s, string t) {int n s.size(),m t.size();stack<char> s1,s2;for(int i0;i<n;i){s1.push(s[i]);if(s[i] #){if(s1.size() 1) s1.pop();else s1.pop(),s1.pop();}}for(i…...
用户特征和embedding层做Concatenation
要将用户特征与嵌入层进行连接,可以使用深度学习框架(如TensorFlow或PyTorch)中的基本操作。以下是使用PyTorch的示例代码,展示了如何将用户特征与嵌入层连接起来。 示例代码(使用PyTorch) 安装 PyTorch 如…...
Ubuntu20.04下修改samba用户密码
Ubuntu20.04下修改samba用户密码 在Ubuntu系统中,修改samba密码通常涉及到两个方面:更改samba用户的密码和重置samba服务的密码数据库。以下是如何进行操作的步骤: 1、更改samba用户密码: 打开终端,使用以下命令更改…...
PHP老照片修复文字识别图像去雾一键抠图微信小程序源码
🔍解锁复古魅力,微信小程序黑科技大揭秘!老照片修复&更多神奇功能等你来试! 📸 【老照片修复,时光倒流的美颜术】 你是否珍藏着一堆泛黄的老照片,却因岁月侵蚀而模糊不清?现在…...
识别色带详解解释
这段代码主要用于检测图像中的绿色区域,并在检测到特定数量的绿色像素时采取相应的动作。下面是每行代码的详细解释: if (divergerColor "green") {目的: 检查当前 divergerColor 是否为 “green”。如果是,则进入代码块进行绿色…...
如何用 Python 绕过 cloudflare(5秒盾) 抓取数据:也不是很难嘛!
大家好!我是爱摸鱼的小鸿,关注我,收看每期的编程干货。 逆向是爬虫工程师进阶必备技能,当我们遇到一个问题时可能会有多种解决途径,而如何做出最高效的抉择又需要经验的积累。本期文章将以实战的方式,带你全面了解 cloudflare(5秒盾) 以及如何绕过使用 cloudflare 服务…...
掌握Conda配置术:conda config命令的深度指南
掌握Conda配置术:conda config命令的深度指南 引言 Conda是一个功能强大的包管理器和环境管理器,广泛用于Python和其他科学计算语言的依赖管理。conda config命令是Conda套件中用于配置和自定义Conda行为的关键工具。通过这个命令,用户可以…...
MySQL:left join 后用 on 还是 where?
在MySQL中,LEFT JOIN用于返回左表(即LEFT JOIN关键字左边的表)的所有记录,即使在右表中没有匹配的记录。对于那些右表中没有匹配的记录,结果集中右表的部分会被填充为NULL。关于ON和WHERE子句的使用,它们在…...
openfoam生成的非均匀固体Solid数据分析、VTK数据格式分析、以及paraview官方用户指导文档和使用方法
一、openfoam生成的非均匀固体Solid数据分析 二、VTK数据格式分析 三、paraview官方用户指导文档和使用方法 官网文档链接:在paraview软件中,点击工具栏中的help->paraview guide 即可直接跳转到浏览器打开官网指导页面。 官网链接如下:…...
JVM:类的生命周期
文章目录 一、介绍二、加载阶段三、连接阶段1、验证阶段2、准备阶段3、解析阶段 四、初始化阶段 一、介绍 类的生命周期描述了一个类加载、连接(验证、准备和解析)、初始化、使用、卸载的整个过程。 二、加载阶段 加载(Loading)…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
