首页 > 试题广场 >

跳跃游戏

[编程题]跳跃游戏

热度指数：13902 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个非负整数数组，你最初在数组第一个元素的位置

数组中的元素代表你在这个位置可以跳跃的最大长度

判断你是否能到达数组最后一个元素的位置

例如

A =[2,3,1,1,4], 返回 true.

A =[3,2,1,0,4], 返回 false.

示例1

输入

[2,3,1,1,4]

输出

true

示例2

输入

[3,2,1,0,4]

输出

false

算法知识视频讲解

LinuX18

bool canJump(int A[], int n) 
    {
      int maxReach = 0;
      for(int i=0;i<n && i<=maxReach;i++)
         maxReach = max(maxReach,i+A[i]);  /// 跳到该点后还能到达的极限
      if(maxReach<n-1)
         return false;
      return true;  
    }

发表于 2017-07-08 21:58:44 回复(7)

JacobGo！

/*
	 * 贪心算法的运用 Runtime: 8 ms.Your runtime beats 73.77 % of java submissions.
	 */
	public boolean canJump(int[] nums) {
		// 异常输入
		if (nums == null || nums.length < 1)
			return false;
		if (nums.length == 1)
			return true;
		int last = nums.length - 1;
		for (int i = nums.length - 2; i >= 0; i--) {
			if (i + nums[i] >= last)
				last = i;
		}
		return last == 0;
	}

发表于 2017-06-26 10:52:40 回复(1)

淡泊宁静吴传奇

class Solution 
{
public:
    bool canJump(int A[], int n) 
    {
       int max=0;            //max标记能跳到的最远处。
       for(int i=0;i<n&&max>=i;++i)    //max>=i表示此时能跳到i处，0<=i<n表
           if(i+A[i]>max)max=i+A[i];   //示扫描所有能到达的点，在改点处能跳到的最远处。
       return max>=n-1?true:false;     //如果最后跳的最远的结果大于等于n-1，那么满足
    }                                  //能跳到最后。
};

发表于 2016-09-04 22:49:39 回复(5)

Shuttle_new

动态规划，初始第一个index为true，其他全部为false；如果当前index为true则把从当前开始到后面的A[i]个位置都变成true.最后一个index如果为true就说明可以到达。

    bool canJump(int A[], int n) {
        vector<bool> dp(n,false);
        dp[0]=true;
        for(int i=0;i<n&&dp[i];i++)
            {
            for(int j=0;j<=A[i];j++)
                dp[i+j]=true;
        }
        return dp[n-1];
    }

发表于 2017-04-13 16:20:53 回复(3)

丶沉梦昂志

public class Solution {
    public boolean canJump(int[] A) {
        int curFast = 0;
        for (int i = 0; i < A.length - 1; i++) {
            if (i <= curFast)
                curFast = Math.max(curFast, i + A[i]);
        }
        if (curFast >= A.length - 1)
            return true;
        else
            return false;
    }
}

发表于 2017-11-22 16:22:46 回复(0)

微软内推小王子

O(n²)版，leetcode会判超时

class Solution(object):
    def canJump(self, nums):
        res = [0] * len(nums)
        res[0] = 1
        for i in range(len(nums)):
            if res[i] == 0:
                continue
            for j in range(1, nums[i] + 1):
                if i + j < len(nums):
                    res[i + j] = 1
            if res[len(nums) - 1] == 1:
                return True
        return res[len(nums) - 1] == 1

O(n)版：

class Solution(object):
    def canJump(self, nums):
        i = 0
        limit = 1 #目前最远到不了的下标
        while i < limit:
            limit = max(limit, nums[i] + i + 1) #更新下标
            if limit >= len(nums):
                return True
            i += 1
        return False

顺便把Jump Game II 的答案也放这里：

class Solution(object):
    def jump(self, nums):
        if len(nums) == 1:
            return 0
        i = 0
        step_flag = 1
        limit = 1
        res = 0
        while i < limit:
            if i >= step_flag:
                res += 1
                step_flag = limit
            limit = max(limit, nums[i] + i + 1)
            if limit >= len(nums):
                return res + 1
            i += 1

编辑于 2017-10-07 14:20:03 回复(0)

C/C++

卷积神经网络哦

C++谁有我短

bool canJump(int A[], int n) {
        int res = 0;
        for(int i=0;i<n&&i<=res;i++) res=max(res, i+A[i]);
        return res >= n - 1;
    }

发表于 2019-07-04 15:26:23 回复(1)

C/C++

hello古斯卡

class Solution {
public:
    bool canJump(int A[], int n) {
        int jumpMax=0;
        for(int i=0;i<n;i++){
            if(jumpMax<i){
                return false;
            }
            jumpMax = max(jumpMax,i+A[i]);
        }
        return true;
    }
};

发表于 2019-10-31 17:00:17 回复(0)

一切顺利，天天开心


	import java.math.*;



	public classSolution {



	public booleancanJump(int[] A) {



	int maxReach = 0;



	int n=A.length;



	for(int i=0;i<n && i<=maxReach;i++){



	    if(maxReach<(i+A[i])){



	        maxReach=i+A[i];



	    }



	}



	if(maxReach<n-1)



	return false;



	return true;



	}



	}

编辑于 2017-12-02 10:54:55 回复(0)

C/C++

nbgao

class Solution {
public:
    bool canJump(int A[], int n) {
        int Max = 0;
        for(int i=0;i<n && i<=Max;i++)
        	Max = max(Max,A[i]+i);
        if(Max < n-1)
        	return false;
        return true;
    }
};

发表于 2017-08-05 01:25:18 回复(0)

后劲好大

public class Solution {
    public boolean canJump(int[] A) {
        if(A == null || A.length <= 0)
        	return false;
        // 定义一个boolean的数组，判断数组第i是否可达
        boolean[] isJump = new boolean[A.length];
        isJump[0] = true;
        for(int i = 0; i < A.length; i++){
        	if(isJump[i]){
        		for(int j = 1; j <= A[i]; j++){
                        // 这里要判断是否越界,超过A.length说明可以到达
        			if(i + j < A.length)
        				isJump[i + j] = true;
        			else
        				return true;
        		}       			
        	}
        }
        return isJump[A.length - 1];
    }
}

编辑于 2017-05-04 10:52:45 回复(0)

Java

詆調壹點

public class Solution {
    public boolean canJump(int[] A) {
		boolean[] flag = new boolean[A.length];
		flag[0] = true;
		for (int i = 0; i < A.length; i ++) {
			if(flag[i]) {
				int maxPosition = Math.min(i + A[i], A.length - 1);
				for (int j = i + 1; j <= maxPosition; j ++) {
					flag[j] = true;
				}
			}
			if(flag[A.length - 1]) return true;
		}
		return false;
	}
}

编辑于 2017-03-25 16:35:33 回复(0)

xyxlil

//深度优先搜索
class Solution {
public:
    bool search(vector<int>& A, int start, int n, int mark[]) {
        if(start >= n - 1) return true;
        //if(A[start] == 0) return false;
        mark[start] = 1;
        int maxjump = start+A[start];
        for(int i = start+1; i <= maxjump; i++) {
            if(!mark[i] && search(A, i, n, mark))
                return true;
        }
        return false;
    }
    bool canJump(vector<int>& A) {
        int mark[A.size()];
        memset(mark, 0, sizeof(mark));
        return search(A, 0, A.size(), mark);
    }
};

发表于 2017-03-12 14:21:14 回复(0)

WangYu_

/*
当前所在格子的下标记为sum，下一步需要跳几个格子为A[sum]；
sum+A[sum]为下一次到达的格子下标，若大于n-1，则说明可到达；小于则继续循环；
*/
class Solution {
public:
    bool canJump(int A[], int n) {
        if(n<=1) return true;
        int sum=0;
        while(sum<n&&A[sum]!=0)
        {
            sum+=A[sum];
            if(sum>=n-1) 
                return true;
        }
        return false;
    }
};

发表于 2017-10-16 09:21:33 回复(2)

求天求地求Offer

//楼上的看起来很简洁，但是等于全部遍历一边，并不好
    public boolean canJump(int[] A) {
         for(int i=0;i<A.length-1;){
             int max=i;
             for(int j=i+1;j<=A[i]+i;j++){
                 if(j>=A.length-1)
                     return true;
                 max=Math.max(max,j+A[j]);
             }
             if(i==max)
                 return false;
             i=max;
         }
        return true;
    }

发表于 2018-08-01 19:48:58 回复(0)

Python

深藏功与名的他很想回学校

class Solution:
def canJump(self , A ):
# write code here
roadlist = [0 for i in A] # 某个位置是否能够到达终点
roadlist[-1] = 1
for i in range(len(A)-2,-1,-1):
if sum(roadlist[i+1:i+A[i]+1]): roadlist[i] = 1
return roadlist[0] == 1

发表于 2023-09-17 11:34:40 回复(0)

虚与委蛇

'''
1.具体思路是先判定跳出条件是，因为是跳跃的最大长度，
判定最后一跳是否超出最后的索引位置，如果是这可以完成该游戏，退出循环，返回true.
2.而不能完成游戏关键是是否有0值，
其中如果有0值，说明不能跳动，判定该0值是否为最后索引即可。
'''

class Solution:
    def canJump(self , A ):
        i = 0
        n = len(A)
        while i<(n-1):
            if A[i] != 0:
                i += A[i]
            else:
                return(A[i]==A[n-1])
        return 1

发表于 2021-08-24 21:46:37 回复(0)

Python

牛客31747223号

#
# 
# @param A int整型一维数组 
# @return bool布尔型
#
class Solution:
    def canJump(self , A ):
        # write code here
        l = len(A)
        i = A[0]
        j = 0
        if l == 1:
            return True
        else:
            while i < l - 1:
                j = A[i]
                if A[i] == 0:
                    return False
                else:
                    i += j
            return True

发表于 2020-11-23 23:07:19 回复(0)

tornado123

具体讲解看代码的注释：

public class JumpingGame {
    /**
     *
     * @param A int整型一维数组
     * @return bool布尔型
     */
    public boolean canJump (int[] A) {
        int[] resultList = new int[A.length + 1];
        // 为一维数组 resultList 填充初始值 0
        Arrays.fill(resultList, 0);
        // 数组的起始位置一定是可达的
        resultList[0] = 1;
        int len = 0;
        for (int i = 0; i < A.length - 1; i++) {
            len = A[i];
            // 判断可达点 并且 len > 0
            if (len > 0 && resultList[i] == 1) {
                // 填充 下标为 i + 1 ~ i + len 的值为1， 表示当前的下标点是可以被到达的。 下面的函数fill 中包含起点 i + 1, 不包含终点 i + len + 1
                Arrays.fill(resultList, i + 1, (i + len + 1 > A.length ? A.length : i + len + 1), 1);
            }
        }
        return (resultList[A.length - 1] == 1 ? true : false);
    }
}

发表于 2020-09-20 00:44:49 回复(0)

科学xx

public boolean canJump (int[] A) {
int max = 0;
for (int i = 0; i < A.length; i++) {
if (max < i){
return false;
}
max = Math.max(max,i+A[i]);
}
return true;
}

发表于 2020-08-30 18:14:40 回复(0)