代码随想录算法训练营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<<"请输…...
效率倍增:用快马生成jdk一键配置脚本与docker环境模板
效率倍增:用快马生成JDK一键配置脚本与Docker环境模板 每次新换电脑或者重装系统,最头疼的就是重新配置开发环境。特别是Java开发,光是下载JDK、配置环境变量就得折腾半天。最近发现用InsCode(快马)平台可以快速生成自动化脚本,把…...
中国跨境电商大会代理授权机制与决策影响分析
对于众多寻求通过“中国跨境电商大会”精准撬动海外市场的企业而言,面对琳琅满目的代理商选择,决策过程本身就是一次关于市场洞察、风险评估与资源匹配的深度考验。一个优质的代理商,不仅是展位的“售票员”,更是企业出海战略的“…...
AI 开发实战:AI 成本监控怎么做,团队才不会越用越贵
AI 开发实战:AI 成本监控怎么做,团队才不会越用越贵 一、这个问题为什么值得专门拿出来做? 在 AI 工程落地里,真正拖慢团队的往往不是模型本身,而是流程和协作方式没有跟上。 围绕“AI 成本监控怎么做,团…...
新手避坑指南:用Python+ROS搞定AVP项目中的.bag数据读取与深度图转点云
从零开始处理AVP项目中的.bag数据:深度图与点云实战解析 停车场里75个RealSense相机同时工作,产生的.bag数据像一座未经开采的金矿——但当你第一次打开这些文件时,可能会感到无从下手。作为刚接触ROS和点云处理的新手,我清楚地记…...
Revit插件开发效率革命:热重载技术如何彻底改变你的开发流程
Revit插件开发效率革命:热重载技术如何彻底改变你的开发流程 【免费下载链接】RevitAddInManager Revit AddinManager update .NET assemblies without restart Revit for developer. 项目地址: https://gitcode.com/gh_mirrors/re/RevitAddInManager RevitA…...
PADS 9.5资源包下载与安装教程:附最新许可证生成工具MentorKG使用指南
PADS 9.5完整资源获取与高效安装实战指南 在电子设计自动化(EDA)领域,PADS系列软件凭借其稳定的性能和友好的操作界面,始终保持着广泛的市场占有率。作为经典的9.5版本,虽然已不是最新发布,但在许多企业的标…...
如何快速打造微信风格视频编辑功能?推荐开源神器WeiXinRecordedDemo
如何快速打造微信风格视频编辑功能?推荐开源神器WeiXinRecordedDemo 【免费下载链接】WeiXinRecordedDemo 仿微信视频拍摄UI, 基于ffmpeg的视频录制编辑 项目地址: https://gitcode.com/gh_mirrors/we/WeiXinRecordedDemo WeiXinRecordedDemo是一款基于FFmpe…...
HunyuanVideo-Foley 社区贡献指南:如何提交Prompt案例与优化建议
HunyuanVideo-Foley 社区贡献指南:如何提交Prompt案例与优化建议 1. 为什么你的贡献很重要 开源项目的生命力来自社区的共同参与。HunyuanVideo-Foley作为一款专注于音效生成的AI模型,其效果提升离不开用户的实际使用反馈和创意贡献。你的每一次Prompt…...
Cherry Studio终极模型集成指南:支持DeepSeek-R1等主流LLM的桌面AI神器
Cherry Studio终极模型集成指南:支持DeepSeek-R1等主流LLM的桌面AI神器 【免费下载链接】cherry-studio 🍒 Cherry Studio is a desktop client that supports for multiple LLM providers. Support deepseek-r1 项目地址: https://gitcode.com/GitHub…...
MangoHud与Vulkan视频编码协议:AV1监控完全指南
MangoHud与Vulkan视频编码协议:AV1监控完全指南 【免费下载链接】MangoHud A Vulkan and OpenGL overlay for monitoring FPS, temperatures, CPU/GPU load and more. Discord: https://discordapp.com/invite/Gj5YmBb 项目地址: https://gitcode.com/gh_mirrors/…...
