DAY30|贪心算法Part04|LeetCode:452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间

devtools/2024/11/20 9:15:45/

目录

LeetCode:452. 用最少数量的箭引爆气球

基本思路

C++代码

LeetCode:435. 无重叠区间

基本思路

C++代码

LeetCode:763.划分字母区间

基本思路

C++代码


LeetCode:452. 用最少数量的箭引爆气球

力扣代码链接

文字讲解:LeetCode:452. 用最少数量的箭引爆气球

视频讲解:算法>贪心算法,判断重叠区间问题

基本思路

        首先我们应该先对气球进行排序,这样才能保证让气球尽可能重叠,因为只有重叠的时候我们才能用更少的箭去射爆气球。那么按照气球起始位置排序,还是按照气球终止位置排序呢?

        其实都可以!只不过对应的遍历顺序不同,我就按照气球的起始位置排序了。既然按照起始位置排序,那么就从前向后遍历气球数组,靠左尽可能让气球重复。

        从前向后遍历遇到重叠的气球了怎么办?如果气球重叠了,重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。以例一为例:

        可以看出首先第一组重叠气球,一定是需要一个箭,气球3,的左边界大于了 第一组重叠气球的最小右边界,所以再需要一支箭来射气球3了。

C++代码

class Solution {
private:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1; // points 不为空至少需要一支箭for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,注意这里不是>=result++; // 需要一支箭}else {  // 气球i和气球i-1挨着points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界}}return result;}
};

        这里points[i][1] = min(points[i - 1][1], points[i][1]); 是为了更新重叠气球的最小右边界,这样的话对于下一次循环过程中,第i+1个气球如果和更新边界后的第i个气球不存在重叠区域,那么就不存在一支箭射爆三个气球的情况。

LeetCode:435. 无重叠区间

力扣代码链接

文字讲解:LeetCode:435. 无重叠区间

视频讲解:算法>贪心算法,依然是判断重叠区间

基本思路

        这个题目和上一题有些相似,都是需要判断区间是否重叠,此时应该按照左边界进行排序还是右边界进行排序呢?其实都可以。主要就是为了让区间尽可能的重叠。

        按照左边界进行排序,我们依旧按照从前向后进行遍历,如果遍历到当前区间的起始位置大于上一个区间的终止位置就说明存在重叠区间,即进行记录。

        另外我们还需要对两个区间的终止位置进行比较,取最小值并赋给变量end,end就是区间分割点,这样当和下个区间相比较时,就可以判断三个区间是否存在公共区间,并且用count用来记录重叠区间的个数。

C++代码

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 count = 0; // 注意这里从0开始,因为是记录重叠区间int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {   if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况else { // 重叠情况 end = min(end, intervals[i][1]);count++;}}return count;}
};

LeetCode:763.划分字母区间

力扣代码链接

文字讲解:LeetCode:763.划分字母区间

视频讲解:算法>贪心算法,寻找最远的出现位置!

基本思路

        题目要求同一字母最多出现在一个片段中,难点在于如何把同一个字母的都圈在同一个区间里呢?在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。

        可以分为如下两步:

  • 统计每一个字符最后出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

C++代码

class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i为字符,hash[i]为字符出现的最后位置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;}
};

http://www.ppmy.cn/devtools/135440.html

相关文章

运维面试题.云计算面试题之四.K8S

常见的k8s运维面试题 1、简述ETCD及其特点? etcd是一个用于配置共享和服务发现的键值存储系统,能够为整个分布式集群存储关键数据,协助集群正常运转 服务端将配置信息存储在etcd中,客户端从etcd中得到配置信息,etcd监听配置信息的变化,发现配置变化通知到客户端 特点 - 安…

云原生周刊:Kubernetes v1.32 要来了

开源项目推荐 Woodpecker Woodpecker 是一款轻量级且功能强大的 CI/CD 引擎&#xff0c;以其高度可扩展性和易用性著称。它支持多种版本控制系统与编程语言&#xff0c;能够灵活适配不同开发流程&#xff0c;帮助团队实现高效的持续集成与交付。无论是个人项目还是大型团队&a…

crypto三方包的用法

文章目录 1. 概念介绍2. 方法与功能2.1 基本用法2.2 加密算法3. 示例代码4. 内容总结我们在上一章回中介绍了"FlutterCacheManager组件"相关的内容,本章回中将介绍一个加密工具包.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 加密主要是为了保护一些重要数据…

Android 源码编译资料集

1、window环境下载Android系统源代码的方法 window环境下载Android系统源代码的方法 - yongfengnice - 博客园 2、安卓构建参考 构建 Android | Android Open Source Project 3、使用windows系统的WSL编译Android10系统 Android系统开发 使用windows系统的WSL编译Androi…

STM32 的 DCMI 接口与 ESP32 的 DVP 接口的区别与作用

STM32 的 DCMI 接口与 ESP32 的 DVP 接口的区别与作用 在嵌入式系统中&#xff0c;图像传感器或摄像头模块的数据传输是一项常见且复杂的任务。为了实现图像数据的高效传输&#xff0c;许多微控制器和处理器设计了专用的接口。这些接口能够处理来自摄像头模块的并行图像数据流…

[控制理论]—位置式PID与增量式PID

位置式PID与增量式PID 1.位置式PID 按模拟PID控制算法&#xff0c;以一系列的采样时刻点kT代表连续时间t&#xff0c;以矩形法数值积分近似代替积分&#xff0c;以一阶后向差分近似代替微分&#xff0c;即&#xff1a; t ≈ k T &#xff08; k 0 , 1 , 2... &#xff09; …

MFC图形函数学习09——画多边形函数

这里所说的多边形是指在同一平面中由多条边构成的封闭图形&#xff0c;强调封闭二字&#xff0c;否则无法进行颜色填充&#xff0c;多边形包括凸多边形和凹多边形。 一、绘制多边形函数 原型&#xff1a;BOOL Polygon(LPPOINT lpPoints,int nCount); 参数&#x…

研究一下前端列表分页列表数据是怎么传给后端的 后端又是如何处理的

前端表单呈现 我们在前端是用的组件化编程 直接用组件绑定的数据结构 我们在vue里面是绑定的这个表单 searchParams 这个searchParams是定义成一个对象 ref 是 vue中一种灵活绑定数据的方式 我们在官方文档中查看 接下来我们查看一下searchParams对象 const searchParams …