力扣第 55 题 跳跃游戏

devtools/2024/11/19 2:17:44/

力扣第 55 题 跳跃游戏(Jump Game)。题目要求判断一个非负整数数组中,是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。

解题思路

我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前能够到达的最远位置,并判断是否可以覆盖到数组的最后一个位置。

  1. 初始化变量 maxReach 为 0,表示当前能够跳到的最远位置。
  2. 遍历数组的每个位置 i,判断:
    • 如果当前下标 i 大于 maxReach,说明无法从前面的跳跃到达位置 i,返回 false
    • 更新 maxReachmax(maxReach, i + nums[i]),表示当前能够跳到的最远位置。
  3. 如果遍历结束后,maxReach 大于等于数组的最后一个下标,则返回 true

C语言实现

#include <stdio.h>
#include <stdbool.h>// 跳跃游戏判断函数
bool canJump(int* nums, int numsSize) {int maxReach = 0;  // 能到达的最远位置for (int i = 0; i < numsSize; i++) {// 如果当前位置超过能到达的最远位置,说明无法继续跳跃if (i > maxReach) {return false;}// 更新能到达的最远位置if (i + nums[i] > maxReach) {maxReach = i + nums[i];}// 如果最远位置已经可以覆盖最后一个位置,则直接返回 trueif (maxReach >= numsSize - 1) {return true;}}return false;
}int main() {int nums[] = {2, 3, 1, 1, 4};int numsSize = sizeof(nums) / sizeof(nums[0]);if (canJump(nums, numsSize)) {printf("可以跳到最后一个位置!\n");} else {printf("无法跳到最后一个位置!\n");}return 0;
}

示例解析

示例 1:

输入:

int nums[] = {2, 3, 1, 1, 4};

输出:

可以跳到最后一个位置!

解释:

  • 从第一个位置跳跃 2 步到索引 1,接着跳跃 3 步到最后一个位置。
示例 2:

输入:

int nums[] = {3, 2, 1, 0, 4};

输出:

无法跳到最后一个位置!

解释:

  • 无论怎么跳跃,都无法跳过索引 3 的位置,因为索引 3 的值为 0。

复杂度分析

  1. 时间复杂度 O ( n ) O(n) O(n)
    • 遍历数组中的每个元素一次,线性时间复杂度。
  2. 空间复杂度 O ( 1 ) O(1) O(1)
    • 只使用了一个变量 maxReach,空间复杂度为常数。

贪心算法的核心

贪心的本质是:

  • 只关心是否能到达尽可能远的位置,而不需要模拟实际的跳跃过程。
  • 一旦 maxReach 无法覆盖某个位置,直接返回 false;如果能够覆盖到最后一个位置,返回 true

http://www.ppmy.cn/devtools/135089.html

相关文章

使用 Go 实现将任何网页转化为 PDF

在许多应用场景中&#xff0c;可能需要将网页内容转化为 PDF 格式&#xff0c;比如保存网页内容、生成报告、或者创建网站截图。使用 Go 编程语言&#xff0c;结合一些现有的库&#xff0c;可以非常方便地实现这一功能。本文将带你一步一步地介绍如何使用 Go 语言将任何网页转换…

⚙️ 如何调整重试策略以适应不同的业务需求?

调整 Kafka 生产者和消费者的重试策略以适应不同的业务需求&#xff0c;需要根据业务的特性和容错要求来进行细致的配置。以下是一些关键的调整策略&#xff1a; 业务重要性&#xff1a; 对于关键业务消息&#xff0c;可以增加重试次数&#xff0c;并设置较长的重试间隔&#x…

【C++】哈希表的实现详解

哈希表的实现详解 一、哈希常识1.1、哈希概念1.2、哈希冲突1.3、哈希函数&#xff08;直接定执 除留余数&#xff09;1.4、哈希冲突解决闭散列&#xff08;线性探测 二次探测&#xff09;开散列 二、闭散列哈希表的模拟实现2.1、框架2.2、哈希节点状态的类2.3、哈希表的扩容2…

音频采样数据格式

音频信号在模拟到数字转换时&#xff0c;会涉及到多个关键参数&#xff0c;如采样率、位深度、通道数等。下面是常见的音频采样数据格式及其相关概念&#xff1a; 1. 采样率 (Sample Rate) 采样率指的是每秒钟对音频信号进行采样的次数&#xff0c;单位为赫兹 (Hz)。常见的值…

HuggingFace:基于YOLOv8的人脸检测模型

个人操作经验总结 1、YOLO的环境配置 github 不论base环境版本如何&#xff0c;建议在conda的虚拟环境中安装 1.1、创建虚拟环境 conda create -n yolov8-face python3.9conda create &#xff1a;创建conda虚拟环境&#xff0c; -n &#xff1a;给虚拟环境命名的…

Android 10 默认授权安装app运行时权限(去掉运行时所有权限授权弹窗)

GRANT_INSTALL就是在安装apk时已经给予了所有申请权限&#xff0c;所以运行时给与权限改为安装时给予权限就可以了。 解决方案如下&#xff1a; 在PermissionManagerService.java文件中restorePermissionState方法中将应用权限设置为安装权限 /frameworks/base/services/core/…

SQL Server中,CONVERT函数转换日期

在SQL Server中&#xff0c;CONVERT函数支持多种样式代码&#xff08;style codes&#xff09;&#xff0c;用于指定日期和时间的格式。样式代码 23 是一种常用的格式&#xff0c;表示 yyyy-mm-dd。以下是一些常用的样式代码&#xff1a; 日期格式样式代码 0 or 100 - mon dd…

从“大吼”到“轻触”,防爆手机如何改变危险油气环境通信?

众所周知&#xff0c;在加油站用手机打电话是被明令禁止的&#xff0c;这是因为手机内部会产生静电或射频火花&#xff0c;可能点燃空气中的油气混合物&#xff0c;导致爆炸或火灾。那么加油站的工作人员如何交流呢&#xff1f;以前他们靠吼&#xff0c;现在有了防爆手机&#…