今天是紀錄LeetCode解題的第四十五天

第四十五題題目：You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

給定一個從索引0開始的整數數組nums長度為n，每個元素nums[i]表示從索引i能跳躍的最大長度，換句話說，如果位於索引i，最大可以到i+j的任何符合以下條件的索引

傳回能跳到索引n-1的最小跳躍次數

解題思路

i從索引0開始遍歷至len(nums) - 1，我們定義farthest是每一跳可以到達的最遠距離，cur_end表示當前跳躍的長度，當cur_end == i時，表示到達最遠可達距離，此時我們要進行下一跳，把jump_count + 1，且把cur_end設為farthest

程式碼

class Solution:
    def jump(self, nums: List[int]) -> int:
        jump_count = 0
        cur_end = 0
        farthest = 0
        for i in range(len(nums)-1):
            farthest = max(farthest,i + nums[i])
            if i == cur_end:
                jump_count += 1
                cur_end = farthest
        return jump_count

執行過程

初始狀態

• nums = [2, 3, 0, 1, 4, 2, 1]
• jump_count = 0
• cur_end = 0
• farthest = 0

第一次執行(i = 0)

• farthest = max(farthest,i + nums[i]) = max(0,0+2) = 2
• if i == cur_end → True
• jump_count += 1 = 1
• cur_end = farthest = 2

第二次執行(i = 1)

• farthest = max(farthest,i + nums[i]) = max(2,1+3) = 4
• if i == cur_end → False

第三次執行(i = 2)

• farthest = max(farthest,i + nums[i]) = max(4,2+0) = 4
• if i == cur_end → True
• jump_count += 1 = 2
• cur_end = farthest = 4

第四次執行(i = 3)

• farthest = max(farthest,i + nums[i]) = max(4,3+1) = 4
• if i == cur_end → False

第四次執行(i = 4)

• farthest = max(farthest,i + nums[i]) = max(4,4+4) = 8
• if i == cur_end → True
• jump_count += 1 = 3
• cur_end = farthest = 8

以此類推繼續做，那因為i不會等於8出現，所以執行到這裡jump_count = 3就是答案了