算法训练(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)…...
本地 AI 智能体落地:OpenClaw 如何稳定运行并真正提效?
最近我把 OpenClaw 作为核心自动化工具来使用了一段时间。它能让大模型直接操作电脑,跑脚本、处理文件、启动服务、执行批量任务,这种 “本地自动化” 体验非常真实。 但一开始我也被它的 “不稳定” 搞得很崩溃。 1. OpenClaw 的真正价值(…...
ANARCI抗体序列分析工具:从入门到精通的专业指南
ANARCI抗体序列分析工具:从入门到精通的专业指南 【免费下载链接】ANARCI Antibody Numbering and Antigen Receptor ClassIfication 项目地址: https://gitcode.com/gh_mirrors/an/ANARCI ANARCI(Antibody Numbering and Antigen Receptor Class…...
Qwen3.5-4B-Claude-Opus应用场景:技术博客选题生成、文章大纲结构化输出
Qwen3.5-4B-Claude-Opus应用场景:技术博客选题生成与文章大纲结构化输出 1. 模型概述与核心能力 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF是基于Qwen3.5-4B的推理蒸馏模型,特别强化了结构化分析和逻辑推理能力。这个经过优化的版本以GGUF…...
Anaconda Prompt卡在solving environment?别慌,三步搞定清华镜像源配置(附.condarc文件)
Anaconda环境配置卡顿?清华镜像源优化全指南 刚接触Python数据科学的新手们,十有八九会在Anaconda环境配置这一步栽跟头。特别是当看到命令行窗口里"solving environment"的提示一直转圈却迟迟没有进展时,那种等待的煎熬简直让人抓…...
新手避坑指南:用Python+ROS搞定AVP项目中的.bag数据读取与深度图转点云
从零开始处理AVP项目中的.bag数据:深度图与点云实战解析 停车场里75个RealSense相机同时工作,产生的.bag数据像一座未经开采的金矿——但当你第一次打开这些文件时,可能会感到无从下手。作为刚接触ROS和点云处理的新手,我清楚地记…...
3步颠覆性解决方案:零成本条码生成技术让企业彻底告别付费依赖
3步颠覆性解决方案:零成本条码生成技术让企业彻底告别付费依赖 【免费下载链接】librebarcode Libre Barcode: barcode fonts for various barcode standards. 项目地址: https://gitcode.com/gh_mirrors/li/librebarcode Libre Barcode开源字体库通过字体化…...
PETRV2-BEV模型的高精度3D车道检测效果展示
PETRV2-BEV模型的高精度3D车道检测效果展示 1. 引言 想象一下,一辆自动驾驶汽车在复杂的城市道路中行驶,需要实时识别车道线、判断可行驶区域、预测周围车辆轨迹。这背后离不开一项关键技术——3D车道检测。传统的2D检测方法在复杂道路场景中往往力不从…...
Python实战:两步移动搜索法(2SFCA)在医疗资源可达性分析中的应用
1. 什么是两步移动搜索法(2SFCA)? 第一次听说两步移动搜索法(2SFCA)时,我完全被这个专业名词唬住了。后来在实际项目中用了才发现,它其实就是个"找资源"的聪明算法。想象一下你住在一…...
Polars 2.0清洗架构解密(含完整数据流拓扑图):为什么92%的团队还在用Pandas硬扛TB级脏数据?
第一章:Polars 2.0清洗架构解密:从设计哲学到性能跃迁Polars 2.0 的清洗架构并非简单功能叠加,而是以“零拷贝流式处理”与“惰性执行图优化”为双核驱动的范式重构。其设计哲学根植于两个核心信条:数据不应在内存中被无谓复制&am…...
苹果内购订阅的“时间陷阱”:如何正确处理UTC与东八区的时间转换(附Java代码)
苹果订阅时间戳的时区陷阱:UTC与东八区转换的实战指南 1. 为什么时间戳处理如此重要? 在苹果应用内购(IAP)订阅系统中,时间戳处理看似简单,实则暗藏玄机。许多开发者都曾踩过这样的坑:用户明明购…...
