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

贪心算法之区间问题总结

一、跳跃游戏

跳跃游戏类的问题,不关心每一步怎么跳,只需要关心最大覆盖范围

这里注意i是在当前最大可覆盖范围内遍历,如{2,1,0,1},就是在0~2范围内遍历,千万不能0~numsSize-1范围内遍历!!!

bool canJump(int* nums, int numsSize){//不关心每一步怎么跳,只需要关心最大覆盖范围int cover=0;for(int i=0;i<=cover;i++){cover=fmax(cover,nums[i]);if(cover>=numsSize-1) return true;}return false;
}

二、跳跃游戏II

没见过不好想,建议记下来

关键是当前覆盖范围和下一步覆盖范围都要考虑

计算下一步覆盖范围的目的是用来更新当前覆盖范围,以保证跳跃步数最少

int jump(int* nums, int numsSize){//统计两个覆盖范围:当前这一步的最大覆盖和下一步最大覆盖//如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,//那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点if(numsSize==1) return 0;int curCover=0,nextCover=0;int result=0;for(int i=0;i<=curCover;i++){nextCover=fmax(nextCover,i+nums[i]);if(i==curCover){if(curCover<numsSize-1){result++;curCover=nextCover;if(nextCover>=numsSize-1) break;}else break;}}return result;
}

三、无重叠区间

区间重叠类问题第一步:排序

区间判断重叠方法:若当前区间的右边界大于下一个区间的左边界,则表示有重叠

合并实质上就是更新当前区间的右边界

class Solution {
private:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {//按照区间左边界从小到大排序//若当前区间的右边界大于下一个区间的左边界,则表示有重叠//可以把移除理解成一种特殊的合并,所有重叠区间合并之后,右边界为最小的那个if(intervals.size()==1) return 0;sort(intervals.begin(),intervals.end(),cmp);int result=0;for(int i=1;i<intervals.size();i++){if(intervals[i-1][1]>intervals[i][0]){intervals[i][1]=fmin(intervals[i-1][1],intervals[i][1]);result++;}}return result;}
};

四、用最少数量的箭引爆气球

实际上这题就是在问:有多少组无重叠区间,和上题都在研究重叠与无重叠区间的问题

注意本题的重叠区间内的所有区间的右边界和上题一样,也要更新为重叠区间里最小的右边界

因为找最大重叠个数的重叠区间看的是“短板”!!!

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()==1) return 1;sort(points.begin(),points.end(),cmp);int result=1;for(int i=1;i<points.size();i++){if(points[i-1][1]<pointss[i][0])result++;elsepoints[i][1]=min(points[i-1][1],points[i][1]);}return result;}
};

五、划分字母区间

本题实际上就是在问:求每个闭包的长度

所以关键就是,怎么判断闭包的起始位置

这就和跳跃游戏II有点像了~

class Solution {
public:vector<int> partitionLabels(string s) {//开辟一个数组记录每个字母的最后出现位置int cover[27];for(int i=0;i<s.size();i++)cover[s[i]-'a']=i;//到达最大覆盖距离时(可以理解成这个闭包的最大覆盖范围),//记录该覆盖范围的长度,然后向后移动一个位置int left=0,right=0;vector<int> result;for(int i=0;i<s.size();i++){right=max(right,cover[s[i]-'a']);if(i==right){result.push_back(right-left+1);left=i+1;}}return result;}
};

六、合并区间

所谓合并区间,其实就是重叠区间的右边界取重叠区间内最大右边界

如果下一个区间和当前重叠区间重叠,则更新当前重叠区间的右边界;

若不重叠,说明是新的闭包,上一个重叠区间更新完成,插入result新的重叠区间

class Solution {
private:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//所谓合并区间,其实就是重叠区间的右边界取重叠区间内最大右边界//如果下一个区间和当前重叠区间重叠,则更新当前重叠区间的右边界;//若不重叠,说明是新的闭包,上一个重叠区间更新完成,插入result新的重叠区间if(intervals.size()==1) return intervals;sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> result;result.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(intervals[i-1][1]>=intervals[i][0])result.back()[1]=max(intervals[i][1],result.back()[1]);elseresult.push_back(intervals[i]);}return result;}
};

相关文章:

贪心算法之区间问题总结

一、跳跃游戏跳跃游戏类的问题&#xff0c;不关心每一步怎么跳&#xff0c;只需要关心最大覆盖范围这里注意i是在当前最大可覆盖范围内遍历&#xff0c;如{2,1,0,1}&#xff0c;就是在0~2范围内遍历&#xff0c;千万不能0~numsSize-1范围内遍历&#xff01;&#xff01;&#x…...

无线WiFi安全渗透与攻防(七)之WIFI07-WEP-wifite自动化渗透WEP加密

WIFI07-WEP-wifite自动化渗透WEP加密 1.wifite介绍 wifite是一款自动化wep、wpa以及wps破解工具&#xff0c;不支持windows和osx。wifite的特点是可以同时攻击多个采用wep和wpa加密的网络。wifite只需简单的配置即可自动化运行&#xff0c;期间无需人工干预。 目前支持任何li…...

震撼,支持多模态模型的ChatGPT 4.0发布了

最近几个月&#xff0c;互联网和科技圈几乎ChatGPT刷屏了&#xff0c;各种关于ChatGPT的概念和应用的帖子也是围绕在周围。当去年年底ChatGPT发布的那几天&#xff0c;ChatGPT确实震撼到了所有人&#xff0c;原来AI还可以这么玩&#xff0c;并且对国内的那些所谓的人工智能公司…...

IDEA常用插件列表

一 背景 IDEA常用插件列表&#xff0c;用来提供工作效率。你都安装了吗 IntelliJ IDEA 默认安装并提供了非常多的工具&#xff0c;比如 Maven Integration、Markdown support、SSH Remote Run 等。其中有很多好用&#xff0c;但是不为人知的工具。 二 插件列表 阿里代码规约…...

比df更好用的命令!

大家好&#xff0c;我是良许。 对于分析磁盘使用情况&#xff0c;有两个非常好用的命令&#xff1a;du 和 df 。简单来说&#xff0c;这两个命令的作用是这样的&#xff1a; du 命令&#xff1a;它是英文单词 disk usage 的简写&#xff0c;主要用于查看文件与目录占用多少磁…...

【Git使用学习】记录学习过程(1)

安装就省略了&#xff0c;安装结果如下。 Git Bash&#xff1a;这是一个模拟Linux环境的命令行工具&#xff0c;可以使用Git的所有功能。Git GUI&#xff1a;这是一个图形化界面的工具&#xff0c;可以方便地执行Git的常用操作。Git CMD&#xff1a;这是一个Windows命令行工具&…...

K_A18_001 基于STM32等单片机采集MQ2传感参数串口与OLED0.96双显示

K_A18_001 基于STM32等单片机采集MQ2传感参数串口与OLED0.96双显示一、资源说明二、基本参数参数引脚说明三、驱动说明IIC地址/采集通道选择/时序对应程序:四、部分代码说明1、接线引脚定义1.1、STC89C52RCMQ2传感参模块1.2、STM32F103C8T6MQ2传感参模块五、基础知识学习与相关…...

【云原生·Docker】常用命令

目录 &#x1f341;1、管理命令 &#x1f341;2、帮助命令 &#x1f341;3、镜像命令 &#x1f341;4、容器命令 &#x1f342;4.1.查看容器 &#x1f342;4.2.创建容器 &#x1f342;4.3.删除容器 &#x1f342;4.4.拷贝文件 &#x1f342;4.5.查看容器IP &#x1f341;5、部署…...

户外露营储能电源芯片CSU3AF10

户外露营的项目有很多&#xff0c;随着户外储能电源的发展&#xff0c;越来越多的电子产品可以在户外使用&#xff0c;也不用担心因为在户外时间过长而手机或者其他电子产品电量耗尽。户外储能电源可保证人们随时随地的用电需求&#xff0c;同时也可以满足家电炊具的供电需求&a…...

无线WiFi安全渗透与攻防(八)之WEP-Hirte渗透WEP加密

WEP-渗透WEP新思路–Hirte 1.Hirte介绍 Hirte是破解无线网络WEP Key的一种攻击类型 只要客户端设备&#xff08;笔记本电脑&#xff0c;手机等&#xff09;连接过的无线网络&#xff0c;那些WIFI即使是不在攻击者范围内也都能被破解&#xff0c;因为该wifi的WEP密钥和配置文…...

前端常考面试题整理

display:none与visibility:hidden的区别 这两个属性都是让元素隐藏&#xff0c;不可见。两者区别如下&#xff1a; &#xff08;1&#xff09;在渲染树中 display:none会让元素完全从渲染树中消失&#xff0c;渲染时不会占据任何空间&#xff1b;visibility:hidden不会让元素…...

二十二、身份验证与权限

一、 准备工作 为了讲清楚身份验证与权限&#xff0c;我们再创建一个应用projects,设计模型如下&#xff1a; class Project(models.Model):name models.CharField(项目名称, max_length20, help_text项目名称)desc models.CharField(项目描述, max_length200, help_text项目…...

k8s pod 升级与回滚

当集群中的某个服务需要升级时&#xff0c;我们需要停止目前与该服务相关的所有pod&#xff0c;然后下载新版本镜像并创建新的pod。如果集群规模比较大&#xff0c;则这个工作变成了一个挑战&#xff0c;而且先全部停止然后逐步升级的方式会导致较长时间的服务不可用。kubernet…...

【Go】Go语言开发环境安装

【Go】Go语言开发环境安装 导入 安装环境&#xff1a;Winowds 我现在是win7安装的&#xff0c;与win10整体步骤是一样的&#xff0c;只是部分显示的时候有点差异不影响&#xff1b; 【名词】 编译器&#xff1a;先将代码编译成可执行文件&#xff0c;再执行&#xff1b; —…...

el-switch使用

效果图&#xff1a; 1.表格代码&#xff0c;给el-waitch加上change事件 <el-table-column prop"status" label"状态" align"center" width"150"> <template slot-sc…...

【算法入门】字符串基础

目录 一.字符串引言1.字符串基础二.洛谷P5734详解1.字符串相关库函数&#x1f4ab;&#xff08;1&#xff09; strcpy函数 &#x1f4ab;&#x1f4ab;&#xff08;2&#xff09; strcat函数 &#x1f4ab;&#x1f4ab;&#xff08;3&#xff09;strstr函数 &#x1f4ab;2.题…...

前端面试题 —— 浏览器原理(二)

目录 一、有哪些可能引起前端安全的问题? 二、网络劫持有哪几种&#xff0c;如何防范&#xff1f; 三、浏览器渲染进程的线程有哪些 四、僵尸进程和孤儿进程是什么&#xff1f; 五、为什么需要浏览器缓存&#xff1f; 六、对浏览器的理解 七、CSS 如何阻塞文档解析&…...

对于植物神经紊乱的治疗 中医采用辩证论治的方法

植物神经紊乱是由于心理压力过大、长期生活不规律所导致的一种疾病&#xff0c;这种疾病的发生往往是症状多样、涉及广泛的。当患有植物神经紊乱之后&#xff0c;主要的症状会以躯体化障碍为常见症状&#xff0c;但是很多患者还会出现情绪失控、睡眠障碍等问题。 对于植物神经紊…...

chatGPT之Python API启用上下文管理

chatGPT已经爆火一段时间了&#xff0c;我想大多数的开发者都在默默的在开发和测试当中&#xff0c;可能也是因为这个原因所以现在很难找到关于开发中遇到的一些坑或者方法和技巧。为什么别人的机器人能联想之前的语料&#xff0c;而你的却像个每次都只如初见的高冷机器人&…...

油田钻井实时在线监测系统

油田钻井的井下油层的压力不断变化&#xff0c;环境深度和压力巨大&#xff0c;且井下原油具有一定的流动性&#xff0c;实时在线压力监测是石油开采行业的难点。为更好地了解油田开采过程中油层的状况&#xff0c;提高油田开采效率和产量&#xff0c;油田钻井实时在线监测系统…...

Google I/O 2026 推出 Antigravity SDK:本地构建 AI Agent,灵活定制功能

Antigravity SDK 登场当开发者需要将 AI 能力嵌入自有应用时&#xff0c;常见做法是通过 API 调用远程 Agent 服务&#xff0c;但这种方式存在延迟高、定制性差、依赖网络等问题。据悉&#xff0c;Google 在 I/O 2026 大会上给出了另一种解法 ---- Antigravity SDK&#xff0c;…...

别再死记命令了!用ENSP模拟企业网,手把手教你配置VRRP+MSTP实现网关和链路双备份

企业网络高可用实战&#xff1a;用ENSP构建VRRPMSTP双冗余架构 刚接触企业网络设计的工程师常陷入一个误区&#xff1a;把网络设备配置等同于命令记忆。我曾见过一位学员能完整背诵VRRP的配置指令&#xff0c;却在真实网络故障时手足无措——因为他从未理解这些命令背后的网络逻…...

告别Office风格审美疲劳:用SARibbon给你的Qt应用换个WPS范儿的清爽界面

告别Office风格审美疲劳&#xff1a;用SARibbon给你的Qt应用换个WPS范儿的清爽界面 在软件开发领域&#xff0c;界面设计往往决定了用户的第一印象。对于使用Qt框架开发桌面应用的程序员来说&#xff0c;Ribbon界面已经成为现代办公软件的标配。然而&#xff0c;传统的Office风…...

告别‘失联’服务器:利用校园网内网固定IP,通过SSH隧道实现无公网访问的服务器管理(WinSCP文件传输教程)

内网服务器高效管理&#xff1a;SSH隧道与WinSCP实战指南 在分布式办公和远程协作日益普及的今天&#xff0c;许多技术团队都面临着内网服务器管理的挑战。想象一下这样的场景&#xff1a;你的核心数据库服务器位于公司内网&#xff0c;没有公网IP&#xff1b;或者你的开发测试…...

大疆L1点云与ContextCapture融合实战:从Sbet轨迹到三维实景模型的完整数据流

1. 大疆L1点云与ContextCapture融合的核心价值 如果你手头有大疆L1激光雷达采集的点云数据&#xff0c;想要在ContextCapture&#xff08;现在叫iTwin Capture&#xff09;里生成高精度三维模型&#xff0c;但卡在了轨迹文件转换这一步&#xff0c;那这篇文章就是为你准备的。…...

长期项目中使用Taotoken观测用量与优化API调用策略

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 长期项目中使用Taotoken观测用量与优化API调用策略 在持续数月的开发项目中&#xff0c;团队对大型语言模型的调用往往从简单的功能…...

Perplexity数据验证功能全链路解析(98.7%准确率背后的4层校验架构)

更多请点击&#xff1a; https://kaifayun.com 第一章&#xff1a;Perplexity数据验证功能全链路解析&#xff08;98.7%准确率背后的4层校验架构&#xff09; Perplexity 的数据验证并非单一规则匹配&#xff0c;而是融合语义一致性、来源可信度、时效性约束与逻辑闭环性的四维…...

AntiDupl.NET终极指南:免费开源图片去重工具快速清理硬盘重复图片

AntiDupl.NET终极指南&#xff1a;免费开源图片去重工具快速清理硬盘重复图片 【免费下载链接】AntiDupl A program to search similar and defect pictures on the disk 项目地址: https://gitcode.com/gh_mirrors/an/AntiDupl 你是否曾为电脑中堆积如山的重复图片而烦…...

Taotoken的用量分析与账单追溯功能让财务对账更轻松

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 Taotoken的用量分析与账单追溯功能让财务对账更轻松 对于依赖大模型API进行开发的企业或项目团队而言&#xff0c;成本核算与费用分…...

Midjourney年度订阅避坑手册:92%用户不知的3大失效风险——自动续费陷阱、区域定价欺诈、账户绑定漏洞

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Midjourney年度订阅优惠全景透视 Midjourney 作为当前主流的 AI 图像生成服务&#xff0c;其年度订阅计划长期受到创作者与团队用户的高度关注。相比月度订阅&#xff0c;年度方案不仅显著降低单月成本…...