遊戲模擬 Jump Game 青蛙過河 Leetcode_#55

Victor Rodriguez on Unsplash

題目敘述

題目會給我們一個輸入陣列nums，每個元素值代表那個格子點可以跳躍的最大長度。

一開始從最左邊的格子點出發開始跳，請問可以成功抵達終點，也就是最右邊的格子點嗎?

如果可以，返回 True。

如果不行，返回False。

題目的原文敘述

測試範例

Example 1:

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

0 -> 1 - > 4 ​
先從零跳一步到1，
再從1跳3步，可以抵達終點​，也就是第四個格子點。

Example 2:

Input: nums = [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.
無​解，跳不過去。

約束條件

Constraints:

• 1 <= nums.length <= 10^4

輸入陣列的長度介於1 ~ 10^4 。

• 0 <= nums[i] <= 10^5

每個格子點最小可以跳0格，相當於留在原地。代表題目可能會給陷阱格子。

最大可以跳10^5個格子。

演算法 第一知覺的想法

第一直覺想到就是依照遊戲規則去模擬，盡量往右邊跳，看看能不能從起點0開始跳到終點?

當然是可以的，但是仔細留意一下，nums[i]最大可以有10^5，代表每個格子點可能的選擇(也就是分枝)可以有十萬條路徑，顯然用直接進行模擬會存在執行速度太慢或者time-out超過時間限制的風險，因為是指數級別的枚舉所有跳躍路徑。

這題其實用DFS模擬，或者BFS模擬跳躍，還是勉強可以通過平台的測試。

但是，後面我們會介紹一個更好的演算法，採用貪心策略Greedy strategy的演算法來提升速度。

程式法 DFS模擬跳躍

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        destination = len(nums)-1

        if destination == 0:
            return True

        seen = set([0])

        def dfs(i):
            
            if i >= destination:
                return True
            
            for jump in range(1, nums[i]+1) :
                if (i + jump) not in seen:
                    seen.add( i + jump )
                    if i + jump >= destination or dfs( i + jump):
                        return True
            
            return False

        # ===========================
        return dfs( i = 0)

程式碼 BFS模擬跳躍

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        destination = len(nums)-1

        if destination == 0:
            return True

        bfs_q = deque([0])
        seen = set([0])
        
        while bfs_q:

            cur = bfs_q.popleft()
            
            for jump in reversed(range(1, nums[cur]+1)):

                if cur + jump >= destination:
                    return True

                if  cur+jump not in seen:
                    bfs_q.append( cur+jump )
                    seen.add( cur+jump )
        
        return False

演算法 Greedy 策略 盡量去延伸我能抵達的地方

其實題目真正問的關鍵在於"能不能夠"抵達終點?

題目並沒有去要求我們列出跳躍的路徑(也就是過程)。

題目只關心結果，能不能抵達終點?

換句話說，假如我們經由跳躍能夠碰觸的範圍，盡量去往右邊延伸，可以覆蓋到終點，那麼一定有解，可以從起點開始跳躍，抵達終點。

如果不行，則代表半路上就停下來了，已經盡力跳了，但是就是過不去，無解，返回False。

程式碼 Greedy 策略 盡量去延伸我能抵達的地方

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        # 能夠抵達的範圍
        max_reach = nums[0]

        for i, jump in enumerate(nums):
							
					   # 已經盡力跳了，但是到不了 index i，
					   # 半路上就被迫停下來了，無解。 
            if max_reach < i:
                return False
            
            # 盡量去往右邊延伸經由跳躍能夠碰觸的範圍，
            max_reach = max(max_reach, i + jump)
        
        # 假如跳耀的範圍能覆蓋終點，那麼一定有解
        return max_reach >= ( len(nums)-1 )

複雜度分析 Greedy 策略 盡量去延伸我能抵達的地方

令n=輸入陣列nums的長度

時間複雜度:

從左邊到右邊逐一檢查每個格子點，盡量去延伸跳躍能覆蓋的範圍，總共所需時間為O(n)。

空間複雜度:

用到的都是固定尺寸的臨時變數，總共所需空間為O(1)。

關鍵知識點

題目並沒有去要求我們列出跳躍的路徑(也就是過程)。

題目只關心結果，能不能抵達終點?

換句話說，假如我們經由跳躍能夠碰觸的範圍，盡量去往右邊延伸，可以覆蓋到終點，那麼一定有解，可以從起點開始跳躍，抵達終點。

如果不行，則代表半路上就停下來了，已經盡力跳了，但是就是過不去，無解，返回False。

Reference:

[1] Jump Game_Python solution sharing