欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【跳跃游戏】动态规划+双指针(python3)

程序员文章站 2022-07-08 10:59:03
目录题目描述思路题解题目描述https://leetcode-cn.com/problems/jump-game/思路题解从后向前遍历数组,设置一个指针i,指向当前遍历到的元素。设置一个指针j,初始值为0,代表离着到达目的节点的距离为0,不断更新可以到达目的节点的索引i最小的元素。遍历时,判断nums[i]和j的关系:若nums[i]

题目描述

https://leetcode-cn.com/problems/jump-game/

思路题解

从后向前遍历数组,设置一个指针i,指向当前遍历到的元素。设置一个指针j,初始值为0,代表离着到达目的节点的距离为0,不断更新可以到达目的节点的索引i最小的元素
遍历时,判断nums[i]和j的关系:

  1. 若nums[i]<j,则代表当前节点无法到达索引i最小的那个元素,于是继续向前推进i,并将j+1,因为前面的节点要到达索引i最小的那个元素要比当前元素的距离+1。
  2. 若nums[i]>=j,则代表当前节点能到达,则i继续向前推进,并重置j=1。

最后判断nums[0]和j的大小。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i=len(nums)-1
        j=0
        while i>0:
            if nums[i]<j:
                i-=1
                j+=1
            else:  #i>=j
                i-=1
                j=1
        if nums[i]>=j: return True
        else: return False

【跳跃游戏】动态规划+双指针(python3)

本文地址:https://blog.csdn.net/anan15151529/article/details/110130463