55. &134 Jump Game

题目要求：

一个数组存储了非负整形数据，数组中的第 i 个元素num[i],代表了可以从数组第i个位置最多向前跳跃nums[i]步；求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置。

Examples：

A = [2,3,1,1,4], return true.

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

A = [3,3,1,0,4], return true.

解题思路：

• 如何选择每个位置向后跳跃的步长？那么问题可以转换为：从第i个位置最远可以跳至第index[i]位置，那么如果第index[i]位置都不是最后一个元素，那就不管怎么跳都不可以跳至最后一个元素了。
• 所以首先确定每个位置可以跳跃的范围：1～i + nums[i]
• index[ ]保存可以最远的跳跃位置！！！

• 示意图

代码：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        index = []   #计算最远可以跳至的位置
        for i in range(len(nums)):
            index.append(i + nums[i])

        jump = 0   #代表已经走过的步数
        max_index = index[0]   #目前允许到大的最远的地方
        while jump < len(index) and jump <= max_index:  #直到jump跳跃到数组尾部或者junp超越了当前可以跳的最远位置
            if max_index < index[jump]:
                max_index = index[jump]
            jump += 1

        if jump == len(index):
            return True
        else:
            return False


    def canJumptwo(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        for i, length in enumerate(nums):
            if i > reach:
                break
            reach = max(reach, i + length)

        return reach >= len(nums) - 1


if __name__ == "__main__":

    print(Solution.canJumptwo(self= None, nums = [1, 1, 1, 1, 2, 0]))

• 示意图

    def canJumptwo(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        for i, length in enumerate(nums):
            if i > reach:
                break
            reach = max(reach, i + length)

        return reach >= len(nums) - 1

python 内置函数：

枚举(enumerate)是Python内置函数。它的用处很难在简单的一行中说明，但是大多数的新人，甚至一些高级程序员都没有意识到它。

• 它允许我们遍历数据并自动计数。默认从0开始计数。

a = [1,1,1,1,2,2,1,0,0,3]
for counter, val in enumerate(a):
    print(counter, val)

#结果是：
0 1
1 1
2 1
3 1
4 2
5 2
6 1
7 0
8 0
9 3

• enumerate也接受一些可选参数，这使它更有用。这个可选参数允许我们定制从哪个数字开始枚举。

for counter, val in enumerate(a, 1):
    print(counter, val)

#结果是：
1 1
2 1
3 1
4 1
5 2
6 2
7 1
8 0
9 0
10 3

• 还可以用来创建包含索引的元组列表

counter_list = list(enumerate(a, 1))
print(counter_list)

#结果是：
[(1, 1), (2, 1), (3, 1), (4, 1), (5, 2), (6, 2), (7, 1), (8, 0), (9, 0), (10, 3)]