玩蛇(Python) - 算法练习:leetcode 55. 跳跃游戏

一、需求介绍：55. 跳跃游戏

1.1 输入

给你一个非负整数数组 nums, 数组中的每个元素代表你在该位置可以跳跃的最大长度。

1.2 要求

你最初位于数组的 第一个下标 。

1.3输出

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false。

1.4 前置条件（无需额外判断）

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

二、需求分析设计

2.1 算法分析

1、根据当前位置的值，可以判断出来最远到达那个位置；移动到下一个位置，并刷新这个最远达到的位置，以此类推。

2、当最远到达位置超过了终点位置，那么就可以到达，返回True；反之如果到了倒数第二个位置，还未到达最后一个位置，返回False。

2.2 算法代码实现（代码自注释且有详细文字注释，还看不懂介绍异性朋友给你）

   #-*- coding:utf-8 -*-
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
       
        #Author: ShanGouXuehui
        #Date: 2024-09-01
        #Git: https://github.com/ShanGouXueHui/PythonAlgorithm
        #Find More Python Algorithm Cases: https://m.toutiao.com/is/iYSgcfwq/
        #Personal Page: https://www.toutiao.com/c/user/token/MS4wLjABAAAAaW5663GHobdB_4icGBE0z2IJSWBSYeEAmoCfHTazjhTREfuBFo6wZCPR34-atRpn/?source=profile
        """
       
        #获得元素个数，用于后续复用
        num_of_elements = len(nums)
        #到达最远的位置, 从第一个位置开始
        reach_farest_position = 0
       
        for position_index in range(num_of_elements):
            #如果可以到达当前位置，则继续往下跳跃
            if reach_farest_position >= position_index:
                #当前位置可以到达的最远位置为position_index + nums[position_index]
                #历史最远，和本位置最远，做一个比较，保留更远的值
                reach_farest_position = max(reach_farest_position, position_index + nums[position_index])
                #如果到达终点返回True
                if reach_farest_position >= num_of_elements - 1:
                    return True
            #如果没有到达当前位置，则游戏结束
            else:
                return False
               
        #最终没有到达最后一个位置
        return False
       
if __name__ == "__main__":
    cs = Solution()
   
    # 示例 1：
    # 输入：
    nums = [2,3,1,1,4]
    # 输出：true
    # 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
    print('示例1： ', cs.canJump(nums))
   
    # 示例 2：
    # 输入：
    nums = [3,2,1,0,4]
    # 输出：false
    # 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
    print('示例1： ', cs.canJump(nums))

2.3 算法结果验证

PS D:\Shangouxuehui_Git\PythonAlgorithm-main> python -u "d:\Shangouxuehui_Git\PythonAlgorithm-main\jump_game1.py"
示例1： True
示例1： False

2.4 源码下载：

https://github.com/ShanGouXueHui/PythonAlgorithm

2.5 更多Python算法合集访问

https://m.toutiao.com/is/iYSgcfwq/

##山狗学会 License Start##

转载请注明出处，"今日头条"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元

主页链接：山狗学会主页

##山狗学会 License End##