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

算法训练(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题目地址 思路一 先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中&#xff0c;遍历气球数组从交集数组中找交集&#xff0c;找到与…...

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消息的可靠性&#xff0c;即&#xff1a;消息应该至少被消费者处理1次 那么问题来了&#xff1a; 我们该如何确保MQ消息的可靠性&#xff1f;如果真的发送失败&#xff0c;有没有其它的兜底方案&#xff1f; 首先&#xff0c;我们一起分析一下消息丢失的可能…...

Profibus_DP转ModbusTCP网关模块连马保与上位机通讯

Profibus转ModbusTCP网关模块&#xff08;XD-ETHPB20&#xff09;广泛应用于工业自动化领域。例如&#xff0c;可以将Profibus网络中的传感器数据转换为ModbusTCP协议&#xff0c;实现数据的实时监控和远程控制。本文介绍了如何利用Profibus转ModbusTCP网关&#xff08;XD-ETHP…...

移动应用:商城购物类,是最常见的,想出彩或许就差灵犀一指

在移动应用中&#xff0c;商城购物类的非常常见&#xff0c;模式也非常成熟&#xff0c;想要设计的出彩也是有难度的&#xff0c;这次分享一些不同的。...

linux 查看历史命令列表来访问之前的内容的命令是:history

在Linux中&#xff0c;要查看历史命令列表以访问之前的内容&#xff0c;你可以使用history命令。这个命令会显示你当前shell会话&#xff08;或者&#xff0c;如果你指定了参数&#xff0c;可能是所有会话&#xff09;中执行过的命令列表。 基本用法 简单地输入history并按下…...

NAS免费用,鲁大师 AiNAS正式发布,「专业版」年卡仅需264元

7月10日&#xff0c;鲁大师召开新品发布会&#xff0c;正式发布旗下以“提供本地Ai部署和使用能力以及在线NAS功能”并行的复合软件产品&#xff1a;鲁大师 AiNAS。 全新的鲁大师 AiNAS将持续满足现如今大众对于数字化生活的全新需求&#xff0c;将“云存储”的便捷与NAS的大容…...

spring监听事件

1、spring-监听事件基本原理 Spring的事件监听机制和发布订阅机制是很相似的&#xff1a;发布了一个事件后&#xff0c;监听该类型事件的所有监听器会触发相应的处理逻辑 2、Spring 监听事件相关规范 在Spring中&#xff0c;事件监听机制主要涉及到了一下几个关键的规范&#x…...

微软发布E2 TTS: 一种简单但效果优秀的文本转语音技术

本文介绍了一种名为“Embarrassingly Easy Text-to-Speech&#xff08;E2 TTS&#xff09;”的文本转语音系统。 该系统通过将输入文本转换为填充标记字符序列&#xff0c;并基于音频填充值任务训练流匹配基mel频谱生成器&#xff0c;实现了人类水平的自然度和最先进的说话人相…...

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模块&#xff0c;用于处理时间相关的功能 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

要将用户特征与嵌入层进行连接&#xff0c;可以使用深度学习框架&#xff08;如TensorFlow或PyTorch&#xff09;中的基本操作。以下是使用PyTorch的示例代码&#xff0c;展示了如何将用户特征与嵌入层连接起来。 示例代码&#xff08;使用PyTorch&#xff09; 安装 PyTorch 如…...

Ubuntu20.04下修改samba用户密码

Ubuntu20.04下修改samba用户密码 在Ubuntu系统中&#xff0c;修改samba密码通常涉及到两个方面&#xff1a;更改samba用户的密码和重置samba服务的密码数据库。以下是如何进行操作的步骤&#xff1a; 1、更改samba用户密码&#xff1a; 打开终端&#xff0c;使用以下命令更改…...

PHP老照片修复文字识别图像去雾一键抠图微信小程序源码

&#x1f50d;解锁复古魅力&#xff0c;微信小程序黑科技大揭秘&#xff01;老照片修复&更多神奇功能等你来试&#xff01; &#x1f4f8; 【老照片修复&#xff0c;时光倒流的美颜术】 你是否珍藏着一堆泛黄的老照片&#xff0c;却因岁月侵蚀而模糊不清&#xff1f;现在…...

识别色带详解解释

这段代码主要用于检测图像中的绿色区域&#xff0c;并在检测到特定数量的绿色像素时采取相应的动作。下面是每行代码的详细解释&#xff1a; if (divergerColor "green") {目的: 检查当前 divergerColor 是否为 “green”。如果是&#xff0c;则进入代码块进行绿色…...

如何用 Python 绕过 cloudflare(5秒盾) 抓取数据:也不是很难嘛!

大家好!我是爱摸鱼的小鸿,关注我,收看每期的编程干货。 逆向是爬虫工程师进阶必备技能,当我们遇到一个问题时可能会有多种解决途径,而如何做出最高效的抉择又需要经验的积累。本期文章将以实战的方式,带你全面了解 cloudflare(5秒盾) 以及如何绕过使用 cloudflare 服务…...

掌握Conda配置术:conda config命令的深度指南

掌握Conda配置术&#xff1a;conda config命令的深度指南 引言 Conda是一个功能强大的包管理器和环境管理器&#xff0c;广泛用于Python和其他科学计算语言的依赖管理。conda config命令是Conda套件中用于配置和自定义Conda行为的关键工具。通过这个命令&#xff0c;用户可以…...

MySQL:left join 后用 on 还是 where?

在MySQL中&#xff0c;LEFT JOIN用于返回左表&#xff08;即LEFT JOIN关键字左边的表&#xff09;的所有记录&#xff0c;即使在右表中没有匹配的记录。对于那些右表中没有匹配的记录&#xff0c;结果集中右表的部分会被填充为NULL。关于ON和WHERE子句的使用&#xff0c;它们在…...

openfoam生成的非均匀固体Solid数据分析、VTK数据格式分析、以及paraview官方用户指导文档和使用方法

一、openfoam生成的非均匀固体Solid数据分析 二、VTK数据格式分析 三、paraview官方用户指导文档和使用方法 官网文档链接&#xff1a;在paraview软件中&#xff0c;点击工具栏中的help->paraview guide 即可直接跳转到浏览器打开官网指导页面。 官网链接如下&#xff1a;…...

JVM:类的生命周期

文章目录 一、介绍二、加载阶段三、连接阶段1、验证阶段2、准备阶段3、解析阶段 四、初始化阶段 一、介绍 类的生命周期描述了一个类加载、连接&#xff08;验证、准备和解析&#xff09;、初始化、使用、卸载的整个过程。 二、加载阶段 加载&#xff08;Loading&#xff09…...

避开这5个坑!用HipSTR分析NGS数据时最容易出错的STR检测问题

避开这5个坑&#xff01;用HipSTR分析NGS数据时最容易出错的STR检测问题 STR检测在二代测序数据分析中扮演着关键角色&#xff0c;但实际操作中常会遇到各种"坑"。本文将结合实战经验&#xff0c;剖析使用HipSTR进行STR检测时最容易出错的五个关键环节&#xff0c;帮…...

告别WoMic:用VB-Audio Virtual Cable和TCP Socket自建无线麦克风(含参数配置避坑指南)

无线音频传输方案重构&#xff1a;VB-Audio与TCP Socket的工程实践 在音频处理领域&#xff0c;虚拟麦克风技术一直是个既实用又有趣的话题。许多开发者最初接触这一领域是通过WoMic这样的解决方案&#xff0c;但随着项目复杂度提升&#xff0c;人们往往需要更灵活、更可控的自…...

OpCore Simplify:零基础黑苹果配置的智能助手

OpCore Simplify&#xff1a;零基础黑苹果配置的智能助手 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 对于许多电脑爱好者来说&#xff0c;安装黑苹…...

求一个V站邀请码

有没有大佬可以给个邀请码~~~~~~~~~~~~~~~~~~...

UReport2实战:如何优雅地导出多Sheet页报表(动态/静态分页全解析)

UReport2实战&#xff1a;如何优雅地导出多Sheet页报表&#xff08;动态/静态分页全解析&#xff09; 在数据驱动的商业环境中&#xff0c;报表导出功能已成为企业级应用的标配需求。当面对海量数据时&#xff0c;传统的单Sheet页Excel导出方案往往导致文件臃肿、查阅困难。URe…...

Untrunc:10倍速视频修复工具,让损坏的MP4/MOV文件起死回生

Untrunc&#xff1a;10倍速视频修复工具&#xff0c;让损坏的MP4/MOV文件起死回生 【免费下载链接】untrunc Restore a truncated mp4/mov. Improved version of ponchio/untrunc 项目地址: https://gitcode.com/gh_mirrors/un/untrunc 你是否曾经因为视频文件损坏而失去…...

如何快速上手uesave-rs:虚幻引擎存档编辑的终极指南

如何快速上手uesave-rs&#xff1a;虚幻引擎存档编辑的终极指南 【免费下载链接】uesave 项目地址: https://gitcode.com/gh_mirrors/ue/uesave 还在为无法修改心爱游戏的存档而烦恼吗&#xff1f;想要自定义游戏体验却不知从何下手&#xff1f;uesave-rs这款强大的Rus…...

Python异常处理最佳实践:从原理到实践

Python异常处理最佳实践&#xff1a;从原理到实践 1. 背景与动机 在Python编程中&#xff0c;异常处理是一个重要的编程实践。良好的异常处理可以使程序更加健壮&#xff0c;提高代码的可维护性和可读性。然而&#xff0c;许多开发者在处理异常时存在一些常见的问题&#xff0c…...

AI 开发实战:AI 成本监控怎么做,团队才不会越用越贵

AI 开发实战&#xff1a;AI 成本监控怎么做&#xff0c;团队才不会越用越贵 一、这个问题为什么值得专门拿出来做&#xff1f; 在 AI 工程落地里&#xff0c;真正拖慢团队的往往不是模型本身&#xff0c;而是流程和协作方式没有跟上。 围绕“AI 成本监控怎么做&#xff0c;团…...

基于python视频弹幕情感分析 视频可视化 短视频推荐系统 协同过滤推荐算法

1、项目介绍 技术栈&#xff1a; Python语言、Flask框架、 requests爬虫、协同过滤推荐算法、sqlite数据库、bilibili数据、前台后台 B站数据采集分析、推荐与可视化分析系统是一个强大的工具&#xff0c;它利用Python语言、Flask框架、requests爬虫技术、协同过滤推荐算法以及…...