#55 Jump Game——Top 100 Liked Questions

待我称王封你为后i 2022-01-30 13:01 163阅读 0赞

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

**Example 1:**

Input: [2,3,1,1,4]
    Output: true
    Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Example 2:**

Input: [3,2,1,0,4]
    Output: false
    Explanation: You will always arrive at index 3 no matter what. Its maximum
                 jump length is 0, which makes it impossible to reach the last index.

> """  
> 第一次：num\[i\]+i为i位置所等到达的最大距离，遍历后如果最大距离小于L-1，说明不能到达末尾，如果>=L-1，说明肯定能到达末尾。同时在每次遍历时，应使dist>=i，这是为了避免元素为零的特例  
> """
> 
>     class Solution(object):
>         def canJump(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: bool
>             """
>             L = len(nums)
>             dist = 0
>             for i in range(L-1):
>                 if dist >= i:
>                     dist = max(dist, i + nums[i])
>             if dist < L - 1:
>                 return False
>             return True
> 
> """
> 
> Runtime: 72 ms, faster than 58.03% of Python online submissions for Jump Game.
> 
> Memory Usage: 13.3 MB, less than 33.52% of Python online submissions for Jump Game.
> 
> """

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关 #15 3Sum——Top 100 Liked Questions

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a +

- 日理万妓/ 2022年02月03日 02:34/ 0 赞/ 132 阅读

相关 #62 Unique Paths——Top 100 Liked Questions

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

￡神魔★判官ぃ/ 2022年01月30日 15:11/ 0 赞/ 160 阅读

相关 #55 Jump Game——Top 100 Liked Questions

Given an array of non-negative integers, you are initially positioned at the first index

待我称王封你为后i/ 2022年01月30日 13:01/ 0 赞/ 164 阅读

相关 #49 Group Anagrams——Top 100 Liked Questions

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea",

àì夳堔傛蜴生んèń/ 2022年01月30日 03:43/ 0 赞/ 238 阅读

相关 #48 Rotate Image——Top 100 Liked Questions

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees

Bertha 。/ 2022年01月30日 03:15/ 0 赞/ 212 阅读

相关 #75 Sort Colors——Top 100 Liked Questions

Given an array with n objects colored red, white or blue, sort them [in-place][] so that

短命女/ 2022年01月29日 03:41/ 0 赞/ 309 阅读

相关 #72 Edit Distance——Top 100 Liked Questions

Given two words word1 and word2, find the minimum number of operations required to conve

妖狐艹你老母/ 2022年01月29日 03:09/ 0 赞/ 225 阅读

相关 #78 Subsets ——Top 100 Liked Questions

Given a set of distinct integers, nums, return all possible subsets (the power set). No

本是古典何须时尚/ 2022年01月27日 02:09/ 0 赞/ 235 阅读

相关 #79 Word Search——Top 100 Liked Questions

Given a 2D board and a word, find if the word exists in the grid. The word can be const

柔光的暖阳◎/ 2022年01月26日 10:43/ 0 赞/ 216 阅读

相关 55.Jump Game

Given an array of non-negative integers, you are initially positioned at the first index

红太狼/ 2021年10月29日 15:54/ 0 赞/ 313 阅读