【LeetCode 刷题】贪心算法(4)-区间问题

此博客为《代码随想录》贪心算法章节的学习笔记,主要内容为贪心算法区间问题的相关题目解析。

文章目录

  • 55. 跳跃游戏
  • 45. 跳跃游戏 II
  • 452. 用最少数量的箭引爆气球
  • 435. 无重叠区间
  • 763. 划分字母区间
  • 56. 合并区间

55. 跳跃游戏

题目链接

class Solution:def canJump(self, nums: List[int]) -> bool:mx = 0  # 最右可达位置for i, jump in enumerate(nums):if i > mx:return Falsemx = max(mx, i + jump)if mx >= len(nums) - 1:return True
  • 维护当前可达的最大右边界,当前下标位置不可达时,返回 Falsemx 已经 >= 最后一个元素的下标时,提前返回 True
  • 也可理解为区间合并问题,将每一个元素对应为 [i, i + jump] 的区间,求是否能够合并出右边界 >= 最后一个元素下标的大区间

45. 跳跃游戏 II

题目链接

class Solution:def jump(self, nums: List[int]) -> int:res = 0cur_rigth, next_right = 0, 0for i in range(len(nums) - 1):next_right = max(next_right, i + nums[i])if i == cur_rigth:cur_rigth = next_rightres += 1return res
  • 要求最小跳跃次数,因此不能每走一步都合并区间,而是应该走到当前步所能达到的尽头,再尝试进行一次跳跃;再当前步走的过程中,同时维护下一次跳跃所能到达的最远边界
  • 由于题目的测试用例均能够到达终点,因此无需特判无法到达的逻辑

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

题目链接

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key=lambda x: x[1])res = 0cur = -inffor start, end in points:if start > cur:cur = endres += 1return res
  • 按照区间右边界升序排列,每次射出的箭都处于当前区间的右边界,以尽可能多的同时覆盖其他区间
  • 一旦当前区间的右边界无法覆盖后续某个区间,则需要新的一支箭,同时射箭的位置调整为新区间的右边界

435. 无重叠区间

题目链接

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x : x[1])res = 0cur_right = -inffor start, end in intervals:if start >= cur_right:res += 1cur_right = endreturn len(intervals) - res
  • 移除最少 等价于 保留最多
  • 同样按照区间右边界升序排列,如果当前区间的起点和之前的区间没有重叠(当前区间起点 >= 之前区间最大右边界),即保留当前区间

763. 划分字母区间

题目链接

class Solution:def partitionLabels(self, s: str) -> List[int]:dic = {}for idx, c in enumerate(s):dic[c] = idxcur_left, cur_right = 0, -infres = []for idx, c in enumerate(s):cur_right = max(cur_right, dic[c])if cur_right == idx:res.append(cur_right - cur_left + 1)cur_left = cur_right + 1cur_right = -infreturn res
  • 先统计每个字母出现的最后位置,之后按顺序遍历,如果当前所有出现过的字母的最后出现位置的最大值 == idx,则表示可以划分为一个合法区间

56. 合并区间

题目链接

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])res = []for start, end in intervals:if res and start <= res[-1][1]:res[-1][1] = max(res[-1][1], end)else:res.append([start, end])return res
  • 按照区间左边界升序排列:因为题目要求返回合并后的区间,按照左边界排序后,如果发生区间合并,也无需修改合并区间左边界的值
  • res[-1] 保存着当前正在合并处理的区间
  • 此题与 “452. 用最少数量的箭引爆气球” 和 “435.无重叠区间” 不是相同的解题思路

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/14812.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

sqli-lab靶场学习(五)——Less15-17(post方法盲注、修改密码)

前言 第11-14关开始用post方法&#xff0c;15-17关会用到盲注&#xff0c;post方法盲注和get方法类似。 Less15 这关是单引号闭合&#xff0c;有报错但没有具体情况的回显&#xff0c;因此适合使用错误盲注。 在用户名密码框分别输入 账号&#xff1a;admin and 11 -- asd…

【Spring】什么是Spring?

什么是Spring&#xff1f; Spring是一个开源的轻量级框架&#xff0c;是为了简化企业级开发而设计的。我们通常讲的Spring一般指的是Spring Framework。Spring的核心是控制反转(IoC-Inversion of Control)和面向切面编程(AOP-Aspect-Oriented Programming)。这些功能使得开发者…

VSCode便捷开发

一、常用插件 Vue 3 Snippets、Vetur、Vue - Official 二、常用开发者工具 三、Vue中使用Element-UI 安装步骤&#xff1a; 1、在VSCode的终端执行如下指令&#xff1a; npm i element-ui -S 2、在main.js中全局引入&#xff1a; import Vue from vue; import ElementUI from …

Android studio 创建aar包给Unity使用

1、aar 是什么&#xff1f; 和 Jar有什么区别 aar 和 jar包 都是压缩包&#xff0c;可以使用压缩软件打开 jar包 用于封装 Java 类及其相关资源 aar 文件是专门为 Android 平台设计的 &#xff0c;可以包含Android的专有内容&#xff0c;比如AndroidManifest.xml 文件 &#…

加速汽车软件升级——堆栈刷写技术的应用与挑战

一、背景和挑战 | 背景&#xff1a; 当前汽车市场竞争激烈&#xff0c;多品牌并存&#xff0c;新车发布速度加快&#xff0c;价格逐渐降低&#xff0c;功能日益多样化。随着车辆功能的不断提升与优化&#xff0c;ECU&#xff08;电子控制单元&#xff09;的代码量也随之增加&…

台湾精锐APEX减速机在半导体制造设备中的应用案例

半导体制造设备对传动系统的精度、可靠性和稳定性要求极高&#xff0c;台湾精锐APEX减速机凭借其低背隙、高精度和高刚性等优势&#xff0c;在半导体制造设备中得到了广泛应用。 案例一&#xff1a;晶圆切割设备 1.应用场景 在晶圆切割过程中&#xff0c;设备需要高精度的运…

Windows安装cwgo,一直安装的是linux平台的

Windows安装cwgo&#xff0c;一直安装的是linux平台的 查看 go env &#xff0c;发现 GOOSlinux 临时修改 GOOS &#xff0c;set GOOSwindows &#xff0c;再安装。 此时&#xff0c;安装的就是 windows 的可执行文件。安装之后再将 GOOS 修改回来即可。

【R语言】plyr包和dplyr包

一、plyr包 plyr扩展包主要是实现数据处理中的“分割-应用-组合”&#xff08;split-apply-combine&#xff09;策略。此策略是指将一个问题分割成更容易操作的部分&#xff0c;再对每一部分进行独立的操作&#xff0c;最后将各部分的操作结果组合起来。 plyr扩展包中的主要函…

google 多模态aistudio Stream Realtime体验

参考&#xff1a; https://aistudio.google.com/live 使用gemini多模态能力&#xff0c;支持语音图像文字输入输出&#xff0c;实时交互体验 支持语音实时交互、摄像头加语音、屏幕视频语音 摄像头 屏幕共享

opentelemetry-collector 配置elasticsearch

一、修改otelcol-config.yaml receivers:otlp:protocols:grpc:endpoint: 0.0.0.0:4317http:endpoint: 0.0.0.0:4318 exporters:debug:verbosity: detailedotlp/jaeger: # Jaeger supports OTLP directlyendpoint: 192.168.31.161:4317tls:insecure: trueotlphttp/prometheus: …

四、OSG学习笔记-基础图元

前一章节&#xff1a; 三、OSG学习笔记-应用基础-CSDN博客https://blog.csdn.net/weixin_36323170/article/details/145514021 代码&#xff1a;CuiQingCheng/OsgStudy - Gitee.com 一、绘制盒子模型 下面一个简单的 demo #include<windows.h> #include<osg/Node&…

保姆级AI开发环境搭建

目录 windows下环境搭建1. Python环境搭建2. 下载vLLM2.1 安装CUDA2.2 安装Pytorch2.3 安装vllm 3. 部署Deepseek&#xff08;huggingface&#xff09;3.1 DeepSeek的优化建议 4. ollama快速部署Deepseek4.1 下载Ollama4.2 配置Ollma4.2 运行模型4.3 其他Ollama命令 linux下环境…

MySQL安装与配置

MySQL是常用的数据库&#xff0c;本篇记录MySQL的安装与配置。 1.首先到官网下载MySQL&#xff0c;这里下载5.7版本的。 https://downloads.mysql.com/archives/community/ 2.下载完成后&#xff0c;解压&#xff0c;然后设置环境变量 3.打开解压的要目录&#xff0c;创建一个…

如何参与开源项目

目的 就是说一下如何参与开源的项目&#xff0c;通过参与QXlsx来说明开源项目是如何参与的&#xff0c;其它的github上的开源项目&#xff0c;也是这样的流程。 关于GitHub: GitHub是一个面向开源及私有软件项目的托管平台&#xff0c;因为只支持Git作为唯一的版本库格式进行…

edu小程序挖掘严重支付逻辑漏洞

edu小程序挖掘严重支付逻辑漏洞 一、敏感信息泄露 打开购电小程序 这里需要输入姓名和学号&#xff0c;直接搜索引擎搜索即可得到&#xff0c;这就不用多说了&#xff0c;但是这里的手机号可以任意输入&#xff0c;只要用户没有绑定手机号这里我们输入自己的手机号抓包直接进…

【论文翻译】DeepSeek-V3论文翻译——DeepSeek-V3 Technical Report——第一部分:引言与模型架构

论文原文链接&#xff1a;DeepSeek-V3/DeepSeek_V3.pdf at main deepseek-ai/DeepSeek-V3 GitHub 特别声明&#xff0c;本文不做任何商业用途&#xff0c;仅作为个人学习相关论文的翻译记录。本文对原文内容直译&#xff0c;一切以论文原文内容为准&#xff0c;对原文作者表示…

Qt之设置QToolBar上的按钮样式

通常给QAction设置icon后,菜单栏的菜单项和工具栏(QToolBar)上对应的按钮会同时显示该icon。工具栏还可以使用setToolButtonStyle函数设置按钮样式,其参数为枚举值: enum ToolButtonStyle {ToolButtonIconOnly,ToolButtonTextOnly,ToolButtonTextBesideIcon,ToolButtonTe…

学习threejs,使用Lensflare模拟镜头眩光

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.Lensflare 二、&…

opencv图像处理

注释详细 1.图像维度&#xff1a;打印出的结果分别为图片像素的横行、纵列和三原色彩色通道 import cv2 imgcv2.imread(pictures//3.png) print(img.shape) cv2.imshow("img",img)#窗口名、变量名 cv2.waitKey(0) 2.图像彩色通道&#xff1a;1张彩色图片&#xff…

harmonyOS生命周期详述

harmonyOS的生命周期分为app(应用)的生命周期和页面的生命周期函数两部分 应用的生命周期-app应用 在app.js中写逻辑,具体有哪些生命周期函数呢,请看下图: onCreated()、onShow()、onHide()、onDestroy()这五部分 页面及组件生命周期 着重说下onShow和onHide,分别代表是不是…