百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术文章 > 正文

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

myzbx 2025-05-24 15:42 16 浏览

一、需求介绍: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##

<script type="text/javascript" src="//mp.toutiao.com/mp/agw/mass_profit/pc_product_promotions_js?item_id=7409662537433645605"></script><script type="text/javascript" src="//mp.toutiao.com/mp/agw/mass_profit/pc_product_promotions_js?item_id=7409662537433645605"></script>

相关推荐

男人的内裤,到底可以穿多久?(男人内裤最多能穿几天)

女生们如果家里有男生可能会发现——他们对内裤很恋旧穿到褪色松垮穿到别有洞天穿到一网情深穿到人间蒸发都仍然...舍不得这位老伙计男生们到底有多热爱旧内裤?有外国媒体曾在街头采访,发现:女士们往往会随...

typeof 与 instanceof 区别(typeof与instanceof区别)

typeof操作符返回一个字符串,表示未经计算的操作数的类型使用方法如下:typeofoperandtypeof(operand)operand表示对象或原始值的表达式,其类型将被返回举个例子...

年纪轻轻病情就已是晚期!你还敢再喝这种饮料吗?

本文作者:谢祥成,浙江大学医学院附属邵逸夫医院肾内科主任医师吴俊男,浙江大学医学院附属邵逸夫医院肾内科主治医师30岁的金先生(化名)是一名才华横溢的设计师。半年前出现视物模糊,起初以为是用眼过度,没有...

typeof 与 instanceof 有什么区别

typeof和instanceof是JavaScript中用于类型检查的两个操作符,但它们的用途和适用场景有显著区别。以下是它们的区别及使用注意事项:1.typeof作用:返回一个变量的基本...

数据结构之顺序表(数据结构顺序表图书管理系统)

线性表定义线性表是n(n≥0)个具有相同特性的数据元素的有限序列。记作:(a1,a2,…,ai-1,ai,ai+1,…,an)线性表相关概念直接前驱元素:ai-1领先于ai,称a...

每一个成熟的人,都需要具备「翻篇」这种能力

“翻篇儿”——仿佛读出这个儿化音,才够表达那种潇洒的感觉是一种人生中非常重要的心理过程和心理技能。人生注定不完美,我们只要活着就会遭遇不愉快的经历,只有及时翻篇儿,才能把更多注意力放在当下,不被过去的...

打通 JAVA 与内核系列之 一 ReentrantLock 锁的实现原理

写JAVA代码的同学都知道,JAVA里的锁有两大类,一类是synchronized锁,一类是concurrent包里的锁(JUC锁)。其中synchronized锁是JAVA语言层面提供的能力,在此不...

韩国吃货主播,美食声控咀嚼音,你是搬运工,好吃到停不下来

刘姐畅谈。Hey,Hongsi。TodaywehaveassortedtoysthatImade。Foryouguysfirst。Itlookscrunchybecause...

黄子韬2019新歌最好的我们完整歌词介绍在哪可以听

最好的我们(TheBestofUs)-黄子韬词:黄子韬曲:黄子韬编曲:DarylK制作人:DarylK助理制作:郭舒文和音:黄子韬电吉他:CalvinC木吉他:雷十一录音室:Kong...

刷一道LeetCode -- 三数之和(三数之和算法)

原题:https://leetcode-cn.com/problems/3sum/给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c...

隐藏在阳光当中的地球刺客(隐藏在阳光下的秘密)

小行星什么时候会撞击地球?这一直是大家比较关注的问题,特别是当大家知道地球上前一任住户是亡于小行星之后,就更加关注这个问题了。图1尤卡坦半岛的陨石坑(NASA)实际上,地球每天都会遭受到一些天体的袭...

安卓手机爱奇艺app中离线视频导出

安卓手机爱奇艺app中离线视频导出:通常我在爱奇艺中发现好的视频,想保存下来,点击离线缓存,缓存好后,在手机上可以查看,但是使用手机连接电脑打开后,发现保存视频的文件夹是空的。1)在手机中爱奇艺文...

50款经典奥斯汀月季,超多图片,抗病好养新手必种的月季

【50款经典奥斯汀月季】大家好,今天来给大家介绍50款经典的奥斯汀月季,奥斯汀是一位伟大的育种家,以他命名的奥斯汀公司也繁育出了数量众多的月季品种。根据木木的种植经验,奥斯汀的月季大多植株长势良...

你也想像J姐一样在梦幻芭比大house里“哭泣”吗?

“6年前我的兜里只揣着400元美金,现如今我已经住上了这上亿豪宅”他是一个我行我素,敢说敢做的一个网红博主他测评过的彩妆都卖断货了他的自创同名品牌深受好评他就是JeffreeStar,你们传说中的J...

VB Do While\Until,Loop循环语句

DoWhile\Until…….Loop循环语句上一节讲了For……Next循环语句,这节讲DoWhile\Until…….Loop循环语句。有人会有疑问,既然有For循环,还要Do循环干什么?它...