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

贪心算法之重叠区间问题

以下四个题都是重叠区间问题

452. 用最少数量的箭引爆气球

  • 为了让气球尽可能重叠,先按照气球起始位置由大到小排序
  • tips:sort默认就可以实现以上排序,不需要写cmp
  • 重点:当下一个气球的左边界不小于上一个气球的右边界时(即有重叠的情况),为了判断再下一个气球能否和这两个有重叠,就需要将右边界 point[i][1] 置成小的那个右边界 min(point[i-1][1] , point[i][1])
class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end());int ret = 1;for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) ret++;else points[i][1] = min(points[i - 1][1], points[i][1]);}return ret;}
};

435. 无重叠区间

与上一个题极其相似,首先按照左边界排序,当重叠的时候,舍弃重叠的右边长的那个区间(即将右边界定为小的那个),ret++记录重叠区间个数。

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int ret = 0;for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {ret++;intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);}}return ret;}
};

763. 划分字母区间

  1. 统计每一个字符最后出现的位置
  2. 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}vector<int> ret;int left = 0, right = 0;for (int i = 0; i < s.size(); i++) {right = max(hash[s[i] - 'a'], right);if (right == i) {ret.push_back(right - left + 1);left = i + 1;}}return ret;}
};

56. 合并区间

和上面的435差不多,先按照左边界排序好,将第一组数据添加到ret中,之后如果满足后一个的左边界小于等于这个的右边界时候,更新ret中的这个(ret.back()[1]更新成大的右边界),不满足就把下一个添加进来,for循环是从i=1开始

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());if (intervals.size() == 1)return intervals;vector<vector<int>> ret;ret.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= ret.back()[1]) {ret.back()[1] = max(ret.back()[1], intervals[i][1]);} elseret.push_back(intervals[i]);}return ret;}
};

相关文章:

贪心算法之重叠区间问题

以下四个题都是重叠区间问题 452. 用最少数量的箭引爆气球 为了让气球尽可能重叠&#xff0c;先按照气球起始位置由大到小排序tips&#xff1a;sort默认就可以实现以上排序&#xff0c;不需要写cmp重点&#xff1a;当下一个气球的左边界不小于上一个气球的右边界时(即有重叠的…...

Python爬虫入门教程(非常详细)适合零基础小白

一、什么是爬虫&#xff1f; 1.简单介绍爬虫 爬虫的全称为网络爬虫&#xff0c;简称爬虫&#xff0c;别名有网络机器人&#xff0c;网络蜘蛛等等。 网络爬虫是一种自动获取网页内容的程序&#xff0c;为搜索引擎提供了重要的数据支撑。搜索引擎通过网络爬虫技术&#xff0c;将…...

ArcGIS Pro基础:软件的常用设置:中文语言、自动保存、默认底图

上图所示&#xff0c;在【选项】&#xff08;Options&#xff09;里找到【语言】设置&#xff0c;将语言切换为中文选项&#xff0c;记得在安装软件时&#xff0c;需要提前安装好ArcGIS语言包。 上图所示&#xff0c;在【选项】里找到【编辑】设置&#xff0c;可以更改软件默认…...

依赖注入+中央事件总线:Vue 3组件通信新玩法

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;Vue篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来Vue篇专栏内容:Vue-依赖注入-中央事件总线 目录 中央事件总线使用 依赖注入使用 总结 中央事件总线 依赖注入…...

EasyCVR视频汇聚平台构建远程安防监控:5大亮点解析,助力安防无死角

随着科技的飞速发展&#xff0c;远程安防监控系统已经成为现代社会中不可或缺的一部分&#xff0c;无论是在小区、公共场所还是工业领域&#xff0c;安防监控都发挥着至关重要的作用。而EasyCVR作为一款功能强大的视频监控综合管理平台&#xff0c;其在构建远程安防监控系统方面…...

fastadmin安装插件报500的错误

项目场景&#xff1a; 项目新建后&#xff0c;想在本地项目中安装相关的插件&#xff0c;但是在插件管理页面点击安装的时候一直报500的错误。 问题描述 我们将项目中的调试打开&#xff0c;在application/config.php里修改 app_debug&#xff0c;将false改为true&#xff0c…...

速盾:为什么需要服务器和cdn?

在互联网时代&#xff0c;服务器和CDN&#xff08;内容分发网络&#xff09;起着非常重要的作用。它们是实现高效、稳定和可靠网络服务的关键组成部分。下面我将详细阐述为什么需要服务器和CDN。 首先&#xff0c;服务器是互联网上存储、处理和传输数据的中心枢纽。当我们在浏…...

十四、模拟实现 list 类

Ⅰ . list 基本框架的实现 01 结点的建立 为了实现链表&#xff0c;我们首先要做的应该是建立结点 为了和真正的 list 进行区分&#xff0c;我们仍然在自己的命名空间内实现 代码实现&#xff1a; namespace yxt {// 建立结点template<class T>struct ListNode{T _d…...

JavaScript简介之引入方式

JavaScript 引入方式 提问&#xff1a;CSS的引入方式&#xff1f;在学习 JavaScript 语法之前&#xff0c;我们首先要知道在哪里写 JavaScript 才行。想要在 HTML 中引入 JavaScript&#xff0c;一般有 3 种方式。 外部 JavaScript 内部 JavaScript 元素事件 JavaScript&#…...

同一台电脑上安装不同版本的nodejs(搭配VSCode)

今天拉取了一个前后端分离的项目&#xff0c;运行前端的时候&#xff0c;出现node版本不匹配的情况。 本文章将从安装node.js开始到VSCode使用进行讲解 1、去官网下载node版本 以16版本为例&#xff0c;需要哪个版本&#xff0c;就在网址上把版本号替换即可 https://nodejs.o…...

python小游戏之摇骰子猜大小

最近学习Python的随机数&#xff0c;逻辑判断&#xff0c;循环的用法&#xff0c;就想找一些练习题&#xff0c;比如小游戏猜大小&#xff0c;程序思路如下&#xff1a; 附上源代码如下&#xff1a; 摇骰子的函数&#xff0c;这个函数其实并不需要传任何参数&#xff0c;调用后…...

C++入门——12继承

1.继承 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承呈现了面向对象程序设计的层次结构&#xff0c;体现了由简…...

Python做统计图之美

Python数据分析可视化 案例效果图 import pandas as pd import matplotlib.pyplot as plt import matplotlib# 数据 data {"房型": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],"住宅类型": ["普通宅", "普通宅", "普通宅", &q…...

激光雷达点云投影到图像平面

将激光雷达点云投影到图像平面涉及几何变换和相机模型的应用。以下是该过程的基本原理&#xff1a; 1. 坐标系转换 激光雷达生成的点云通常位于激光雷达的坐标系中&#xff0c;而图像则在相机坐标系中。为了将点云投影到图像上&#xff0c;首先需要将点云从激光雷达坐标系转换…...

[python]将anaconda默认创建环境python版本设置为32位的

首先看看gpt怎么回答的 装了Anaconda。如果尚未安装&#xff0c;可以从Anaconda官网下载适合你的操作系统的安装程序&#xff0c;并按照安装向导进行安装。 二、创建32位Python环境 在Anaconda中&#xff0c;你可以通过修改环境变量来尝试切换到32位模式&#xff08;尽管这并…...

Jmeter+Influxdb+Grafana平台监控性能测试过程(三种方式)

一、Jmeter自带插件监控 下载地址&#xff1a;Install :: JMeter-Plugins.org 安装&#xff1a;下载后文件为jmeter-plugins-manager-1.3.jar&#xff0c;将其放入jmeter安装目录下的lib/ext目录&#xff0c;然后重启jmeter&#xff0c;即可。 启动Jmeter&#xff0c;测试计…...

[创业之路-135] :ERP、PDM、EDM、Git各种的用途和区别,硬件型初创公司需要哪些管理工具?

目录 前言&#xff1a; 一、ERP&#xff08;企业资源计划&#xff09; 二、PDM&#xff08;产品数据管理系统&#xff09; 三、EDM&#xff08;文档管理系统&#xff0c;有时也指电子邮件营销&#xff09; 四、Git 总结 五、硬件研发、生产型企业需要哪些管理工具&#…...

通过剪枝与知识蒸馏优化大型语言模型:NVIDIA在Llama 3.1模型上的实践与创新

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

DOM型xss靶场实验

xss是什么&#xff1f; XSS是一种经常出现在web应用中的计算机安全漏洞&#xff0c;它允许恶意web用户将代码植入到提供给其它用户使用的页面中。比如这些代码包括HTML代码和客户端脚本。攻击者利用XSS漏洞旁路掉访问控制--例如同源策略(same origin policy)。这种类型的漏洞由…...

华为---端口隔离简介和示例配置

目录 1. 端口隔离概念 2. 端口隔离作用 3. 端口隔离优点 4. 端口隔离缺点 5. 端口隔离的方法和应用场景 6. 端口隔离配置 6.1 端口隔离相关配置命令 6.2 端口隔离配置思路 7. 示例配置 7.1 示例场景 7.2 网络拓扑图 7.3 基本配置 7.4端口隔离配置与验证 7.4.1 双…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...