当前位置: 首页 > 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 双…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

Springboot 高校报修与互助平台小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;高校报修与互助平台小程序被用户普遍使用&#xff0c;为…...

Android Framework预装traceroute执行文件到system/bin下

文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数&#xff08;使用 ICMP Echo 请求&#xff09;-T 参数&#xff08;使用 TCP SYN 包&#xff09; 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11&#xff0c;在/s…...

第21节 Node.js 多进程

Node.js本身是以单线程的模式运行的&#xff0c;但它使用的是事件驱动来处理并发&#xff0c;这样有助于我们在多核 cpu 的系统上创建多个子进程&#xff0c;从而提高性能。 每个子进程总是带有三个流对象&#xff1a;child.stdin, child.stdout和child.stderr。他们可能会共享…...

Razor编程中@Helper的用法大全

文章目录 第一章&#xff1a;Helper基础概念1.1 Helper的定义与作用1.2 Helper的基本语法结构1.3 Helper与HtmlHelper的区别 第二章&#xff1a;基础Helper用法2.1 无参数Helper2.2 带简单参数的Helper2.3 带默认值的参数2.4 使用模型作为参数 第三章&#xff1a;高级Helper用法…...