首页 > 试题广场 >

跳跃游戏(一)

[编程题]跳跃游戏(一)

热度指数：5339 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则返回true，否则返回false。

数据范围:

$1<=nums.length<= 2\times10^5$

$0<=nums[i]<=10^5$

示例1

输入

[2,1,3,3,0,0,100]

输出

true

说明

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

示例2

输入

[2,1,3,2,0,0,100]

输出

false

说明

无论怎么样，都跳不到nums[6]=100的位置

算法知识视频讲解

唐氏综合征

这道题不考虑跳跃次数，只考虑是否会跳到最后，给出两种解法

一. DP 解法：判断能否跳到第 i 个时，应该考虑从哪个位置开始，并且开始位置一定可以达到，因此状态转移时必须要考虑这两个条件，如果当前位置无法达到时，后面的就没必要判断了，直接返回false 即可：

public static boolean canJump(int[] nums) {
        // write code here
        boolean[] dp = new boolean[nums.length + 1];
        dp[0] = true;
        dp[1] = true;
        int pos = 1;
        for (int i = 2; i <= nums.length; i++) {
            for (int j = pos; j < i; j++) {
                if (dp[j] && nums[j - 1] >= i - j) {
                    dp[i] = true;
                    pos = j;
                    break;
                }
            }
            if(!dp[i]) return false;
        }
        return dp[nums.length];
    }

二：贪心算法

1. 尝试每个位置能到达的最远距离，最后取个最大值即可，这种最简单，比DP更容易想到，更容易理解

public static boolean canJump(int[] nums) {
        // write code here
         int currPos = 0;
        for (int i = 0; i < nums.length && i <= currPos; ++i) {
            currPos = Math.max(currPos, i + nums[i]);
            if (currPos >= nums.length - 1) return true;
        }
        return currPos >= nums.length - 1;
    }

发表于 2024-07-19 22:50:55 回复(0)

空中转体一周半

用一个变量记录能到达的最大下标，maxindex = i + nums[i].结束循环的时候判断该下标是否到达数组最后即可。

import java.util.*;
public class Solution {
    public boolean canJump (int[] nums) {
        int maxindex = 0;
        for(int i = 0; i < nums.length && i <= maxindex; ++i) {
            maxindex = Math.max(maxindex, i + nums[i]);
            if(maxindex >= nums.length - 1)return true;
        }
        return maxindex >= nums.length - 1;
    }
}

发表于 2023-02-24 11:11:20 回复(0)

Java

牛客499848474号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        // write code here
        boolean[] canJump = new boolean[nums.length];
        if (nums.length == 1) {
            return true;
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= nums.length - 1) {
                canJump[i] = true;
            } else {
                for (int j = nums[i]; j >= 1; j--) {
                    if (canJump[j + i]) {
                        canJump[i] = true;
                        break;
                    }
                }
            }
        }
        return canJump[0];
    }
}

发表于 2025-01-02 09:35:41 回复(0)

Python 3

45度信仰

从第一个元素开始，每次选取最大的 val。 value = nums[ i ], val = value+ i + 1 。当 val >= len(nums)，可以抵达

class Solution:
    def canJump(self , nums: List[int]) -> bool:
        length = len(nums)
        if length <= 1:
            return True
        i = 0
        val =  nums[i] + i
        if val >=len(nums)-1:
            return True
        while True:
            maxs = 0
            for j in range(i+1,val+1):
                if j < len(nums)-1:
                    val =  nums[j] + j
                    if val >= maxs:
                        maxs = val
                        i = j
                    if maxs >= len(nums)-1:
                        return True
            if not maxs:
                return False

发表于 2024-10-06 22:42:06 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        // write code here
        //最大跳远距离
        int maxReach=0;
        //循环维护最大跳转距离
        for(int i=0;i<nums.length;i++){
            //如果最大跳远距离无法到达该点为false
            if(maxReach<i){
                return false;
            }
            //如果最大跳远距离大等于目标位置为true
            if(maxReach>=nums.length-1){
                return true;
            }
            //遍历每个节点，只要该节点的跳远距离大于maxReach，就更新maxReach
            maxReach=Math.max(maxReach,i+nums[i]);
        }

        return true;
    }
}

发表于 2023-05-19 11:10:31 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return bool布尔型
*/
func canJump( nums []int ) bool {
    n:=len(nums)
    end:=0
    for i:=0;i<n;i++{
        if end<i{
            return false
        }
        end=max(end,i+nums[i])
    }
    return true
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-07 12:05:27 回复(0)

Java

BlueProtocol

public boolean canJump (int[] nums) {
		// write code here
		int len = nums.length;
		int end = 0;
		for (int i = 0; i < len; i++) {
			if (i > end) return false;
			end = Math.max(end,i + nums[i]);
		}
		return true;
	}

发表于 2022-10-13 09:51:43 回复(0)

kyLinkChen

package main

//import "fmt"

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return bool布尔型
*/
func canJump( nums []int ) bool {
for i := len(nums) - 1; i >= 0; i-- {
tmpNums := nums[:i + 1]
if len(tmpNums) <= 1 {
break
}
endIndex := testJump(tmpNums)
if endIndex == -1 {
return false
}
i = endIndex
}
return true
}

func testJump(nums []int) int {
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] >= len(nums) - i - 1 {
return i
}
}
return -1
}

发表于 2022-07-28 09:43:00 回复(0)

Java

查尔斯的匕首

 public boolean canJump (int[] nums) {
        // write code here
        if(nums.length==1)
            return true;
        int num=1;
        int j=1;
        for(int i=nums.length-1;i>0;){
            if(i-j<0)
                return false;
            if(nums[i-j]>=j){
                 if(i-j==0)
                    return true;
                i--;
                j=1;
            }else{
                j++;
            }
        }
        return false;
    }
}

发表于 2022-05-30 21:48:45 回复(0)

danspace

class Solution:
    def canJump(self , nums: List[int]) -> bool:
        # write code here
        reach = nums[0]
        for i in range(len(nums)):
            if reach < i: 
                return False
            if i + nums[i]>= len(nums)-1:
                return True
            reach = max(reach,i + nums[i])

发表于 2022-04-24 11:52:19 回复(0)

C++

the幻云

    //贪心策略：在cover范围内移动，不断更新cover范围，若可以覆盖整个范围，那么最后点可达
    //直白说，就是每次取最大覆盖范围，最后就可以取到全局最大范围
    bool canJump(vector<int>& nums) {
        // write code here
        int cover=0;//在没跳的时候，只能从下标为0的地方开始跳，就覆盖范围为0
        for(int i=0;i<=cover;i++)
        {
            cover=max(cover,i+nums[i]);
            if(cover>=nums.size()-1) 
                return true;
        }
        return false;
    }

发表于 2022-04-15 19:01:10 回复(0)

C++

QNBZ

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            if(i>res)return false;
            res=max(res,nums[i]+i);
            if(res>=nums.size()-1)return true;
        }
        return false;
    }
};

发表于 2022-01-07 14:21:42 回复(0)

Java

大丸子啊啊啊

public boolean canJump (int[] nums) {
boolean[] res = new boolean[nums.length];
int max = 0;
for(int i=0;i<nums.length;i++){
if(i>max) return false;
if(nums[i]+i>max){
max = nums[i]+i;
}
if(max>=nums.length-1) return true;
}
return false;
}

发表于 2021-12-15 16:42:49 回复(0)

倔强小头

public static boolean canJump(int[] nums) {
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            //严格控制0的输出
            if(i>res) return false;
            res=Math.max(res,i+nums[i]);
            if(res>=nums.length-1) return true;
        }
        return false;
    }

发表于 2021-11-26 19:38:08 回复(0)

提交观点

问题信息

动态规划

上传者：牛客301499号

难度：

14条回答 59收藏 2833浏览

通过挑战的用户

查看代码

Ice&雪

2022-09-16 18:19:53
sunuv

2022-09-16 08:23:26
牛客50552...

2022-09-15 15:31:47
QNBZ

2022-09-15 08:39:43
牛客27437...

2022-09-14 16:19:03

跳跃游戏(一)

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题