[LeetCode][python3]Day25. Jump Game (30-Day LeetCoding Challenge)

  1. My solution
class Solution:
def canJump(self, nums: List[int]) -> bool:
l=len(nums)
index=0
maxpath=nums[0]
while index<l and index<=maxpath:
maxpath=max(maxpath,index+nums[index])
index+=1
if index!=l:
return False
return True
class Solution:
def canJump(self, nums: List[int]) -> bool:
N = len(nums)

target = N-1
for i in range(N-1, -1, -1):
if i + nums[i] >= target:
target = i

return target == 0
class Solution:
def canJump(self, nums: List[int]) -> bool:
# problem becomes, will we eventually get stuck on nums[i] == 0
# if nums[i] = 0, need to check nums[i-k] > k
# if satisfied, move on to find next zero
# if not satisfied until nums[0], return false

# if array length 1, already at last index
if len(nums) == 1: return True
# if array length not 1, and nums[0] is zero, we're already stuck
if nums[0] == 0: return False

# if last element is zero, we don't need to check it, we're guaranteed
# to reach it if nums[-2] is not zero, if nums[-2] is zero, we'll be
# checking later in this code whether we're stuck at it or not,
# if we'll be stuck at it, program will return False anyways.
if not nums[-1]:
nums.pop()

# if there's no 0 in nums, automatically True
if 0 not in nums: return True

# start from tail
i = len(nums)-1
while i > 0:
# look for zero, we only check if elements to the left of zero
# will get stuck at it
if nums[i]:
i -= 1
continue
zero = i # i index is zero
# while elements to the left of zero can only reach this zero or shorter
# we keep going left to look for a number that can jump past this zero
# if we find it, we go to top of while loop to look for another zero
while i >= 0 and nums[i] <= zero - i:
i -= 1
# if we are not able to find this number that can jump past zero at nums[0]
# i will change into -1, this is the only condition we fail the jump game.
if i == -1: return False
# if no failure is found, it means all zero can be jumped past, so we can win.
return True

--

--

--

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Four Faith Industrial routers Command Injection RCE Reverse Shell

Simplifying context managers in python

Bake Your Free Time — Vol I

Making your own assistant with Qt/QML and Google Speech-to-Text

Jenkins Environment using Docker

Now That’s a Flex(box)

Best Slack apps and integrations for a product manager — Part 1/3

Tricks and Tips to Work with Lottie

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
N2I

N2I

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

More from Medium

Concept of Time complexity with Python Examples

Python Basics: 07 arithmetic operations

Recursion and Python Strings

Python Tutorial for absolute beginners #1