🎨自動填補 迴旋矩陣IV_Spiral Matrix IV_Leetcode 2326

engin akyurt on Unsplash

題目敘述 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)

Reference

[1] Spiral Matrix IV - LeetCode