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

【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.无重叠区间” 不是相同的解题思路

相关文章:

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

此博客为《代码随想录》二叉树章节的学习笔记&#xff0c;主要内容为贪心算法区间问题的相关题目解析。 文章目录 55. 跳跃游戏45. 跳跃游戏 II452. 用最少数量的箭引爆气球435. 无重叠区间763. 划分字母区间56. 合并区间 55. 跳跃游戏 题目链接 class Solution:def canJump…...

javaEE初阶————多线程初阶(3)

大家新年快乐呀&#xff0c;今天是第三期啦&#xff0c;大家前几期的内容掌握的怎么样啦&#xff1f; 1&#xff0c;线程死锁 1.1 构成死锁的场景 a&#xff09;一个线程一把锁 这个在java中是不会发生的&#xff0c;因为我们之前讲的可重入机制&#xff0c;在其他语言中可…...

Deep Sleep 96小时:一场没有硝烟的科技保卫战

2025年1月28日凌晨3点&#xff0c;当大多数人还沉浸在梦乡时&#xff0c;一场没有硝烟的战争悄然打响。代号“Deep Sleep”的服务器突遭海量数据洪流冲击&#xff0c;警报声响彻机房&#xff0c;一场针对中国关键信息基础设施的网络攻击来势汹汹&#xff01; 面对美国发起的这场…...

【AI应用】免费的文本转语音工具:微软 Edge TTS 和 开源版 ChatTTS 对比

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 我试用了下Edge TTS&#xff0c;感觉还不错&#xff0c;不过它不支持克隆声音&#xff08;比如自己的声音&#xff09; 微软 Edge TTS 和 开源版 ChatTTS 都是免费的 文本转语音&…...

Deepseek-v3 / Dify api接入飞书机器人go程序

准备工作 开通了接收消息权限的飞书机器人&#xff0c;例如我希望用户跟飞书机器人私聊&#xff0c;就需要开通这个权限&#xff1a;读取用户发给机器人的单聊消息 im:message.p2p_msg:readonly准备好飞书机器人的API key 和Secretdeepseek-v3的api keysecret&#xff1a;http…...

流媒体技术原理

流媒体技术的原理主要涉及以下几个核心概念和技术&#xff1a; 1. 编码和压缩 编码&#xff1a;视频和音频原始数据通常非常庞大。为了传输和存储&#xff0c;首先需要通过编码将这些数据转换成更小、更易处理的格式。常见视频编码标准包括H.264、H.265&#xff08;HEVC&…...

matlab simulink 三级倒立摆LQR控制

1、内容简介 略 matlab simulink 122-三级倒立摆LQR控制 可以交流、咨询、答疑 2、内容说明 略 要求初始条件&#xff3b;0.01 0.01 0.01 0.01 0 0 0 0&#xff3d; 调节时间希望在3s内&#xff0c;超调量尽量的小&#xff0c;最大不能超过0.05&#xff1b; 用simulink的…...

使用令牌桶算法通过redis实现限流

令牌桶算法是一种常用的限流算法&#xff0c;它可以平滑地控制请求的处理速率。在 Java 中结合 Redis 实现令牌桶算法&#xff0c;可以利用 Redis 的原子操作来保证多节点环境下的限流效果。 一 实现思路 初始化令牌桶&#xff1a;在 Redis 中存储令牌桶的相关信息&#xff0…...

Tableau实用技巧 —— 提取Tableau文件中图片

需求背景 在日常开发过程中&#xff0c;我们时常会遇到两种图片提取需求&#xff1a;一是本地报告中的图片文件丢失需要找回&#xff0c;二是从网络论坛中发现有价值的报告图片希望保存使用。针对这些实际应用场景&#xff0c;以下将详细介绍有效的图片提取方法。 解决思路 …...

记一次golang环境的变化

前两天编译打包了了个文件&#xff0c;把env的 goos 搞坏了 导致运行项目一直报错 先是这样 go: unsupported GOOS/GOARCH pair windows/amd64再是这样 /amd64supported GOOS/GOARCH pair linux咱就说&#xff0c;咱也是知道环境配置的有问题 &#xff08; go env GOOS &…...

web直播弹幕抓取分析 signature

声明: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 前言 最近遇到太多难点了卡了很久&am…...

CVE-2024-13025-Codezips 大学管理系统 faculty.php sql 注入分析及拓展

Codezips 里面有很多cms系统&#xff0c;其中的一个College Management System In PHP With Source Code存在sql注入漏洞。 复现 对源码进行下载登录。 里面有很多远程js加载不出来但是不影响接口使用。 对于/college-mgmt-php-master/Front-end/faculty.php接口进行测试。…...

第二个Qt开发实例:在Qt中利用GPIO子系统和sysfs伪文件系统实现按钮(Push Button)点击控制GPIO口(效果为LED2灯的灭和亮)

引言 本文承接博文 https://blog.csdn.net/wenhao_ir/article/details/145420998 里的代码&#xff0c;在那里面代码的基础上添加上利用sysfs伪文件系统实现按钮(Push Button)点击控制GPIO口的代码&#xff0c;进而实现LED2灯的灭和亮。 最终的效果是点击下面的LED按钮实现LED…...

【自动化测试】使用Python selenium类库模拟手人工操作网页

使用Python selenium类库模拟手人工操作网页 背景准备工作安装Python版本安装selenium类库下载selenium驱动配置本地环境变量 自动化脚本输出页面表单自动化填充相关代码 背景 待操作网页必须使用IE浏览器登录访问用户本地只有edge浏览器&#xff0c;通过edge浏览器IE模式访问…...

Elasticsearch:向量搜索的快速介绍

作者&#xff1a;来自 Elastic Valentin Crettaz 本文是三篇系列文章中的第一篇&#xff0c;将深入探讨向量搜索&#xff08;也称为语义搜索&#xff09;的复杂性&#xff0c;以及它在 Elasticsearch 中的实现方式。 本文是三篇系列文章中的第一篇&#xff0c;将深入探讨向量搜…...

低至3折,百度智能云千帆宣布全面支持DeepSeek-R1/V3调用

DeepSeek-R1和 DeepSeek-V3模型已在百度智能云千帆平台上架 。 出品|产业家 新年伊始&#xff0c;百度智能云又传来新动作 。 2月3日百度智能云宣布&#xff0c; DeepSeek-R1和 DeepSeek-V3模型已在百度智能云千帆平台上架&#xff0c;同步推出超低价格方案&#xff0c;并…...

VSCode中使用EmmyLua插件对Unity的tolua断点调试

一.VSCode中搜索安装EmmyLua插件 二.创建和编辑launch.json文件 初始的launch.json是这样的 手动编辑加上一段内容如下图所示&#xff1a; 三.启动调试模式&#xff0c;并选择附加的进程...

RabbitMQ 从入门到精通:从工作模式到集群部署实战(三)

文章目录 使用CLI管理RabbitMQrabbitmqctlrabbitmq-queuesrabbitmq-diagnosticsrabbitmq-pluginsrabbitmq-streamsrabbitmq-upgraderabbitmqadmin 使用CLI管理RabbitMQ RabbitMQ CLI 工具需要安装兼容的 Erlang/OTP版本。 这些工具假定系统区域设置为 UTF-8&#xff08;例如en…...

2025软件授权与保护领域的新趋势

2024年对威步而言是一个重要的里程碑——公司成立35年以来&#xff0c;一直专注于软件安全及软件授权管理&#xff0c;以保护企业的数字资产与知识产权。展望2025年&#xff0c;数字资产盗窃、数据泄露与网络犯罪等威胁仍在持续增长&#xff0c;威步将在新的形势下继续推动技术…...

线段树(点修,区查,区修)

文章目录 什么是线段树&#xff1f;线段树能够解决什么样的问题&#xff1f;模板 什么是线段树&#xff1f; 线段树是一种二叉搜索树&#xff0c;而二叉搜索树&#xff0c;首先满足二叉树&#xff0c;即每个结点最多有两颗子树&#xff0c;并且是一颗搜索树&#xff0c;我们要知…...

深度学习 - 神经网络的原理

## 深度学习 - 神经网络的原理 深度学习是机器学习的一个分支&#xff0c;其核心是模拟人脑神经网络的结构和功能&#xff0c;构建多层的神经网络模型&#xff0c;从数据中学习特征并进行预测或分类。 **神经网络的基本原理&#xff1a;** 1. **神经元模型:** * 神经网…...

DeepSeek辅助段落扩写的能力怎么样?

DeepSeek-R1在学术写作的诸多细节层面展现出了显著的应用价值。接下来我们将通过一系列具体案例&#xff0c;深入探讨该工具如何在扩写、翻译、发表以及内容改进等关键环节为学术写作提供有力支持。在提问环节&#xff0c;DeepSeek-R1能够高效地简化提示词&#xff0c;并精准地…...

深入Linux系列之进程地址空间

深入Linux系列之进程地址空间 1.引入 那么在之前的学习中&#xff0c;我们知道我们创建一个子进程的话&#xff0c;我们可以在代码层面调用fork函数来创建我们的子进程&#xff0c;那么fork函数的返回值根据我们当前所处进程的上下文是返回不同的值&#xff0c;它在父进程中返…...

虚拟DOM与Diff算法:Vue如何高效更新UI?

虚拟DOM与Diff算法&#xff1a;Vue如何高效更新UI&#xff1f; 虚拟DOM与Diff算法&#xff1a;Vue如何高效更新UI&#xff1f;什么是虚拟DOM&#xff1f;定义虚拟DOM的优势 Diff算法&#xff1a;如何高效计算UI差异定义核心思想Diff算法的步骤示例代码 Vue中的虚拟DOM与Diff算法…...

Golang 并发机制-6:掌握优雅的错误处理艺术

并发编程可能是提高软件系统效率和响应能力的一种强有力的技术。它允许多个工作负载同时运行&#xff0c;充分利用现代多核cpu。然而&#xff0c;巨大的能力带来巨大的责任&#xff0c;良好的错误管理是并发编程的主要任务之一。 并发代码的复杂性 并发编程增加了顺序程序所不…...

【MySQL】第二弹---数据库基础全解析:从概念到实践的深度探索

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】 目录 1. 数据库基础 1.1 什么是数据库 1.2 主流数据库 1.3 基本使用 1.3.1 MySQL安装 1.3.2 连接服务器 1.3.3 服务器…...

c++计算机教程

目的 做出-*/%计算机 要求 做出可以计算-*/%的计算机 实现 完整代码 #include<bits/stdc.h> int main() {std::cout<<"加 减- 乘* 除/ 取余% \没有了|(因为可以算三位)"<<"\n"<<"提示:每打完一个符号或打完一个数,\…...

win32汇编环境,对话框程序中自定义工具栏的使用示例三

;运行效果 ;win32汇编环境,对话框程序中自定义工具栏的使用示例三 ;这次是竖着的,以下为生成48*48大小的自定义工具栏图标,自已设计图标样式,显得更专业点。 ;原理是,先生成工具栏控件,再生成图像列表,然后弄几个图标加入图像列表,再把图像列表与工具栏控件关联。需留意…...

集合类不安全问题

ArrayList不是线程安全类&#xff0c;在多线程同时写的情况下&#xff0c;会抛出java.util.ConcurrentModificationException异常 解决办法&#xff1a; 1.使用Vector&#xff08;ArrayList所有方法加synchronized&#xff0c;太重&#xff09; 2.使用Collections.synchronized…...

怎么使用Cursor以及升级Cursor pro会员

什么是cursor Cursor&#xff1a;结合AI技术的代码编辑器&#xff0c;助力开发者提升编码效率与质量。作为Visual Studio Code的一个衍生版本&#xff0c;Cursor继承了其用户熟知的界面和插件兼容性&#xff0c;并加入了革命性的AI特性。这款编辑器自2023年1月推出以来&#x…...

启用gui,启动图形化界面

1、停止服务 2、开启maxscale GUI &#xff0c;修改主配置文件&#xff08;增加框框内两行&#xff09; 3、启动服务 注&#xff1a;如果出现以下启动不成功 考虑权限问题 4、访问http://ip:8989 用户名/密码&#xff1a;admin/mariadb...

03-移除元素

给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k&#xff0c;要通过此题&#xff0c;您需要执行以下操作&#xff1a; 更改…...

LSSVM最小二乘支持向量机多变量多步光伏功率预测(Matlab)

代码下载&#xff1a;LSSVM最小二乘支持向量机多变量多步光伏功率预测&#xff08;Matlab&#xff09; LSSVM最小二乘支持向量机多变量多步光伏功率预测 一、引言 1.1、研究背景与意义 随着全球能源危机和环境问题的日益严重&#xff0c;可再生能源的开发利用成为了世界各国…...

使用Vue开发可复用的Web Components:跨框架组件封装指南

使用Vue开发可复用的Web Components&#xff1a;跨框架组件封装指南 使用Vue开发可复用的Web Components&#xff1a;跨框架组件封装指南引言什么是Web Components&#xff1f;为什么选择Vue开发Web Components&#xff1f; 封装跨框架组件的步骤1. 创建基本的Vue组件2. 将Vue组…...

用AI写游戏1——js实现贪吃蛇

使用模型通义千问 提示词&#xff1a; 用js html css 做一个贪吃蛇的动画 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Snake Game</title><link rel"stylesheet" href"c…...

星闪开发入门级教程之安装编译器与小项目烧录

系列文章目录 星闪开发入门级教程 好久不见&#xff0c;已经好几年没有发文章了&#xff0c;星闪-作为中国原生的新一代近距离无线联接技术品牌。我想着写点东西。为了适合新手&#xff0c;绝对小白文。 文章目录 系列文章目录前言一、Hispark Studio1.安装Hispark Studio2.安…...

java求职学习day32

JavaScript 详解 课程目标&#xff1a; 1 、 JavaScript 介绍 2 、 HTML 和 JavaScript 结合方式 3 、 JavaScript 的使用 4 、 DOM 操作 5 、 BOM 操作 1. JavaScript介绍 (1)虽然是 java 作为前缀&#xff0c;但 java 和 javascript 的关系&#xff0c;就像老婆和老婆…...

【Markdown语法】锚点机制:跳转任意位置

最近写文章时&#xff0c;发现有一个需求&#xff1a;想要实现一种点击跳转到文档中任意位置的功能&#xff0c;这就是锚点机制&#xff0c;就像游戏中的传送锚点&#xff0c;于是写成文章记录一下使用方式。 本文将详细介绍如何使用Markdown创建文档内部跳转&#xff08;即锚…...

Docker安装pypiserver私服

Docker安装pypiserver私服 1 简介 Python开源包管理工具有pypiserver、devpi和Nexus等&#xff0c;pypiserver安装部署比较简单&#xff0c;性能也不错。 搭建pypiserver私服&#xff0c;可以自己构建镜像&#xff0c;也可以使用官网的docker镜像。 # Github地址 https://g…...

基于微信小程序的居住证申报系统设计与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

网站改HTTPS方法

默认的网站建设好后打开的样子那看起来像是钓鱼网站&#xff0c;现在的浏览器特别只能&#xff0c;就是你新买来的电脑默认的浏览器同样也会出现这样“不安全”提示。 传输协议启动了向全球用户安全传输网页内容的流程。然而&#xff0c;随着HTTPS的推出&#xff0c;传输协议通…...

什么是三层交换技术?与二层有什么区别?

什么是三层交换技术&#xff1f;让你的网络飞起来&#xff01; 一. 什么是三层交换技术&#xff1f;二. 工作原理三. 优点四. 应用场景五. 总结 前言 点个免费的赞和关注&#xff0c;有错误的地方请指出&#xff0c;看个人主页有惊喜。 作者&#xff1a;神的孩子都在歌唱 大家好…...

极客说|利用 Azure AI Agent Service 创建自定义 VS Code Chat participant

作者&#xff1a;卢建晖 - 微软高级云技术布道师 「极客说」 是一档专注 AI 时代开发者分享的专栏&#xff0c;我们邀请来自微软以及技术社区专家&#xff0c;带来最前沿的技术干货与实践经验。在这里&#xff0c;您将看到深度教程、最佳实践和创新解决方案。关注「极客说」&a…...

Rust语言进阶之标准输入: stdin用法实例(一百零五)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…...

力扣刷题思路

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言递归70. 爬楼梯112. 路径总和509. 斐波那契数 分治169. 多数元素240.搜索二维矩阵 II --- 二分查找 单调栈 ---「找最近一个比当前值大/小」的问题739. 每日温度…...

MUX-VLAN实验

一、搭建实验拓扑图 二、基本设备配置 设备接口IP地址子网掩码网关PC1E0/0/110.0.1.1255.255.255.0N/APC2E0/0/110.0.1.2255.255.255.0N/APC3E0/0/110.0.1.3255.255.255.0N/APC4E0/0/110.0.1.4255.255.255.0N/APC5E0/0/110.0.1.6255.255.255.0N/Aserver-1E0/0/110.0.1.5255.2…...

音频进阶学习十二——Z变换

文章目录 前言一、Z变换1.Z变换的作用2.Z变换公式3.Z的状态表示1&#xff09; r 1 r1 r12&#xff09; 0 < r < 1 0<r<1 0<r<13&#xff09; r > 1 r>1 r>1 4.关于Z的解释 二、收敛域1.收敛域的定义2.收敛域的表示方式3.ROC的分析1&#xff09;当 …...

理解推理型大语言模型

构建和改进推理模型的方法与策略 本文描述了构建推理模型的四种主要方法&#xff0c;以及我们如何增强大型语言模型&#xff08;LLM&#xff09;的推理能力。我希望这能为你提供有价值的见解&#xff0c;并帮助你了解这一领域快速发展的文献和热潮。 在2024年&#xff0c;LLM…...

【Brinson 绩效归因模型】

Brinson 绩效归因模型 1、前言2、Brinson模型介绍2.1 归因方式2.1.1 BHB 超额收益分解方案2.1.2 BF 超额收益分解方案 2.2 多期 Brinson 模型 1、前言 如此之多的基金&#xff0c;收益率各有不同&#xff0c;即使同等收益率的基金也各有不同的成因。在这种形势下&#xff0c;广…...

如何轻松将Matlab生成的图表嵌入PowerPoint演示文稿

文章目录 Matlab将生成的图添加PPT中一、Matlab脚本1.添加图片函数2.使用示例 总结 Matlab将生成的图添加PPT中 在许多科学、工程和商业领域&#xff0c;Matlab作为一款强大的数值计算和可视化工具&#xff0c;被广泛应用于数据分析和模型构建。然而&#xff0c;当涉及到分享这…...