首页 > 试题广场 >

跳跃游戏(一)

[编程题]跳跃游戏(一)
  • 热度指数：6042 时间限制：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的位置  
算法知识视频讲解
添加回答
Java
牛客208400313号头像 牛客208400313号 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        int maxLoc = nums[0];
        // 遍历同时判断该位置是否可到达
        for (int i = 1; i < n && i <= maxLoc; i++) {
            // 每个位置计算自己能到达的最远位置
            maxLoc = Math.max(maxLoc, nums[i] + i);
        }

        // 能到达的最远位置与数组最后一个下标比较
        System.out.println(maxLoc >= n - 1);
    }

}
发表于 2022-10-04 18:13:34 回复(0)
C++
多事头像 多事
#include <iostream>
#include<vector>
using namespace std;
//选择每次跳的最远的下标
int findp(const int *a,int n){
    int temp=0;
    int ans;
    for(int i=1;i<n;i++){
        if(temp<a[i]+i){
            temp=a[i]+i;
            ans=i;
        }
           
    }
    return ans;
}
int main() {
   int n,temp;
   vector<int> nums;
   cin>>n;
   for(int i=1;i<=n;i++){
        cin>>temp;
        nums.push_back(temp);
   }
   int key;
   for(int i=0;i<n;i+=key){
        if(nums[i]-n+1+i>=0){
            cout<<"true";
            return 0;
        }
        if(nums[i]==0){
            cout<<"false";
            return 0;
        }
        key=findp(&nums[i],nums[i]+1);
   }

}
// 64 位输出请用 printf("%lld")
编辑于 2024-03-06 10:14:17 回复(0)
牛客212561046号头像 牛客212561046号 
#include <iostream>
using namespace std;

int main() {

    int n;
    cin>>n;
    int right = 0, flag=0;
    for(int i=0; i<n; i++){
        if(i>right) break;
        if(right>n-2){
            flag = 1;
            break;
        }
        int x;
        cin>>x;
        right = max(right, i+x);
    }
    cout<< (flag==1 ? "true" : "false");
    return 0;
}

发表于 2023-12-30 18:00:01 回复(0)
昊天明月头像 昊天明月
python 本身的True，就和答案true不一样，真的无语啊。
发表于 2023-07-06 10:19:51 回复(0)
C++
牛客148703446号头像 牛客148703446号
优化空间后的动态规划方法 
f(i)表示起跳点在[0,i]范围内能跳到的最远地方的坐标
       if f(i) < i 说明不能跳到坐标为i的地方
       if f(i) >= n - 1说明可以跳到最后
注意n=1的特判 
#include <iostream>
#include <vector>
using namespace std;
bool dp26()
{
    // freopen("1.txt", "r", stdin);
    int n, tmp, a0, a1;
    cin >> n;
    if (n == 1) {
        cout << "true";
        return true;
    }
    cin >> tmp;
    a0  =  tmp;
    for (int i = 1; i < n; i++) {  
        cin >> tmp;
        if (a0 < i) {
            cout << "false";
            return false;
        } else if (a0 >= n - 1){
            cout << "true";
            return true;
        }else {
            a1 = max(i + tmp, a0);
            a0 = a1;
        }
    }
    return false;
}

int main()
{
    dp26();
    return 0;
}


发表于 2023-03-15 22:48:28 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    var max,x int
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        if i>max{
            fmt.Print(false)
            return
        }
        if i+x>max{
            max=i+x
        }
    }
    fmt.Print(true)
}

发表于 2023-02-24 21:03:37 回复(0)
愉快的大白菜不讲武德头像 愉快的大白菜不讲武德 
 Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        int[] dp = new int[n];
        dp[0] = in.nextInt();
        for (int i = 1; i < n; i++) {
            int num = in.nextInt();
            if (dp[i - 1] < i) {
                dp[n - 1] = 0; //达不到 , 直接结束.
                break;
            }
            dp[i] = Math.max(dp[i - 1], i + num);
        }
        System.out.println(dp[n - 1] >= n - 1);


发表于 2022-11-18 22:50:47 回复(0)
牛客419656984号头像 牛客419656984号 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=in.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++) arr[i]=in.nextInt();
        int res=0;
        for(int i=0;i<n;i++){
            if(i<=res){
               res=Math.max(res,i+arr[i]);
               if(res>=n-1){
                   System.out.println(true); System.exit(0);
               } 
            }
        }
        System.out.println(false);
    }
}

发表于 2022-10-13 22:29:26 回复(0)
Python3
在加班的奇亚籽很刻苦头像 在加班的奇亚籽很刻苦 
n = int(input())
nums = [int(x) for x in input().split()]
if n ==1:
    print('true')
else:
    dp = [False]*n
    target = n-1
    for i in range(n-2,-1,-1):
        if target-i <= nums[i]:
            target = i
            dp[i] = True
            continue
    print(str(dp[0]).lower())

发表于 2022-10-08 10:04:06 回复(0)
牛娃牛娃头像 牛娃牛娃 
#include<bits/stdc++.h>
using namespace std;

string JumpGame(int n,vector<int>&nums){
    int cover =0;
     for(int i=0;i<=cover;i++){
         cover =max(i+nums[i],cover);
         if(cover>=n-1)return "true";
     }
     return "false";
}

int main(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    cout<<JumpGame(n,nums);
    return 0;
}

发表于 2022-05-15 21:52:22 回复(0)
C++
元气少女李逵头像 元气少女李逵 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    int b;
    for(int i=0;i<n;i++)
    {
        cin>>b;
        a.push_back(b);
    }
    if(a[0]==0 && a.size()!=1)
    {
        cout<<"false"<<endl;
        return 0;
    }
    //每步判断，跳跃距离递减
    vector<int> dp(n+1,0);
    dp[1]=1;
    int temp=0;
    for(int i=2;i<=n+1;i++)
    {
        temp=max(temp,a[i-2]);
        if(dp[i-1]==1)
        {
            dp[i]=temp>=1? 1:0;
            temp=temp-1;
        }
        else
        {
            cout<<"false"<<endl;
            return 0;
        }
    }
    cout<<"true"<<endl;
    return 0;
}

发表于 2022-04-12 20:00:42 回复(0)
C++
等一个offer！头像 等一个offer！ 
#include<bits/stdc++.h>
using namespace std;

string canJump(vector<int>&nums,int n){
    int farthest=0;
    for(int i=0;i<n;i++){
        if(i<=farthest){
            farthest=max(farthest,i+nums[i]);
            if(farthest>=n-1){
                return "true";
            }
        }
    }
    return "false";
}

int main(){
    int n;cin>>n;
    vector<int>nums(n);
    for(int i=0;i<n;i++) cin>>nums[i];
    cout<<canJump(nums,n);
}

发表于 2022-04-06 19:40:19 回复(0)
Java
wwwzzz头像 wwwzzz
四种方式，dp2最快，dfs慢点。bfs超内存，dp1和dp3超时。 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i< n;i++) {
                arr[i] = in.nextInt();
            }
            boolean b = dfs(arr);
            System.out.println(b);
        }
    }
    
    // dp 记录能到达的最大的index
    // 时间复杂度为n
    public static boolean dp2(int[] arr) {
        int n = arr.length;
        int dp = arr[0];
        for (int i = 1; i < n && i <= dp ; i++) {
            dp = Math.max(dp, arr[i] + i);
        }
        return dp >= n -1;
    }
    
    // 时间和arr元素的大小相关，当arr元素较小时，时间复杂度为O(n) = n
    public static boolean dp1(int[] arr) {
        int n = arr.length;
        boolean[] dp = new boolean[arr.length];
        dp[0] = true; 
        for (int i = 0; i<n; i++) {
            if (dp[i]) {
                for (int j= i+1; j <n && j <= i + arr[i]; j++) {
                    dp[j] = true;
                    if (j == arr.length -1) return true;
                }
            } else {
                break;
            }
        }
        return dp[arr.length -1];
    }
    
    // timeout
    // O(n) = n^2
    public static boolean dp3(int[] arr) {
        boolean[] dp = new boolean[arr.length];
        dp[0] = true;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = dp[j] && (i-j<=arr[j]);
                if (dp[i]) break;
            }
        }
        return dp[arr.length-1];
    }
    
    public static boolean dfs(int[] arr) {
        
        return _dfs(arr, 0);
    }
    
     public static boolean _dfs(int[] arr, int idx) {
        if (idx == arr.length - 1) return true;
        int step = arr[idx];
         for (int i=idx+1; i<=idx+step&&i<arr.length;i++) {
             if (_dfs(arr, i)) return true;
         }
        return false;
    }
    
    
    
    
    // out of memory
    public static boolean bfs(int[] arr) {
        int len = arr.length;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
         
        boolean found = false;
        while (!list.isEmpty()) {
            int idx = list.removeFirst();
            if (idx == len - 1) return true;
            int step = arr[idx];
            for (int i = idx+1; i <= idx + step; i++) {
                list.add(i);
            }
        }
        
        return false;
    }
    
    
}


发表于 2022-03-24 15:23:28 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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