跳跃游戏

[编程题]跳跃游戏

热度指数：13966 时间限制：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

算法知识视频讲解

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)

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)

Python

黄沙遮天

典型的动态规划问题，我们只需要计算计算跳转到每个下标所需要的最小跳转次数就可以了。首先令跳转次数列表list1=[0 for i in range(len(a))].然后使用动态规划方程式更新每一个下标的跳转次数

1.temp = list1[i - 1] + 1 if A[i - 1] >= 1

2.temlist.append(list1[j]) if j + A[j] >= i

list1[i]=min(temp,min(temlist)+1)

class Solution:
    def canJump(self, A):
        # write code here
        length = len(A)
        if length <= 1:
            return True
        list1 = [0 for i in range(length)]
        list1[0] = 0
        for i in range(1, length):
            temp = 0
            temlist = []
            if A[i - 1] >= 1:
                temp = list1[i - 1] + 1
            else:
                temp = 1000
            for j in range(0, i):
                if j + A[j] >= i:
                    temlist.append(list1[j])
            if len(temlist)!=0:
                list1[i] = min(temp, min(temlist) + 1)
            else:
                return False
        if list1[-1] == 0:
            return False
        else:
            return True

发表于 2020-06-25 15:26:28 回复(0)