題目敘述 2326. Spiral Matrix IV
題目給定一個Linked list和對應的矩陣高度m、寬度n。
請依照順時針的拜訪順序，從左上角出發，依照次序把Linked List的內容填到矩陣裡。
如果有剩餘不足的空位，就填補-1。
最後將填補好的矩陣返回作為答案。
測試範例
Example 1:
Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.
Example 2:
Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.
約束條件
Constraints:
1 <= m, n <= 10^5
高度、寬度都介於1~十萬之間。
1 <= m * n <= 10^5
格子點總數介於1~十萬之間。
- The number of nodes in the list is in the range
[1, m * n].
Linked list長度介於 1~格子點總數之間。
0 <= Node.val <= 1000
所有節點值都介於0~1000之間。
演算法 模擬順時針迴旋路徑
先建立一個高度m 寬度n的二維陣列，陣列元素值都初始化成-1。
接著，依照題意進行順時針迴旋路徑的模擬，
依照順序把Linked List的內容填到對應的陣列位置上。
最後，回傳二維陣列作為答案即可。
Python程式碼 模擬順時針迴旋路徑
class Solution:
def spiralMatrix(self, m: int, n: int, head: "ListNode") -> List[List[int]]:
# Store the east, south, west, north movements in a matrix.
x, y = 0, 0
# Go east on starting point
direction = 0
# Direction vector:
# Easr , South , West , North
vector = [[1, 0], [0, 1], [-1, 0], [0, -1]]
res = [[-1 for _ in range(n)] for _ in range(m)]
# Keep filling array cell one by one on spiral path
while head is not None:
res[y][x] = head.val
newx = x + vector[direction][0]
newy = y + vector[direction][1]
# If we meet an edge or an already filled cell, change the direction clockwise.
if ( newy < 0 or newx < 0 or newy >= m or newx >= n or res[newy][newx] != -1):
direction = (direction + 1) % 4
x += vector[direction][0]
y += vector[direction][1]
head = head.next
return res
Go程式碼 模擬順時針迴旋路徑
func spiralMatrix(m int, n int, head *ListNode) [][]int {
result := make( [][]int, m)
// Create 2D Array with height m * width n
for y := 0 ; y < m ; y++{
result[y] = make( []int, n)
for x := 0 ; x < n ; x++{
result[y][x] = -1
}
}
// Moving Vector
// East , South , West , North
vector := [][]int{ {1, 0}, {0, 1}, {-1, 0}, {0, -1}}
// Direction
direction := 0
// Starting point
x, y := 0, 0
// Keep moving in spiral path, filling with node value in linked list
for head != nil{
result[y][x] = head.Val
// Turn right if next position is edge or out of boundary.
nx, ny := x + vector[direction][0], y + vector[direction][1]
if (nx >= n) || (nx < 0) || (ny >= m) || (ny < 0) || ( result[ny][nx] != -1 ) {
direction = (direction + 1) % 4
}
// Go to next array cell in spiral path
x, y = x + vector[direction][0], y + vector[direction][1]
// Go to next node of linked list
head = head.Next
}
// Return 2D Array
return result
}
複雜度分析
時間複雜度 O(mn)
建立二維陣列，依序拜訪每個格子點一次，總共耗時O(m * n)
空間複雜度 O(mn)
建立二維陣列，總共所需空間為O(m * n)
