最短路徑應用: 遊戲模擬 Jump Game IV 青蛙過河 IV_Leetcode_#1345

Maarten van den Heuvel on Unsplash

題目敘述

題目會給我們一個輸入陣列arr，起始點固定在索引為0的位置，
終點固定在索引為n-1的位置。

假設當下所在的索引位置為i，那麼每次移動的時候，可以跳到i-1，i+1，或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。

例如:

假設當下在i=3的位置，arr[i] = 5，那麼下一步可以跳到i-1=2 或者i+1=4，或者陣列上其他陣列元素值=5的位置。

請問，從起點0出發跳到終點n-1，所需要的最小跳躍次數為多少?

題目的原文敘述

測試範例

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

arr[0] 跳到 arr[4]，因為兩者的元素值相同，都是100
arr[4] 跳到 arr[3]，3 = 4-1 是相差一隔的鄰居​
arr[3] 跳到 arr[9]，因為兩者的元素值相同，都是404

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.

起點剛好等於終點，不用跳就已經抵達終點。
所以0次。​

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

arr[0] 可以直接跳到 arr[7]，因為兩者的元素值相同，都是7​

約束條件

Constraints:

• 1 <= arr.length <= 5 * 10^4

陣列長度界於1~五萬之間。

• -10^8 <= arr[i] <= 10^8

每個陣列元素值界於 負一億~正一億 之間。

演算法

題目已經無形中保證一定有解，為什麼?

因為最差情況下，就是每次都從i往右跳一格到i+1，總有一步會抵達終點n-1。

但是，題目要問的是從起點0到終點n-1的最短路徑需要幾次跳躍?

抽象的想，可以把arr[i]每個陣列格子都視為一個節點。

然後 arr[i] 和 arr[i-1], arr[i+1]各有一條邊相連，成本為1。

假如arr[j] = arr[i] 元素值相等，arr[i] 也和其他的arr[j] 有邊相連，成本為1。

到這裡，就把原本跳躍次數的問題，轉化成圖論中的最短路徑搜索問題，
起點為Node 0，終點為 n-1，最少要經過幾條邊(相當於幾次跳躍)才能抵達。

在無權重的圖 或者 權重都相等的圖中尋找最短路徑，那很自然就會想到BFS先天具有點播源擴散的特質，也因此具有最短路徑的搜索性質。

我們只要從Node 0 開始進行BFS廣度優先搜尋，一層一層往外拜訪，
當拜訪到Node n-1的時候，
當下的步數 = 最短路徑長度 = 從起點到終點的最小跳躍次數。

程式碼 BFS先天在無權圖 或者 等權圖 具有最短路徑的特質

class Solution:
    def minJumps(self, arr):

        n = len(arr)
        destination = n-1

        ## Dictionary: a group of the same number
        # key: number 
        # value: idx of number
        same_number = defaultdict(list)

        for idx, number in enumerate(arr):
            same_number[number].append(idx)

        #         src = 0, step = 0
        bfs_q = deque([(0, 0)])

        # visited set
        seen = set([0])

        # Launch BFS from starting index = 0
        # BFS naturaly has shortest path from source to destination.
        while bfs_q:

            cur, step = bfs_q.popleft()

            # Reach destination
            if cur == destination:
                return step

            # Go to the neighbor to previous index as well as next index
            for next_idx in (cur+1, cur-1):
                if 0 <= next_idx < n and next_idx not in seen:
                    bfs_q.append( (next_idx, step+1) )
                    seen.add( next_idx )

            # Go to friend index who has the same number with me      
            for next_idx in same_number[ arr[cur] ]:
                if next_idx not in seen:
                    bfs_q.append( (next_idx, step+1) )
                    seen.add( next_idx )

            # Avoid repeated redundant traversal which would not yield better result
            del same_number[ arr[cur] ]

        
        return -1

複雜度分析 BFS先天在無權圖 或者 等權圖 具有最短路徑的特質

令n=輸入陣列nums的長度 = 圖中的節點總數

時間複雜度:

從start拜訪整張圖，每個節點至多訪問一次，每個節點至少有兩條向外的指向邊。

最後一定能找到最短路徑(因為最差情況就是每次都往右走，總有一步會走到終點)。

拜訪整張圖所需時間為O(n)。

空間複雜度:

從起點開始BFS逐層搜索，每一層拜訪彼此相差一步的節點，最大長度為O(n)。

關鍵知識點

在無權重的圖 或者 權重都相等的圖中尋找最短路徑，那很自然就會想到BFS先天具有點播源擴散的特質，也因此具有最短路徑的搜索性質。

我們只要從Node 0 開始進行BFS廣度優先搜尋，一層一層往外拜訪，

當拜訪到Node n-1的時候，

當下的步數 = 最短路徑長度 = 從起點到終點的最小跳躍次數。

在這邊也整理了一些常用的BFS、DFS圖論中的應用場景，提供讀者作為參考。

Reference:

[1] Jump Game IV_Python O(n) by BFS with natural shortest path itself [w/ Comment]