[LeetCode] 55. Jump Game

写了一个符和直觉的递归，时间超限了。

from typing import List
import time

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        return self.isreach(nums, 0)

    def isreach(self, nums: List[int], start: int) -> bool:
        if start >= len(nums) - 1:
            return True

        furthest_jump = min(start + nums[start], len(nums) - 1)

        for next_position in range(start + 1, furthest_jump + 1):
            if self.isreach(nums, next_position):
                return True

        return False


def main():
    start_time = time.time()
    print(Solution().canJump([2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6]))
    end_time = time.time()
    print("Time taken: {:.6f} seconds".format(end_time - start_time))
    
if __name__ == '__main__':
    main()

False
Time taken: 148.563587 seconds

Process finished with exit code 0

改用贪心算法，使用max_reachable记录可达的最大list下标。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        #1
        if len(nums) ==1:
            return True
        #else
        max_reachable = 0
        for i,element in enumerate(nums):
            if i > max_reachable:
                return False
            max_reachable = max(i + element, max_reachable)
        return True