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

leetcode 面试经典 150 题：跳跃游戏 II

news 来源：原创 2025/5/15 9:08:29

链接	跳跃游戏 II
题序号	45
题型	数组
题解	贪心算法
难度	中等
熟练度	✅✅✅

题目

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

提示:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

题解

解题思路：可以用贪心算法来完成此题，每次尽可能跳得更远，以确保跳跃次数最少。通过维护当前能够到达的最远位置 max_far 和当前跳跃的边界 end，来确定是否需要增加跳跃次数。贪心算法的关键点：
- 维护当前能跳到的最远位置：max_far，表示从当前位置能跳到的最远位置。
- 维护当前跳跃范围的右边界：end，表示当前跳跃范围的右边界，也是下一次跳跃的起始点。
- 维护跳跃次数：step，表示已经完成的跳跃次数。
复杂度：时间复杂度O(n)，其中 n 是数组的长度。因为代码中只包含一个循环，且每次循环的操作都是常数时间。空间复杂度O(1)，只使用了常数级别的额外空间。
c++ 实现算法：

class Solution2 {
public:int jump(vector<int>& nums) {int max_far = 0; // 当前能够跳到的最远位置int step = 0;    // 跳跃次数int end = 0;    // 上一次跳跃能够到达的右边界（下一次跳跃的起跳点）for (int i = 0; i < nums.size() - 1; i++){// 更新当前能够跳到的最远位置max_far = std::max(max_far, i + nums[i]);// 如果当前位置到达了上一次跳跃的右边界if (i == end){end = max_far;  // 更新下一次跳跃的右边界step++;         // 增加跳跃次数}}return step;}
};

算法推演：

假设输入数组为 nums = {2, 3, 1, 1, 4}，代码的执行过程如下：
初始状态：max_far = 0，step = 0，end = 0。
第一次循环（i = 0）： max_far = max(0, 0 + 2) = 2。 i == end，更新 end = 2，step++ → step = 1。
第二次循环（i = 1）： max_far = max(2, 1 + 3) = 4。 i != end，不更新 end 和 step。
第三次循环（i = 2）： max_far = max(4, 2 + 1) = 4。 i == end，更新 end = 4，step++ → step = 2。
第四次循环（i = 3）： max_far = max(4, 3 + 1) = 4。 i != end，不更新 end 和 step。
第五次循环（i = 4）：循环结束。最终返回 step = 2，表示最少需要 2 次跳跃才能到达数组的最后一个位置。

c++ 完整demo：

#include <iostream>
#include <vector>
using namespace std;
class Solution2 {
public:int jump(vector<int>& nums) {int max_far = 0; // 当前能够跳到的最远位置int step = 0;    // 跳跃次数int end = 0;    // 上一次跳跃能够到达的右边界（下一次跳跃的起跳点）for (int i = 0; i < nums.size() - 1; i++){// 更新当前能够跳到的最远位置max_far = std::max(max_far, i + nums[i]);// 如果当前位置到达了上一次跳跃的右边界if (i == end){end = max_far;  // 更新下一次跳跃的右边界step++;         // 增加跳跃次数}}return step;}
};
int main() {vector <int>  nums2 = {2, 3, 1, 1, 4};Solution2 solution2;int jump = solution2.jump(nums2);cout << "jump: " << jump << endl;return 0;
}

leetcode 面试经典 150 题：跳跃游戏 II

链接跳跃游戏 II题序号45题型数组题解贪心算法难度中等熟练度✅✅✅ 题目给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums…...

编程日记 2025/5/15 9:08:29

C++20 新特性解析

1. 概念（Concepts）概念是 C++20 引入的一项重要特性，它允许程序员定义类型约束，从而在编译时检查模板参数是否符合某些要求。概念提供了模板参数的限制，使得模板代码更加可读和易于维护。示例代码： #include <iostream> #include <concepts>// 定义一个…...

编程日记 2025/5/12 8:03:41

vue不是内部或外部命令？

问题：当我们在使用脚手架创建项目之前，执行了npm i vue/cli -g或yarn global add vue/cli之后，再执行vue --version无法执行，vue不是内部或外部命令。前几天在学vue时也是遇到了这个问题，现在来分享一下解决方法。 …...

编程日记 2025/5/15 7:47:46

C#中的Frm_Welcome.Instance.Show()，是什么意思

Frm_Welcome.Instance.Show() 是一种常见的单例模式（Singleton Pattern）实现方式，通常用于在应用程序中确保某个窗体（Form）只有一个实例，并通过该实例显示窗体。以下是对这段代码的详细解释： 代…...

编程日记 2025/5/15 8:27:32

k8s优雅操作pod容器组回退备份 kubectl get deploy deployName -o yaml>>deployName-bak-date "%Y-%m-%d".yaml获取副本数 replicasecho | kubectl get -o template deploy/deployName --template{{.spec.replicas}}停止容器组 kubectl scale deployment …...

编程日记 2025/5/15 7:52:07

【LeetCode: 1760. 袋子里最少数目的球 + 二分】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…...

编程日记 2025/5/15 7:13:42

动态规划LeetCode-416.分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1： 输入：nums [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2&…...

编程日记 2025/5/15 9:00:42

kotlin-kapt

kotlin-kapt kotlin-kapt 是 Kotlin 的一个插件，专门用于处理注解处理器（Annotation Processor）。以下是对该插件的详细解释和指南： kotlin-kapt 是什么？ kotlin-kapt 是 Kotlin 官方提供的一个插件，用于在…...

编程日记 2025/5/15 8:46:38

网络安全技术复习总结

1|0第一章概论 1.网络安全发展阶段包括四个阶段：通信安全、计算机安全、网络安全、网络空间安全。 2.2017年6月1日，我国第一部全面规范网络空间安全的基础性法律《中华人民共和国网络安全法》正式实施。 3.2021年 6月10日，《中华人民共和…...

编程日记 2025/5/15 8:15:02

java 集合

Java集合框架（Java Collections Framework）是一个强大的工具库，旨在简化数据存储和操作的任务。它提供了一组接口、类和算法，帮助开发者高效地管理数据，如列表、集合和映射。下面是Java集合框架的详细介绍：…...

编程日记 2025/5/15 7:58:49

Java常见排序算法及代码实现

1、选择排序算法选择排序（Selection Sort）是一种简单直观的排序算法，它的工作原理是每次从未排序部分选择最小（或最大）的元素，将其放到已排序部分的末尾。 2、冒泡排序算法冒泡排序（Bubble…...

编程日记 2025/5/15 8:52:10

130,[1] 攻防世界 very_easy_sql

进入靶场典型SQL注入页面先查看源码访问试试http://127.0.0.1/ 还尝试了其他都是nonono 回归第一个登录页面提交的内容不在url处显示，反而第二个url页面会在url处显示明白第一个页面是通过post方式提交，反正没得到什么信息，去抓…...

编程日记 2025/5/14 21:54:41

Spring Boot从入门到精通：核心知识点+实战指南

目录一、Spring Boot 是什么？为什么它如此流行？ 二、快速创建你的第一个Spring Boot应用 2.1 使用Spring Initializr生成项目 2.2 核心代码示例三、深度解析Spring Boot核心机制 3.1 自动配置原理揭秘 3.2 自定义Starter实战四、生产环境必备…...

编程日记 2025/5/15 7:51:01

深入探索现代CSS：从基础到未来趋势

引言：CSS的进化之路 CSS（层叠样式表）自1996年诞生以来，已从简单的样式描述语言发展为构建现代Web体验的核心技术。截至2023年，超过98%的网站使用CSS3技术，其发展历程见证了Web从静态文档到富交互应用的蜕变…...

编程日记 2025/5/15 7:20:58

python-leetcode 23.反转链表

题目： 给单链表的头节点，反转链表，并返回反转后的链表。方法一：迭代在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此要先存储前一个节点，在更改引…...

编程日记 2025/5/15 7:20:58

Foundation CSS 可见性

Foundation CSS 可见性引言在网页设计中，CSS可见性是一个至关重要的概念。它决定了元素在网页上是否可见，以及如何显示。Foundation CSS 是一个流行的前端框架，它提供了丰富的工具和组件来帮助开发者构建响应式和可访问的网页。本文将深入探讨 Foundation CSS 中的可见性…...

编程日记 2025/5/15 8:12:25

DeepSeek模拟阿里面试——java基本语法

为了全面准备阿里Java高级程序员的面试，以下是针对数据类型和变量、运算符、流程控制的系统性复习和准备策略： 数据类型和变量基本数据类型整数类型：byte（1字节）、short（2字节）、int&#xf…...

编程日记 2025/5/15 7:44:22

大模型基本原理（二）——ChatGPT的工作原理

如何得到一个ChatGPT？ 1、无监督预训练：通过大量的文本数据集进行无监督训练，得到一个基座模型（只会续写文本） 2、监督微调：通过一些人类撰写的高质量对话数据对基座模型进行监督微调，得到一个…...

编程日记 2025/5/14 3:30:13

TensorRT 8.6.1教程1-TensorRT简介

区分计算节点和数据节点视频 TensorRT 教程 | 基于 8.6.1 版本 | 第一部分_哔哩哔哩_bilibili cookbook...

编程日记 2025/5/12 15:14:00

Seaweedfs（master volume filer） docker run参数帮助文档

文章目录进入容器后执行获取weed -h英文中文 weed server -h英文中文 weed volume -h英文中文关键点测试了一下，这个-volume.minFreeSpace string有点狠，比如设置值为10（10%），它直接给系统只留下10%的空间&#xff0…...

编程日记 2025/5/8 20:07:23

深度求索（DeepSeek）的AI革命：NLP、CV与智能应用的技术跃迁

Deepseek官网：DeepSeek 引言：AI技术浪潮中的深度求索近年来，人工智能技术以指数级速度重塑全球产业格局。在这场技术革命中，深度求索（DeepSeek）凭借其前沿的算法研究、高效的工程化能力以及对垂直场景的…...

编程日记 2025/5/15 7:12:08

探索RDMA技术：从基础到实践

1. 引言在当今的高性能计算（HPC）和数据中心领域，数据传输的效率和速度至关重要。RDMA（Remote Direct Memory Access，远程直接内存访问）技术作为一种高效的网络通信机制，能够显著减少数据传输的延迟和CPU负载。本文将从基础到实践，详细介绍RDMA技术及其编程模型，帮助…...

编程日记 2025/5/14 10:55:44

Excel 笔记

实际问题记录 VBA脚本实现特殊的行转列已知：位于同一Excel工作簿文件中的两个工作表：Sheet1、Sheet2。问题：现要将Sheet2中的每一行，按Sheet1中的样子进行转置： Sheet2中每一行的黄色单元格，为列头。…...

编程日记 2025/5/13 17:14:24

Flutter编译运行android问题之JVM版本问题

错误1： FAILURE: Build failed with an exception. * What went wrong: Execution failed for task :audioplayers_android:compileDebugKotlin. > Inconsistent JVM-target compatibility detected for tasks compileDebugJavaWithJavac (1.8) and compileDebug…...

编程日记 2025/5/14 22:40:45

自动化遇到的问题记录（遇到问题就更）

总结回归下自己这边遇到的一些问题 “EOF错误”，获取不到csv里面的内容跑多csv文件里的场景，部分场景的请求值为 1、检查csv文件里不能直接是[]开头的参数，把[]改到ms平台的请求参数里 2、有时可能是某个参数值缺了双引号的其中一边 met…...

编程日记 2025/5/14 4:40:34

解决 Flutter Device Daemon 启动失败问题的实践记录

解决 Flutter Device Daemon 启动失败问题的实践记录最近在使用 Flutter 开发时踩了一个坑。看似是个小问题，但折腾了好久，最终通过日志分析和查阅资料才找到了解决办法。这里记录一下整个问题的排查过程，希望能帮助到遇到类似问题的小伙伴…...

编程日记 2025/5/11 14:03:40

中国通信企业协会通信网络安全服务能力评定证书使用说明

中国通信企业协会颁发的通信网络安全服务能力资格证书，是证明证书持有单位符合通信网络安全服务相应能力准则要求。证书持有单位在使用中国通信企业协会颁发的证书时，应遵守以下规定： 评定证书证书持有单位必须遵守《中国通信企业协会通信网…...

编程日记 2025/5/11 22:22:14

《我在技术交流群算命》(三)：QML的Button为什么有个蓝框去不掉啊（QtQuick.Controls由Qt5升级到Qt6的异常）

有群友抛出类似以下代码和运行效果截图： import QtQuick import QtQuick.ControlsWindow {width: 640height: 480visible: truetitle: qsTr("Hello World")Button{anchors.centerIn: parentwidth: 100height: 40background: Rectangle {color: "red…...

编程日记 2025/5/13 5:08:54

多项式插值（数值计算方法）Matlab实现

多项式插值（数值计算方法）Matlab实现一. 原理介绍二. 程序设计1. 构建矩阵2. 求解矩阵方程3. 作出多项式函数4. 绘制插值曲线5. 完整代码三. 图例一. 原理介绍关于插值的定义及基本原理可以参照如下索引插值原理（数值计算方法&#xff…...

编程日记 2025/5/13 0:01:46

【AIGC】语言模型的发展历程：从统计方法到大规模预训练模型的演化

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: AIGC | ChatGPT 文章目录 💯前言💯语言模型的发展历程：从统计方法到大规模预训练模型的演化1 统计语言模型（Statistical Language Model, SLM）：统…...

编程日记 2025/5/7 11:11:47

[python]如何安装whl包并解决依赖关系（详细）

一、什么是whl文件？ whl是一种预编译的二进制包文件，它主要用于安装python库。简单来讲whl就是一种已经编译好的python库文件。我们可以使用whl包来安装python库。二、我们为什么需要使用whl文件来安装python库？ 有的小伙伴可能会疑惑&…...

编程日记 2025/5/9 14:29:55

Windows中使用Docker安装Anythingllm，基于deepseek构建自己的本地知识库问答大模型，可局域网内多用户访问、离线运行

文章目录 Windows中使用Docker安装Anythingllm，基于deepseek构建自己的知识库问答大模型1. 安装 Docker Desktop2. 使用Docker拉取Anythingllm镜像2. 设置 STORAGE_LOCATION 路径3. 创建存储目录和 .env 文件.env 文件的作用关键配置项 4. 运行 Docker 命令docker r…...

编程日记 2025/5/6 7:18:00

用Kibana实现Elasticsearch索引的增删改查：实战指南

在大数据时代，Elasticsearch（简称 ES）和 Kibana 作为强大的数据搜索与可视化工具，受到了众多开发者的青睐。Kibana 提供了一个直观的界面，可以方便地对 Elasticsearch 中的数据进行操作。本文将详细介绍如何使用 Kiban…...

编程日记 2025/5/14 15:54:29

AI前端开发的国际化发展机遇：ScriptEcho助力全球化布局

在全球化的今天，互联网应用已不再局限于单一市场。高效便捷的前端开发方案成为企业拓展国际市场的关键。得益于人工智能技术的飞速发展，AI代码生成器正在深刻改变前端开发模式，为国际化应用开发带来前所未有的机遇。然而，国际化开…...

编程日记 2025/5/14 7:22:36

本地基于GGUF部署的DeepSeek实现轻量级调优之一：提示工程（Prompt Engineering）（完整详细教程）

前文，我们在本地windows电脑基于GGUF文件，部署了DeepSeek-1.5B模型，如果想自行对模型进行训练，离线模式下加载本地的DeepSeek模型进行训练时，是不能直接使用GGUF文件进行训练。请参照我的文章在本地部署好模型之后再继…...

编程日记 2025/5/12 4:05:52

基于 GEE 计算研究区年均地表温度数据

目录 1 代码解析 2 完整代码 3 运行结果 1 代码解析 （1）定义研究区： // 研究区的范围需要自己提前上传 var dataset table;// 将研究区显示在中心，后面的数字为缩放等级，范围从1 - 24 Map.centerObject(dataset,…...

编程日记 2025/5/10 0:18:40

编程语言的深度剖析：从语法到性能优化

引言随着软件开发的不断进化，编程语言的选择对项目的成功与否具有关键影响。今天的开发者面临着丰富多样的编程语言选择：每一种语言都有独特的优势、特性和适用场景。然而，语言的设计理念、运行机制和优化技巧背后的技术细节却常常被忽视。本…...

编程日记 2025/5/14 8:48:23

设计模式-结构型-外观模式

在软件开发中，随着功能的不断迭代，系统会变得越来越复杂，模块之间的依赖关系也会越来越深。这种复杂性会导致代码难以理解、维护和扩展。而外观模式（Facade Pattern）正是为了解决这一问题而生的。一、外观模式简介 …...

编程日记 2025/5/14 13:54:21

uniapp中对于文件和文件夹的处理，内存的查询

目录移动文件到指定文件夹新增本地文件夹设定本地文件过期时间，清除超时文件，释放内存操作本地文件之----删除 uniapp获取设备剩余存储空间的方法读取本地文件夹下的文件移动文件到指定文件夹 function moveTempFile(tempFilePath, targetFo…...

编程日记 2025/5/14 21:40:21

计算机网络和操作系统常见面试题目（带脑图，做了延伸以防面试官深入提问）

呜哦~~(✪▽✪)曼波~~~~ 今天我们来聊聊计算机网络和操作系统的面试题目吧！这些题目是面试中经常遇到的，曼波觉得掌握它们对面试非常有帮助哦！(๑✧◡✧๑) --- 1. 计算机网络面试题目 1.1 OSI 七层模型是什么？ 回答&#xff…...

编程日记 2025/5/15 6:45:35

C++ Primer 条件语句

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/6 6:44:56

JAVA安全—Shiro反序列化DNS利用链CC利用链AES动态调试

前言讲了FastJson反序列化的原理和利用链，今天讲一下Shiro的反序列化利用，这个也是目前比较热门的。原生态反序列化我们先来复习一下原生态的反序列化，之前也是讲过的，打开我们写过的serialization_demo。代码也很简单&…...

编程日记 2025/5/8 17:03:20

16.React学习笔记.React更新机制

一. 发生更新的时机以及顺序## image.png props/state改变render函数重新执行产生新的VDOM树新旧DOM树进行diff计算出差异进行更新更新到真实的DOM 二. React更新流程## React将最好的O(n^3)的tree比较算法优化为O(n)。同层节点之间相互比较，不跨节点。不同类型的节…...

编程日记 2025/5/10 9:03:29

React使用 useImperativeHandle 自定义暴露给父组件的实例方法（包括依赖）

关键词 React useImperativeHandle 摘要 useImperativeHandle 是 React 提供的一个自定义 Hook，用于在函数组件中显式地暴露给父组件特定实例的方法。本文将介绍 useImperativeHandle 的基本用法、常见应用场景，以及如何处理其依赖项，以帮…...

编程日记 2025/5/12 0:47:51

Vue 过渡动画实现全解析：打造丝滑交互体验

Vue 过渡动画实现全解析：打造丝滑交互体验在当今竞争激烈的 Web 开发领域，用户体验已成为衡量项目成功与否的关键指标。过渡动画作为提升用户体验的利器，能让应用的交互更加丝滑流畅，给用户带来愉悦的使用感受。在 Vue.js 框架中…...

编程日记 2025/5/14 6:05:41

从 0 开始本地部署 DeepSeek：详细步骤 + 避坑指南 + 构建可视化（安装在D盘）

个人主页：chian-ocean 前言： 随着人工智能技术的迅速发展，大语言模型在各个行业中得到了广泛应用。DeepSeek 作为一个新兴的 AI 公司，凭借其高效的 AI 模型和开源的优势，吸引了越来越多的开发者和企业关注。为了更好地…...

编程日记 2025/5/13 17:31:52

Render上后端部署Springboot + 前端Vue 问题及解决方案汇总

有一个 Vue 前端和 Spring Boot 后端的动态网页游戏，当前在本地的 5173 端口和运行。你希望生成一个公开链接，让所有点击链接的人都能访问并玩这个游戏。由于游戏原本需要在本地执行 npm install 后才能启动，你现在想知道在部署时是选择 Ren…...

编程日记 2025/5/8 11:30:07

Linux——信号的保存与处理

前言：本文主要介绍信号的保存与处理过程。一、信号阻塞与信号底层逻辑在linux下面的进程控制块(PCB),存在一个pending变量用于存放接收到的信号，该变量有32位，变量的位代表信号的类别，变量的值代表是否收到信号。进程会根据该变…...

编程日记 2025/5/9 6:14:06

【deepseek-r1本地部署】

首先需要安装ollama,之前已经安装过了，这里不展示细节在cmd中输入官网安装命令：ollama run deepseek-r1:32b，开始下载出现success后，下载完成接下来就可以使用了，不过是用cmd来运行使用可以安装UI可视化界面&a…...

编程日记 2025/5/11 22:58:58

Docker Desktop Windows 安装

一、先下载Docker desktop WIndows 下载地址二、安装安装超简单一路下一步三、安装之后，桌面会出现一个小蓝鲸图标，打开它》更新至最新版本，不然小蓝鲸打开，一会就退出了。》wsl --update （这个有时比较慢…...

编程日记 2025/5/9 13:11:28

题目

题解

相关文章：