代码随想录算法训练营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互操作性,…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...

(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...