题解 | #跳跃游戏(一)#

跳跃游戏(一)

http://www.nowcoder.com/practice/23407eccb76447038d7c0f568370c1bd

题目分析

题目给出我们一个数组，数组中每个数字表示当前位置能够向数组末尾前进的步数

题目要求我们判断给定数组下，是否能从数组开始位置到达末尾位置，返回判断的结果

方法一：动态规划（超时）

实现思路
- 我们用一个一维的dp数组，dp[i]=1表示当前位置i可以到达
- 我们遍历nums数组，针对位置i的数字
  - 如果此时dp[i]=0则说明前面的移动过程未能到达当前位置，则返回False
  - 如果此时dp[i]=1，则根据nums[i]的大小，向后更新nums[i]个可到达位置，将dp数组中对应位置标记为1
- 最后判断dp[n-1]是否为1即可
- 需要额外注意下一些边界条件的设置，比如dp[0]=1的初始化，相当于一开始第一个位置就可以访问到

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return bool布尔型
#
class Solution:
    def canJump(self , nums: List[int]) -> bool:
        # write code here
        n = len(nums)
        if n == 1:
            return True
        dp = [0] * n
        dp[0] = 1				# dp 初始化
        for i in range(n-1):	# 遍历每一个数字
            if dp[i] == 0:		# 判断是否可达
                return False
            for j in range(i+1, min(n,i+nums[i]+1)):	# 向后标记可达位置
                dp[j] = 1
        return dp[n-1]

复杂度分析

时间复杂度： $O(\sum_{i=0}^n{min(n,nums[i])})$ ，时间代价和数组中的元素值、数组长度边界有关，其中 $n$ 表示数组长度，算法中将数组中所有的数字作为向后遍历的访问数量，因此总时间代价时所有数字的加和，并且不超过数组最长的长度。
空间复杂度： $O (n)$ ，申请了与给定数组长度线性大小的空间

方法二：单指针

实现思路
- 我们标记一个reach值，作为当前能够走到最远位置的标记
- 通过遍历数组，对于每一个数字
  - reach都判断是否可以到达当前位置，做一次判断
  - reach再判断是否当前已经可以超过最末尾的位置，做一次判断
  - reach最后更新当前可达的最远位置，看当前数字提供的最远跨度在哪里
- 返回判断结果即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return bool布尔型
#
class Solution:
    def canJump(self , nums: List[int]) -> bool:
        # write code here
        n = len(nums)
        reach = 0
        for i in range(n):
            if reach < i:			# 是否可达判断
                return False
            if reach >= n-1:			# 是否可以到达最后位置判断
                return True
            reach = max(reach, i + nums[i])		#更新最远可达位置
        return True