代码随想录算法训练营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<<"请输…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...