代码随想录算法训练营day30 | 452. 用最少数量的箭引爆气球 、435. 无重叠区间、763.划分字母区间
碎碎念:加油
参考:代码随想录
452. 用最少数量的箭引爆气球
题目链接
452. 用最少数量的箭引爆气球
思想
局部最优: 让重叠的气球尽量在一起,用一支弓箭射。
全局最优: 用最少数量的箭引爆气球。
首先对气球进行排序,可以按照左边界排序,这样可能会重叠的气球排在一起。
如何判断气球重叠 ,因为左边界已经排序了,所以判断看右边界即可。如果第i个气球的左边界小于等于前一个气球的右边界,说明两个气球重叠了。
此时我们想看这两个气球和下一个气球是否重叠 ,就需要更新右边界,更新为两个气球右边界的最小值。更新右边界,用来和下一个气球比较。
题解
// cpp
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);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][0], points[i - 1][0]);}}return result;}
};
# python
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) == 0:return 0points.sort(key=lambda x:x[0])result = 1for i in range(1, len(points)):if points[i][0] > points[i - 1][1]:result += 1else:points[i][1] = min(points[i][1], points[i - 1][1])return result
反思
result从1开始,因为显然使得所有气球都爆炸的箭的数量最少为1。
435. 无重叠区间
题目链接
435. 无重叠区间
思想
本题的思想和上一题很相似。
首先排序,让相邻的区间尽可能挨在一起。本做法用的是按照左边界排序。
判断相邻区间是否重叠: 如果当前遍历到的区间的左边界小于上一个区间的右边界,那么它们就是重叠的,result加一,更新右边界的大小,更新为两个区间右边界中较小的那个。
题解
// cpp
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort (intervals.begin(), intervals.end(),cmp);int result = 0;for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {result++;intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);}}return result;}
};
# python
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals) == 0:return 0intervals.sort(key=lambda x:x[0])result = 0for i in range(1, len(intervals)):if intervals[i][0] < intervals[i - 1][1]:result += 1intervals[i][1] = min(intervals[i][1], intervals[i - 1][1])return result
反思
763.划分字母区间
题目链接
763.划分字母区间
思想
遍历字符串,统计每个字符出现的最远位置。
遍历字符串,更新字符的最远出现下标,如果找到字符的最远出现位置下标和当前的下标相等了,就找到了分割点。
题解
// cpp
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> result;int left = 0;int right = 0;for (int i = 0; i < s.size(); i++) {right = max(right, hash[s[i] - 'a']); // 不断更新最右端,取得遍历过的字母的最远的出现位置if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
};
# python
class Solution:def partitionLabels(self, s: str) -> List[int]:hash_ = {}for i, ch in enumerate(s):hash_[ch] = iresult = []left = 0right = 0for i, ch in enumerate(s):right = max(right, hash_[ch])if i == right:result.append(right - left + 1)left = i + 1return result
反思
相关文章:

代码随想录算法训练营day30 | 452. 用最少数量的箭引爆气球 、435. 无重叠区间、763.划分字母区间
碎碎念:加油 参考:代码随想录 452. 用最少数量的箭引爆气球 题目链接 452. 用最少数量的箭引爆气球 思想 局部最优: 让重叠的气球尽量在一起,用一支弓箭射。 全局最优: 用最少数量的箭引爆气球。 首先对气球进行排…...

如何手动修复DLL丢失?2种手动修复dll文件方法
DLL(动态链接库)文件是Windows操作系统中非常重要的组成部分,它们包含了程序运行所需的代码和数据。然而,由于各种原因,如系统更新、软件卸载不当或病毒感染,DLL文件有时会丢失或损坏,导致程序无…...

Node.js(2)——压缩前端html
需求:把回车符(\r)和换行符(\n)去掉后,写入到新的html文件中 步骤: 读取源html文件内容正则替换字符串写入到新的html文件中 示例: 获取html文件中的内容并检查(同时…...
堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言
堆的实现与堆排序及TopK问题的C语言代码 下面是详细的堆实现,包括向上调整、向下调整算法,以及堆排序和解决TopK问题的完整C语言示例代码。 1. 堆的实现 首先,定义堆的数据结构: #include <stdio.h> #include <stdli…...

【C++BFS】1466. 重新规划路线
本文涉及知识点 CBFS算法 LeetCode1466. 重新规划路线 n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部…...

服务器并发模型
服务器: 单循环服务器:服务器在同一时刻只能响应一个客户端的请求 并发服务器模型:服务器在同一时刻可以响应多个客户端的请求 UDP:无连接 TCP:有连接 1.多进程 资源空间消耗大 效率低 2.多线程 相…...

Chapter 23 数据可视化——地图
欢迎大家订阅【Python从入门到精通】专栏,一起探索Python的无限可能! 文章目录 前言一、基础绘图二、视觉映射三、案例分析 前言 随着地理信息系统(GIS)技术的迅猛发展和大数据时代的到来,数据可视化已经成为分析和理…...

Linux笔记 --- 组合数据类型
结构体 简单的定义结构体的方法 struct student {char name;int age;float score; };//使用student模板创建两个结构体变量 struct student Jack,Rose; 结构体中可以存放除了函数以外的任何数据类型的数据,在创建结构体时student被称为结构体模板名称,…...
DaoCloud-Dockfile文件NGINX文件
Dockfile文件 安装依赖,打包,配置NGINX代理,最后把打完的包复制到服务器相应的文件夹下,构建镜像成功。 # syntax docker/dockerfile:experimental FROM xx.xx.xx.xx/public/node:16.14.2 as builder# LABEL maintainer"e…...
耳机行业中MIC ENC
0 Preface/Foreword ENC: Environment Noise Cancellation,环境降噪,主要指在通话过程中,戴着ENC通话降噪耳机的使用者,即使在嘈杂的环境,比如在嘈杂的街区,开着窗运行的汽车上,说话…...
python-自动化办公-Excel-Openpyxl
Python处理Excel数据之Openpyxl 1.1 Openpyxl库的安装使用 openpyxl模块是一个读写Excel 2010文档的 Python 库,如果要处理更早格式的Excel文档,需要用到额外的库,openpyxl是一个比较综合的工具,能够同时读取和修改Excel文档。其…...

图形编辑器基于Paper.js教程10:导入导出svg,导入导出json数据
深入了解Paper.js:实现SVG和JSON的导入导出功能 Paper.js是一款强大的矢量绘图JavaScript库,非常适合用于复杂的图形处理和交互式网页应用。本文将详细介绍如何在Paper.js项目中实现SVG和JSON格式的导入导出功能,这对于开发动态图形编辑器等…...

[STM32][Bootloader][教程]STM32 HAL库 Bootloader开发和测试教程
0. 项目移植 对于不想知道其执行过程的朋友来说,可以直接移植,我的板子是STM32F411CER6, 512K M4内核 项目地址: Bootloader(可以自己写标志位用于自测,项目中这部分代码已经被注释,可以打开自行测试&…...

如何手写一个SpringBoot框架
你好,我是柳岸花开。 在这篇文章中,我们将手写模拟SpringBoot的核心流程,让大家能够以一种简单的方式了解SpringBoot的大概工作原理。 项目结构 我们创建一个工程,包含两个模块: springboot模块,表示Spring…...
vite解决前端跨域步骤
Vite 解决跨域问题的原理主要是通过其内置的开发服务器功能实现的,具体来说,是通过 HTTP 代理(HTTP Proxy)机制。在开发环境中,Vite 服务器可以配置为一个代理服务器,将前端应用发出的请求转发到实际的后端…...

同步交互与异步交互:深入解析与选择
同步交互与异步交互:深入解析与选择 1、同步交互2、异步交互3、选择策略 💖The Begin💖点点关注,收藏不迷路💖 在软件开发的世界里,交互方式主要分为两大类:同步与异步。下面是对这两种方式的解…...

Day1
首先,大概学习了一下用anaconda去创建一个环境(因为Django是有python版本的要求),然后学着去切换环境。 创建环境:conda create -n django_study python3.10 激活环境:conda activate django_study 删除环…...

Introduction to Data Analysis with PySpark
1.DataFrame and RDDs 2.Spark Architecture 3. Data Formats and Data Sources 倘若您觉得我写的好,那么请您动动你的小手粉一下我,你的小小鼓励会带来更大的动力。Thanks....

基于双PI控制器结构的六步逆变器供电无刷直流电机调速simulink仿真
目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 无刷直流电机(BLDCM)原理 4.2 六步换相逆变器 4.3 双PI控制器设计 5.完整工程文件 1.课题概述 基于双PI控制器结构的六步逆变器供电无刷直流电机调速simulink仿真。双PI控制…...
双向链表的基本操作
#include<iostream> #include<cmath> #include<cstring> using namespace std; typedef long long ll; typedef struct line {int data;struct line *pre;//前指针struct line *next;//后指针 }line,*a; line* init_line(line*head) {cout<<"请输…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...