螺旋矩陣 IV

2326。螺旋矩陣 IV

難度：中

主題：陣列、鍊錶、矩陣、模擬

給定兩個整數 m 和 n，它們代表矩陣的維度。

您還將獲得一個整數鍊錶的頭。

產生 m x n 矩陣，其中包含以 螺旋 順序（順時針）呈現的鍊錶中的整數，從矩陣的 左上角 開始。如果還有剩餘的空格，則用-1填滿。

傳回產生的矩陣.

範例1：

• 輸入： m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
• 輸出： [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
• 說明：
  • 上圖顯示如何在矩陣中列印值。
  • 請注意，矩陣中剩餘的空間以-1填滿。

範例2：

• 輸入： m = 1, n = 4, head = [0,1,2]
• 輸出： [[0,1,2,-1]]
• 說明：
  • 上圖顯示如何在矩陣中從左到右列印值。
  • 矩陣中的最後一個空格設定為-1。

範例 3：

• 輸入： 成本= [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 輸出： 10

約束：

• 1 5
• 1 5
• 清單中的節點數量在 [1, m * n] 範圍內。
• 0

提示：

1. 首先，產生一個 m x n 矩陣，填入 -1s。
2. 藉助方向向量 ⟨di, dj⟩ 在矩陣 (i, j) 處導航。在(i,j)處，你需要決定是否可以繼續沿著目前的方向前進。
3. 如果無法繼續前進，請將方向向量順時針旋轉 90 度。

解：

我們將模擬 m x n 矩陣的螺旋遍歷，並用鍊錶中的值填滿它。其餘沒有對應鍊錶值的位置將以-1填滿。

解的架構如下：

1. 矩陣初始化：我們先建立一個 m x n 矩陣，初始化為 -1。
2. 方向向量：可以使用循環向右、向下、向左和向上方向的方向向量來控制螺旋運動。這確保我們以螺旋方式遍歷矩陣。
3. 鍊錶迭代：我們遍歷鍊錶，將數值以螺旋順序放入矩陣中。
4. 邊界處理：我們檢查是否已到達邊界或遇到已填滿的儲存格。如果是這樣，我們改變方向（順時針）。

讓我們用 PHP 實作這個解：2326。螺旋矩陣 IV

<?php
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
/**
 * @param Integer $m
 * @param Integer $n
 * @param ListNode $head
 * @return Integer[][]
 */
function spiralMatrix($m, $n, $head) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to print the matrix (for debugging)
function printMatrix($matrix) {
    foreach ($matrix as $row) {
        echo implode(" ", $row) . "\n";
    }
}

// Example usage:
// Create the linked list: [3,0,2,6,8,1,7,9,4,2,5,5,0]
$head = new ListNode(3);
$head->next = new ListNode(0);
$head->next->next = new ListNode(2);
$head->next->next->next = new ListNode(6);
$head->next->next->next->next = new ListNode(8);
$head->next->next->next->next->next = new ListNode(1);
$head->next->next->next->next->next->next = new ListNode(7);
$head->next->next->next->next->next->next->next = new ListNode(9);
$head->next->next->next->next->next->next->next->next = new ListNode(4);
$head->next->next->next->next->next->next->next->next->next = new ListNode(2);
$head->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next->next = new ListNode(0);

$m = 3;
$n = 5;

$matrix = spiralMatrix($m, $n, $head);
printMatrix($matrix);
?>

解釋：

1. 矩陣初始化：矩陣初始化為-1，因此任何未填滿的空間預設保持-1。

2. 螺旋運動：

   • 方向向量 dirs 管理四個方向的移動：右、下、左、上。
   • 索引 dirIndex 追蹤當前方向。朝一個方向移動後，我們計算下一個位置並檢查它是否有效。如果沒有，我們就改變方向。

3. 鍊錶遍歷:

   • 我們遍歷鍊錶節點，將數值依照螺旋順序一一放入矩陣中。

4. 邊界與方向變化:

   • 當我們遇到無效位置（出界或已填滿）時，我們將方向旋轉 90 度（即改變方向向量）。

時間複雜度：

• 填滿矩陣需要 O(m * n)，因為我們遍歷每個單元格一次。因此，時間複雜度為 O(m * n)，在給定限制的情況下，這是有效的。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是螺旋矩陣 IV的詳細內容。更多資訊請關注PHP中文網其他相關文章！