跳跃游戏的最优解法——贪心算法的智慧与实践
跳跃游戏的最优解法——贪心算法的智慧与实践
跳跃游戏是一类经典的算法题,既有趣又充满挑战,不仅能锻炼思维能力,还能直观展现贪心算法的核心思想。今天,我们从题目入手,拆解贪心算法的原理,用通俗易懂的方式解析为什么它能够成为跳跃游戏问题的最优解。
1. 题目背景:跳跃游戏的规则
我们以「跳跃游戏I」为例(英文叫 Jump Game
):给定一个数组,每个元素表示你在该位置可以跳跃的最大步数,问是否能够跳到数组的最后一个位置。
例如:
输入:nums = [2,3,1,1,4]
输出:True(解释:从下标0跳到1,再跳到4,就到达了终点)
如果转成布尔问题,它问的其实是:“从起点开始,能不能到达终点?”
2. 解法探索:贪心算法的核心思想
在跳跃游戏中,核心任务是不断地评估自己能跳到的“最远位置”。贪心算法的关键在于每一步都做出局部最优选择,尽可能让“最远可达位置”覆盖更多的区域。
贪心思路
- 初始化最远可达位置为 0;
- 从起点开始,逐步更新“最远可达位置”;
- 如果某个位置的“最远可达位置”小于当前下标,说明无法继续前进;
- 如果能覆盖数组的最后一位,返回True。
贪心的本质是:用最少的思考和计算,只关注当下最优的选择,而不纠结未来的每一步怎么跳。
3. 实战代码解析:贪心算法
我们来看代码实现,并配以详细注释。
def canJump(nums):# 初始化最远可达位置为 0farthest = 0# 遍历数组中的每个位置for i in range(len(nums)):# 如果当前位置超出了最远可达位置,直接返回 Falseif i > farthest:return False# 更新最远可达位置farthest = max(farthest, i + nums[i])# 打印调试信息(可选)print(f"当前下标: {i}, 可跳范围: {nums[i]}, 最远可达: {farthest}")# 如果最远可达位置覆盖了数组末尾,返回 Trueif farthest >= len(nums) - 1:return True# 如果循环结束仍未覆盖终点,返回 Falsereturn False
代码运行示例
让我们用具体的例子验证代码效果:
nums = [2, 3, 1, 1, 4]
print(canJump(nums))
# 输出:
# 当前下标: 0, 可跳范围: 2, 最远可达: 2
# 当前下标: 1, 可跳范围: 3, 最远可达: 4
# True
解析:
- 从起点(下标 0)开始,最远能跳到下标 2;
- 到下标 1 时,根据跳跃能力(最大范围是 3),最远可达位置更新为下标 4;
- 因为覆盖了数组的最后一个位置,答案是
True
。
4. 贪心算法的优劣分析
优势
- 效率高:时间复杂度为 O(n),只需遍历一次数组。
- 易实现:核心逻辑简单明确,只关注“最远可达位置”。
劣势
- 局限性:贪心算法不是通用解法,适用于这类“局部最优可推导全局最优”的问题,但无法解决所有的跳跃游戏变种。
- 不可逆:一旦做出贪心选择,就不会回头,这在某些情况可能导致最优解的遗漏(但对于跳跃游戏,这种情况不会发生)。
5. 拓展题型:最少跳跃步数
跳跃游戏的另一种变体是「跳跃游戏II」,要求计算跳到数组末尾所需的最少跳跃次数。这同样可以用贪心算法解决,只是逻辑稍作调整。
代码示例:计算最少跳跃次数
def jump(nums):jumps = 0 # 记录总的跳跃次数cur_end = 0 # 当前跳跃能到的最远位置farthest = 0 # 总的最远可达位置for i in range(len(nums) - 1):farthest = max(farthest, i + nums[i])# 如果到达了当前跳跃的最远位置if i == cur_end:jumps += 1 # 增加一次跳跃cur_end = farthest # 更新当前跳跃的最远位置# 打印调试信息(可选)print(f"跳跃次数: {jumps}, 当前范围终点: {cur_end}, 最远可达: {farthest}")return jumps
运行示例:
nums = [2, 3, 1, 1, 4]
print(jump(nums))
# 输出:
# 跳跃次数: 1, 当前范围终点: 2, 最远可达: 2
# 跳跃次数: 2, 当前范围终点: 4, 最远可达: 4
# 2
解析:
- 第一次跳跃覆盖到下标 2;
- 第二次跳跃直接覆盖到终点,总共需要两次跳跃。
6. 结语:贪心的智慧,跳跃的艺术
贪心算法是算法设计中的一把利器,它在跳跃游戏中不仅高效而且简单,让人不禁感慨“智慧源自规则”。然而,贪心并非万能,它适用于“局部最优推导全局最优”的场景,使用时必须结合问题特性。
相关文章:
跳跃游戏的最优解法——贪心算法的智慧与实践
跳跃游戏的最优解法——贪心算法的智慧与实践 跳跃游戏是一类经典的算法题,既有趣又充满挑战,不仅能锻炼思维能力,还能直观展现贪心算法的核心思想。今天,我们从题目入手,拆解贪心算法的原理,用通俗易懂的…...
搭建docker registry私服,并且支持https推送
搭建docker registry私服,并且支持https推送 一、为什么写这篇文章二、搭建过程三、验证 一、为什么写这篇文章 网上关于搭建docker registry的文章一大把,但是都是配置为http方式推送,且需要显示端口,这个在真正项目使用中&…...
UniApp Vue 3 中的网络请求封装及用法
在UniApp中,结合Vue 3的强大特性,进行网络请求的封装是项目中常见的需求。这样的封装不仅提高了代码的可维护性,还使得在组件中使用网络请求更加简洁。本文将详细介绍UniApp Vue 3中的网络请求封装,并提供一个简单的用法示例。 创…...
策略模式结合模板方法模式
之前学习了策略模式加模板方法模式 策略模式单独详解 模板方法模式单独详解 这里回忆起完全可以进行策略和模板方法模式的组合。 import java.util.HashMap; import java.util.Map;// 上下文对象(解决参数传递问题) class OrderContext {private final…...
每日算法-250407
记录一下今天刷的三道 LeetCode 题目。 2389. 和有限的最长子序列 题目 思路 排序 前缀和 二分查找 解题过程 理解题意: 题目要求我们对于 queries 数组中的每个查询值 q,找出 nums 数组中元素和 小于等于 q 的 最长子序列 的长度。注意,是子序列&am…...
【Git “ls-tree“ 命令详解】
本章目录: 1. 命令简介2. 命令的基本语法和用法基本语法常见使用场景示例 1:查看当前提交的文件树示例 2:查看某个分支的文件树示例 3:查看特定路径下的文件树 3. 命令的常用选项及参数常用选项: 4. 命令的执行示例示例 1…...
Text-to-SQL技术深度解析:从理论突破到工程实践
引言:Text-to-SQL的技术演进与当代价值 在当今数据驱动的商业环境中,结构化数据查询语言(SQL)仍然是访问和分析企业数据的核心工具。然而,SQL的专业性要求构成了数据民主化的主要障碍——据统计,仅约35%的开发人员接受过系统的SQL培训,而超过51%的专业岗位需要SQL技能。T…...
Spring Boot 整合 Servlet三大组件(Servlet / Filter / Listene)
Spring Boot 整合 “Servlet三大组件“ ( Servlet / Filter / Listene ) 目录如下: pom.xml配置 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.…...
react 18 可中断的理解以及应用
React 的“可中断(interruptible)”渲染,指的是 React 在执行渲染过程中可以暂停、中断、再继续或放弃更新。这是 React 18 引入的并发特性的一部分,目的是让界面响应更流畅,防止“卡顿”。 📖 举个例子&am…...
C++使用Qt Charts可视化大规模点集
引言 数据可视化是数据分析和决策过程中的重要环节。随着数据量的不断增长,如何高效地可视化大规模数据集成为了一个挑战。Qt Charts 提供了一个强大的工具集,用于创建直观的数据可视化图表。本文将探讨如何使用 C 和 Qt Charts 可视化大规模点集&#…...
第一部分——Docker篇 第二章 Docker安装
关于系统的改造探索 开篇:系统改造的调研报告 第一部分——Docker篇 第一章 Docker容器 第二章 Docker安装 第三章 构建自定义镜像 第四章 搭建镜像仓库 第五章 容器编排 第六章 容器监控 文章目录 关于系统的改造探索第一部分——Docker篇 前言一、在线环境二、…...
Transformer - 多头自注意力机制复现
一、数学原理 1. 多头注意力机制 多头注意力机制允许模型在不同的表示子空间中关注输入序列的不同部分。它通过并行计算多个注意力头来实现这一点,每个头学习序列的不同部分。 2. 注意力分数计算 3. 掩码机制 掩码机制用于防止模型访问某些位置的信息。例如&…...
SpringCloud-快速通关(一)
本文是基于【雷丰阳老师:尚硅谷2025最新SpringCloud - 快速通关】进行实践操作,并对雷神的笔记做一个更详细的补充,供大家学习参考,一起加油! 视频地址:SpringCloud快速通关_教程简介_哔哩哔哩_bilibili …...
Ansible Playbook详解:自动化配置管理的核心
1. 引言 Ansible Playbook是Ansible自动化系统的核心,它使用YAML格式描述一系列要在远程系统上执行的任务。通过Playbook,我们可以将复杂的IT操作转化为可重复、可版本控制的代码。本文将深入探讨Playbook的结构、语法和高级特性,帮助读者掌握编写高效、可维护的Playbook的…...
【实践总结】如何编写“多角色适配”的高质量技术文档?
一份文档想要“一稿多用”?先别急着开写!先读完这篇总结,你将学会如何拆解目标、设计结构、提升可读性,让文档不再顾此失彼。 🔍 背景:一文多用,常常适得其反 在实际的软件项目中,我们往往希望通过一份设计文档,同时完成以下多个目标: ✅ 描述系统结构,便于团队成…...
Ansible 入门教程:从零开始掌握自动化运维
1. 引言 在当今快速发展的IT环境中,自动化运维已成为提高效率、减少人为错误的关键。Ansible作为一个简单yet强大的自动化工具,正受到越来越多DevOps工程师的青睐。本文将带领读者从零开始,逐步掌握Ansible的核心概念和基本用法,为自动化运维之路打下坚实基础。 2. Ansible简…...
WSL2迁移教程:如何备份和转移Ubuntu子系统到新位置
WSL2迁移教程:如何备份和转移Ubuntu子系统到新位置 文章目录 WSL2迁移教程:如何备份和转移Ubuntu子系统到新位置前言环境准备迁移步骤详解1. 查看当前WSL发行版状态2. 关闭所有WSL实例3. 导出WSL发行版4. 注销原有WSL发行版5. 导入WSL发行版到新位置6. 验…...
【备赛】eeprom
简介 EEPROM即电可擦可编程只读存储器,属于非易失存储芯片。 它能电擦除、多次编程,支持字节级操作。 掉电后数据不丢失。 蓝桥杯嵌入式的eeprom使用AT24C02,使用IIC通信协议。 驱动的函数官方已经写好,我们只需要移植并使用就…...
Pytorch torch.utils.data.dataloader.default_collate 介绍
torch.utils.data.dataloader.default_collate 是 PyTorch 中 DataLoader 默认的 collate_fn 函数,用于将一个批次的样本数据合并成张量(Tensor)或其他结构化数据格式。以下是关于 default_collate 的详细介绍: 1. 功能 default…...
Github最新AI工具汇总2025年4月份第2周
根据GitHub官方动态及开发者生态最新进展,以下是2025年4月第二周(截至4月7日)值得关注的AI工具与技术更新汇总: 1. GitHub Copilot Agent Mode全量发布 核心功能:在VS Code中启用Agent模式后,Copilot可自主…...
2013年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2013年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激励学生学习数学的积极性,提高学…...
LabVIEW 开发如何降本增效
在 LabVIEW 开发领域,如何在确保项目质量的同时降低开发成本,是众多企业和开发者共同关注的焦点。这不仅关乎资源的高效利用,更影响项目的投资回报率和市场竞争力。下面,我们将从多个维度深入剖析降本策略,并结合具体案…...
云存储服务器的作用都有哪些?
云存储服务器是一种用来存储和管理企业数据信息的服务器,可以为企业与组织提供一个可靠、安全和可扩展的存储平台,能够帮助个人和企业将数据信息存储在云端,以此来实现数据信息的备份、共享和访问功能。 云存储服务器支持多个用户共同访问和共…...
可编辑33页PPT | AI智能智慧工厂厂区完全整体解决方案
荐言摘要:AI智能智慧工厂厂区完全整体解决方案是一种集成了先进的人工智能技术、工业自动化系统和创新管理理念的综合性方案,旨在提升生产效率、降低成本、实现灵活生产,并推动工厂的智能化发展。 随着技术的不断进步,工厂架构经…...
vmware虚拟机上Ubuntu或者其他系统无法联网的解决方法
一、检查虚拟机是否开启了网络服务 打开方式:控制面板->-管理工具--->服务 查找 VMware DHCP Service 和VMware NAT Service ,确保这两个服务已经启动。如下图,没有启动就点击启动。 二、设置网络类型 我们一般使用前两种多一些&…...
python中pyside6多个py文件生成exe
网上见到的教程大多数都是pyinstaller安装单个py文件,针对多个py文件的打包,鲜有人提及;有也是部分全而多的解释,让人目不暇接,本次记录自己设置一个声波捕捉界面的打包过程。 1.pycharm中调用pyinstaller打包 参考链接:https://blog.csdn.net/weixin_45793544/articl…...
P1006 [NOIP 2008 提高组] 传纸条 题解
题目传送门 前言 每次准备摸鱼时都在这道题的界面。 今天有空做做,顺便写一波题解,毕竟估值蹭蹭往下跳。 双倍经验:P1004 [NOIP 2000 提高组] 方格取数,P1006 [NOIP 2008 提高组] 传纸条。 题意简述 现有一个 m m m 行 n …...
linux下编译Websocketpp,适用x86和armv8
编译boost库 下载源文件:Version 1.79.0 编译: sudo ./bootstrap.sh sudo ./b2 install 安装websocketpp git clone https://github.com/zaphoyd/websocketpp.git cd websocketpp #进入目录 mkdir build cd build cmake .. make sudo make ins…...
skynet.dispatch 使用详解
目录 skynet.dispatch 函数详解1. 函数定义与参数2. 消息处理流程3. 使用示例示例 1:处理 Lua 协议消息示例 2:处理自定义协议消息 4. 关键机制(1) 协程与阻塞操作(2) 消息响应 5. 与 skynet.register_protocol 的协作6. 注意事项7. 典型应用场景 总结 s…...
CondaError: Run ‘conda init‘ before ‘conda activate‘
CondaError: Run conda init before conda activate,表明 Conda 环境未正确初始化,导致无法激活目标环境。以下是具体解决方案: 1. 初始化 Conda Conda 需要先初始化才能使用 activate 命令。根据Linux系统,运行以下命令初始化 B…...
从代码学习深度学习 - 序列到序列学习数据预处理 PyTorch 版
文章目录 前言一、数据读取二、文本预处理三、词元化四、构建词表五、截断和填充六、转换为张量七、数据迭代器总结前言 在深度学习领域,序列到序列(Seq2Seq)模型是一种非常重要的架构,广泛应用于机器翻译、文本摘要和对话生成等任务。在实现 Seq2Seq 模型时,数据的预处理…...
SQL:Primary Key(主键)和Foreign Key(外键)
目录 1. Key(键) 2. Index(索引) 3.Key和Index的区别 4. Primary Key(主键) 5. Foreign Key(外键) 6.主键和外键的关系 温馨提示: 闪电按钮不同的执行功能 首先&…...
ClickHouse接入prometheus监控
ClickHouse接入prometheus监控 在 ClickHouse 集群环境下(假设你有 3 台服务器),使用自带的 Prometheus 端点来监控是完全可行的。集群部署意味着你需要为每台服务器配置 Prometheus 端点,并确保 Prometheus 能够从所有节点采集数…...
轻量级UDP流量重放工具的技术实现与场景应用(C/C++代码实现)
在网络协议测试、安全攻防演练、性能调优等领域,精确控制数据包传输行为是核心需求。udp_replay作为一款专注于UDP流量的开源工具,通过简洁的设计实现了对pcap文件中UDP数据流的灵活重放。本文将从技术实现原理、核心功能亮点及典型应用场景三个维度展开…...
时序数据库 TDengine × Excel:一份数据,两种效率
在日常工作中,很多人都离不开 Excel。不论是设备运维工程师、数据分析师,还是业务人员,一份熟悉的电子表格往往就是他们的“第一张报表”。 现在,TDengine 也可以与 Excel 实现无缝连接,用户可以直接在 Excel 中查询时…...
video自动播放
文章目录 前言在iOS系统中,H5页面的自动播放功能受到了一些限制,为了提升用户体验和保护用户隐私,Safari浏览器对于自动播放的行为做了一些限制。 一、自动播放的限制二、解决方案 前言 在iOS系统中,H5页面的自动播放功能受到了一…...
如何利用AI智能生成PPT,提升工作效率与创意表现
如何利用AI智能生成PPT,提升工作效率与创意表现!在这个信息爆炸的时代,制作一份既专业又富有创意的PPT,已经不再是一个简单的任务。尤其是对于每天都需要做报告、做展示的职场人士来说,PPT的质量直接影响着工作效率和个…...
Java8+Spring Boot + Vue + Langchain4j 实现阿里云百炼平台 AI 流式对话对接
1. 引言 在本文中,我们将介绍如何使用 Spring Boot、Vue.js 和 Langchain4j,实现与 阿里云百炼平台 的 AI 流式对话对接。通过结合这些技术,我们将创建一个能够实时互动的 AI 聊天应用。 这是一个基于 Spring Boot Vue.js Langchain4j 的智…...
【scikit-learn基础】--『数据加载』之外部数据集
这是scikit-learn数据加载系列的最后一篇,本篇介绍如何加载外部的数据集。 外部数据集不像之前介绍的几种类型的数据集那样,针对每种数据提供对应的接口,每个接口加载的数据都是固定的。 而外部数据集加载之后,数据的字段和类型是…...
Redis原理:keys命令
语法: keys pattern 返回所有符合pattern的key 支持 glob-style patterns: h?llo matches hello, hallo and hxlloh*llo matches hllo and heeeelloh[ae]llo matches hello and hallo, but not hilloh[^e]llo matches hallo, hbllo, ... but not helloh[a-b]llo ma…...
4.7学习总结 可变参数+集合工具类Collections+不可变集合
可变参数: 示例: public class test {public static void main(String[] args) {int sumgetSum(1,2,3,4,5,6,7,8,9,10);System.out.println(sum);}public static int getSum(int...arr){int sum0;for(int i:arr){sumi;}return sum;} } 细节:…...
高级java每日一道面试题-2025年3月24日-微服务篇[Nacos篇]-使用Nacos如何实现配置管理?
如果有遗漏,评论区告诉我进行补充 面试官: 使用Nacos如何实现配置管理? 我回答: 在Java高级面试中讨论如何使用Nacos实现配置管理的综合回答 在Java高级面试中,关于如何使用Nacos实现配置管理,可以从以下几个方面进行全面、深入的阐述&am…...
Exce格式化批处理工具详解:高效处理,让数据更干净!
Exce格式化批处理工具详解:高效处理,让数据更干净! 1. 概述 在数据分析、报表整理、数据库管理等工作中,数据清洗是不可或缺的一步。原始Excel数据常常存在格式不统一、空值、重复数据等问题,影响数据的准确性和可用…...
CExercise_06_1指针和数组_1查找数组的最大值和最小值
题目: 查找数组的最大值和最小值,但要将最大值作为返回值返回,最小值则依靠传入的指针完成赋值。 要求不能使用"[]"运算符。 函数的声明如下: int max_min(int *arr, int len, int *pmin); 关键点 1) * 运算符用于解引用…...
redis中的hash
Redis中的hash是什么 Hash: 哈希,也叫散列,是一种通过哈希函数将键映射到表中位置的数据结构,哈希函数是关键,它把键转换成索引。 Redis Hash(散列表)是一种 field-value pairs(键值对&#x…...
【学习笔记】李沐斯坦福21秋季:实用机器学习中文版
这里写自定义目录标题 数据处理数据获取数据标注数据清洗特征工程 数据处理 数据获取 爬虫 实际工作中大部分都是从数据库里取数 数据标注 只有一小部分有标签 大部分无标签的话 半监督学习:没标注数据和有标注数据共同使用 做法1:半监督学习 基于有标签的小部分…...
UE5学习笔记 FPS游戏制作43 UI材质
文章目录 实现目标制作UI材质使用UI材质 实现目标 把图片变为灰色 制作UI材质 右键新建一个材质 左侧细节栏,材质域改为用户界面,混合模式改为半透明 此时输出节点应该有两个属性 在内容浏览器里找到要用的图片,然后向上拖动到材质标题…...
QT控件 修改QtTreePropertyBrowser自定义属性编辑器源码,添加第一列标题勾选,按钮,右键菜单事件等功能
头阵子遇到一个需要修改QtTreePropertyBrowser控件的需求,QT开发做这么久了,这个控件倒是第一次用,费了点时间研究,在这里做个简单的总结。 QtTreePropertyBrowser控件 是 Qt 解决方案 (Qt Solutions) 中的一个组件,用…...
MFC工具栏CToolBar从专家到小白
CToolBar m_wndTool; //创建控件 m_wndTool.CreateEx(this, TBSTYLE_FLAT|TBSTYLE_NOPREFIX, WS_CHILD | WS_VISIBLE | CBRS_FLYBY | CBRS_TOP | CBRS_SIZE_DYNAMIC); //加载工具栏资源 m_wndTool.LoadToolBar(IDR_TOOL_LOAD) //在.rc中定义:IDR_TOOL_LOAD BITMAP …...
Golang 项目平滑重启
引言 平滑重启(Graceful Restart)技术作为一种常用的解决方案,通过允许新进程接管而不中断现有的请求,确保了系统的稳定运行和业务连续性。同时目前公司的服务重启绝大部分也都适用的 go 的平滑重启技术。 本部分将对平滑重启的…...