🔗 🟡 2326. Spiral Matrix IV 1422

tags: Weekly Contest 300 陣列(Array) 矩陣(Matrix) 鏈結串列(Linked List) 模擬(Simulation)

題意

給定兩個整數 mm 和 nn，代表矩陣的維度。

另給定一個整數鏈結串列的頭節點 headhead。

生成一個 m×nm \times n 的矩陣，將鏈結串列中的整數以順時針螺旋順序填入，從矩陣的左上角開始。如果有剩餘的空位，則用 −1-1 填充。

返回生成的矩陣。

約束條件

  • 1≤m,n≤1051 \leq m, n \leq 10^5
  • 1≤m×n≤1051 \leq m \times n \leq 10^5
  • 鏈結串列中節點數目在 [1,m×n][1, m \times n] 之間
  • 0≤Node.val≤10000 \leq \text{Node.val} \leq 1000

思路：模擬(Simulation)

首先先忽略鏈結串列，只考慮矩陣的填入。根據題意，我們會由左上角開始，依次沿著右、下、左、上的方向填入數字，直到填滿矩陣。為此，我們可以定義四個方向，分別是 (0,1)(0, 1)、(1,0)(1, 0)、(0,−1)(0, -1)、(−1,0)(-1, 0)，分別代表右、下、左、上，並將它們儲存在 DIR 陣列中。

接著考慮轉向的問題，當我們遇到邊界或已經填過的數字時，就需要轉向。方向的次序和數量是固定的，因此我們可以使用 cdcd 來表示當前的方向，當轉向時，將 cdcd 加 11 並取餘數，即可得到新的方向。

根據題意，我們需要用 −1-1 填充矩陣中剩餘的空位。因此，我們可以初始化一個 m×nm \times n 的矩陣，並將所有位置先填入 −1-1。

在遍歷鏈結串列的過程中，我們將當前節點的值填入矩陣的當前位置，然後移動到下一個節點。接下來，計算下一步的位置 (nx,ny)(nx, ny)。如果下一步的位置超出了矩陣的邊界或者該位置已經被填充過了，我們則需要根據順時針方向轉向，並重新計算新的下一步位置。最後，更新當前的位置為新的 (nx,ny)(nx, ny)。這樣不斷重複，直到鏈結串列中的所有數字都被填入矩陣中。

複雜度分析

  • 時間複雜度：O(m×n)O(m \times n)，其中 mm 和 nn 分別是矩陣的行數和列數。在最壞的情況下，我們需要填滿整個矩陣，每個位置僅被訪問一次。
  • 空間複雜度：O(m×n)O(m \times n)，主要來自於用於存儲結果的矩陣 ans。此外，方向陣列和其他輔助變數所佔用的空間可以忽略不計，因此整體的空間需求與矩陣的大小成正比。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    """
        Simulation
        從左上角開始，按照順時針方向依次填入數字，遇到邊界或已經填過的數字就轉向
    """
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 定義四個方向
        ans = [[-1] * n for _ in range(m)] # 初始化答案矩陣
        x, y, cd = 0, 0, 0 # 初始化起始位置和方向
        while head is not None:
            ans[x][y] = head.val # 填入數字
            head = head.next # 移動到鏈接串列的下一個節點
            nx, ny = x + DIR[cd][0], y + DIR[cd][1] # 計算新位置
            # 若新位置超出邊界或已經填過，則需要轉向
            if (nx < 0 or nx >= m or ny < 0 or ny >= n or ans[nx][ny] != -1):
                cd = (cd + 1) % 4 # 轉向
                nx, ny = x + DIR[cd][0], y + DIR[cd][1] # 計算新位置
            x, y = nx, ny # 更新位置
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<pair<int, int>> DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int x = 0, y = 0, cd = 0, nx, ny;
        while (head != nullptr) {
            ans[x][y] = head->val;
            head = head->next;
            nx = x + DIR[cd].first;
            ny = y + DIR[cd].second;
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || ans[nx][ny] != -1) {
                cd = (cd + 1) % 4;
                nx = x + DIR[cd].first;
                ny = y + DIR[cd].second;
            }
            x = nx;
            y = ny;
        }
        return ans;
    }
};

寫在最後

Cover photo is remixed from @吃肥皂泡泡, thanks for their work!