当前位置: 首页 > news >正文

代码随想录算法训练营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.划分字母区间

碎碎念&#xff1a;加油 参考&#xff1a;代码随想录 452. 用最少数量的箭引爆气球 题目链接 452. 用最少数量的箭引爆气球 思想 局部最优&#xff1a; 让重叠的气球尽量在一起&#xff0c;用一支弓箭射。 全局最优&#xff1a; 用最少数量的箭引爆气球。 首先对气球进行排…...

如何手动修复DLL丢失?2种手动修复dll文件方法

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

Node.js(2)——压缩前端html

需求&#xff1a;把回车符&#xff08;\r&#xff09;和换行符&#xff08;\n&#xff09;去掉后&#xff0c;写入到新的html文件中 步骤&#xff1a; 读取源html文件内容正则替换字符串写入到新的html文件中 示例&#xff1a; 获取html文件中的内容并检查&#xff08;同时…...

堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言

堆的实现与堆排序及TopK问题的C语言代码 下面是详细的堆实现&#xff0c;包括向上调整、向下调整算法&#xff0c;以及堆排序和解决TopK问题的完整C语言示例代码。 1. 堆的实现 首先&#xff0c;定义堆的数据结构&#xff1a; #include <stdio.h> #include <stdli…...

【C++BFS】1466. 重新规划路线

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

服务器并发模型

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

Chapter 23 数据可视化——地图

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

Linux笔记 --- 组合数据类型

结构体 简单的定义结构体的方法 struct student {char name;int age;float score; };//使用student模板创建两个结构体变量 struct student Jack,Rose; 结构体中可以存放除了函数以外的任何数据类型的数据&#xff0c;在创建结构体时student被称为结构体模板名称&#xff0c;…...

DaoCloud-Dockfile文件NGINX文件

Dockfile文件 安装依赖&#xff0c;打包&#xff0c;配置NGINX代理&#xff0c;最后把打完的包复制到服务器相应的文件夹下&#xff0c;构建镜像成功。 # 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&#xff1a; Environment Noise Cancellation&#xff0c;环境降噪&#xff0c;主要指在通话过程中&#xff0c;戴着ENC通话降噪耳机的使用者&#xff0c;即使在嘈杂的环境&#xff0c;比如在嘈杂的街区&#xff0c;开着窗运行的汽车上&#xff0c;说话…...

python-自动化办公-Excel-Openpyxl

Python处理Excel数据之Openpyxl 1.1 Openpyxl库的安装使用 openpyxl模块是一个读写Excel 2010文档的 Python 库&#xff0c;如果要处理更早格式的Excel文档&#xff0c;需要用到额外的库&#xff0c;openpyxl是一个比较综合的工具&#xff0c;能够同时读取和修改Excel文档。其…...

图形编辑器基于Paper.js教程10:导入导出svg,导入导出json数据

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

[STM32][Bootloader][教程]STM32 HAL库 Bootloader开发和测试教程

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

如何手写一个SpringBoot框架

你好&#xff0c;我是柳岸花开。 在这篇文章中&#xff0c;我们将手写模拟SpringBoot的核心流程&#xff0c;让大家能够以一种简单的方式了解SpringBoot的大概工作原理。 项目结构 我们创建一个工程&#xff0c;包含两个模块&#xff1a; springboot模块&#xff0c;表示Spring…...

vite解决前端跨域步骤

Vite 解决跨域问题的原理主要是通过其内置的开发服务器功能实现的&#xff0c;具体来说&#xff0c;是通过 HTTP 代理&#xff08;HTTP Proxy&#xff09;机制。在开发环境中&#xff0c;Vite 服务器可以配置为一个代理服务器&#xff0c;将前端应用发出的请求转发到实际的后端…...

同步交互与异步交互:深入解析与选择

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

Day1

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

Introduction to Data Analysis with PySpark

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

基于双PI控制器结构的六步逆变器供电无刷直流电机调速simulink仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 无刷直流电机&#xff08;BLDCM&#xff09;原理 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)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启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全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用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&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 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️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...