首页 > 试题广场 >

跳跃游戏(一)

[编程题]跳跃游戏(一)
  • 热度指数：6043 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则输出true，否则输出false。
数据范围:


输入描述:
第一行输入一个正整数 n ，表示数组 nums 的长度
第二行输入 n 个整数表示数组的每个元素


输出描述:
输出 true 或者 false
示例1

输入

7
2 1 3 3 0 0 100

输出

true

说明

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，再跳到nums[3]=3的位置，再直接跳到nums[6]=100，可以跳到最后，输出true  
示例2

输入

7
2 1 3 2 0 0 100

输出

false

说明

无论怎么样，都跳不到nums[6]=100的位置  
算法知识视频讲解
开通博客
头像 fred-coder
发表于 2022-02-22 10:58:51
如果给定的数据长度较小，可以采用动态规划，设置 dp, dp[i] 表示 是否可以调到该位置; 状态转移方程为 dp[i] = dp[j] and data[j] + j >= i j < i,由于数据的长度较大，双重循环遍历会超时,采用贪心策略，从后向前遍历数组，看当前位置 + 值 是 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 DizhX
发表于 2022-02-19 16:13:11
// 方法一：保存布尔型dp数组表示该格子能否到达 import java.util.Scanner;   public class Main{           pu 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 晚风做酒
发表于 2022-03-09 15:47:30
参考LK上大佬的代码； int main() { int n,i , k = 0;  //  k表示最远能到达的距离；     cin>>n; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 赫he
发表于 2023-07-13 20:08:57
记录最远可以到达的地方，在遍历每个nums时，更新最远的距离 #include <iostream> using namespace std; const int N = 2e5+10; int a[N]; int n; int main() { scanf("%d&q 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 乐弦之佩
发表于 2022-11-24 19:37:27
import java.util.*; public class Main { public static void main(String[] args) { // 标准输入 Scanner input = new Scanner(System.in); 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客238088962号
发表于 2022-10-30 10:28:00
该题用动态规划法求解的核心思想是由终点向起点回推（如果由起点向终点的话，笔者才疏学浅，只想到了穷举一种方法），条件为j-k<=a[k]，即由k点到j点的距离小于a[k]跳动的最大距离，j点为靠后的那一个点。由于数组中任意一点a[k]的值为k点能跳动的最大值，故只要从想要到达的那个点由后向前寻找 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 编程小鹏
发表于 2024-03-03 20:56:35
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 韭菜牛客
发表于 2022-03-28 14:44:53
描述 给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则输出true，否则输出false。 数据范围: 1<=nums.length<=2×1051<=nums.length<= 2\t 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ivy2019
发表于 2022-08-28 21:46:37
注意理解题意“数组里面的每个元素代表下一跳能够跳跃的最大长度”，这就意味着多多益善，不管走到第几步，只要能等于或者超过n-1的值就应该返回true。 反之，不管在第几步，只要当前是目前为止的最长跳跃距离、且该处值为0、且该处不是出口n-1，那么久可以认为，永远也跳不到出口去了。此时应该返回fa 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 静寂旮旯
发表于 2022-04-28 22:23:13
解题思路： 普通的dp会超时，在输入过程中直接执行dp，令mx_idx表示当前i下所能到达的最远下标，每次输入取所能到达下标的最大值，假如能到达下标n-1则返回true，但如果在此过程中出现下标i的v为0，而该下标恰好是mx_idx所能达到的最远下标，则不能再继续往下走，可以中断，并返回false 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
13条回答 1509浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号