一魚多吃 用BFS來列出拜訪路徑 Diagonal Traverse II_Leetcode#1424

Lili Popper on Unsplash

題目敘述

題目會給我們一個不規則排列的二維陣列，要求我們列出從起點出發，走次對角線方向，由左下到右上逐層拜訪的路徑。

題目的原文敘述

測試範例

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

約束條件

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= sum(nums[i].length) <= 10^5
• 1 <= nums[i][j] <= 10^5

演算法

除了傳統的次對角線方向總合當作鍵值的字典演算法之外，還有一個高效率的BFS演算法。

我們可以這樣想，把左上角(0, 0)這個座標當作起點。依循BFS的原則，往右下角擴散。

假設當下拜訪到的座標為(x, y)

當現在位在最左邊的column時，把下方的鄰居(x, y+1)推入BFS queue。

當現在不在最右邊的column時，把右邊的鄰居(x+1, y)推入BFS queue。

接著，把拜訪到的元素值記錄下來，就是最終答案。

從起點 左上角的1出發

拜訪1 的時侯，加入鄰居 4, 2

拜訪4 的時侯，加入鄰居 7, 5

拜訪2 的時侯，加入鄰居 3

拜訪7 的時侯，加入鄰居 8

拜訪5 的時侯，加入鄰居 6

拜訪3 已經抵達最右邊的column

拜訪8 的時侯，加入鄰居 9

拜訪6 已經抵達最右邊的column

拜訪9 已經抵達最右邊的column

最後，整個次對角線的拜訪路徑就是

1, 4, 2, 7, 5, 3, 8, 6, 9

程式碼

class Solution:
　def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
　　
　　# Height of input 2D array
　　H = len(nums)

　　# 2D (x, y) coordination of each grid
　　traversal_q = deque( [(0, 0)] )

　　# record of traversal path
　　record = []

　　# Launch BFS traversal from staring point (0, 0)
　　while traversal_q:
　　　
　　　## Add current grid to record of traversal path
　　　x, y = traversal_q.popleft()
　　　record.append( nums[y][x] )

　　　## Add neighbor below on the leftmost column
　　　if x == 0 and ( (y + 1) < H ):
　　　　traversal_q.append( (x, y+1) )
　　　
　　　
　　　## Add neighbor on right hand side
　　　
　　　# Get width of current row dynamically
　　　cur_width = len( nums[y] )

　　　if x + 1 < cur_width:
　　　　traversal_q.append( (x+1, y) )

　　return record

關鍵知識點

本題目切忌先入為主，把題目當成方陣或矩陣。
這題的輸入其實是不規則的二維陣列。

可以想到BFS演算法，把矩陣的每個格子點視為一個節點，相鄰的節點有一條邊相連。

我們可以這樣想，把左上角(0, 0)這個座標當作起點。依循BFS廣度優先的原則，往右下角擴散。

最後整個BFS拜訪順序的軌跡，就是答案。

Reference:

[1] Python O(HW) on BFS and neighbor growing [w/ Visualization] - Diagonal Traverse II - LeetCode