55. Jump Game

Given an array of non-negative integers nums, 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.

My Answer 1: Accepted (Runtime: 120 ms - 11.39% / Memory Usage: 16.6 MB - 5.98%)

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

1. nums 의 길이가 1 일때는 어떤 값이든 True / nums[0] 이 0 이면 무조건 False 처리
2. i (0 ~ len(nums)-1) 와 maxidx 를 이용해서 반복문 돌리기
3. maxidx 가 전체 길이보다 크거나 같으면 last index 에 도달할 수 있으므로 True
4. i 가 maxidx 까지 갔을 때의 nums[i] 값이 0 이면 False
5. 모두 아닐 경우 maxidx 값보다 큰 값이 있으면 update 해주고 i 는 1 씩 증가

Solution 1: Runtime: 80 ms - 93.08% / Memory Usage: 16.2 MB - 15.31%

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachableIndex = 0
        for curr in range(len(nums)):
            if curr + nums[curr] >= reachableIndex:
                reachableIndex = curr + nums[curr]
            if curr == reachableIndex:
                break
                
        return reachableIndex >= len(nums) - 1

내 방식과 비슷한데 훨씬 효율이 좋은 솔루션

Greedy 랑 DP 도 있는 거 같은데... 모른 척 하고 싶네요...^^