螺旋矩阵 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中文网其他相关文章！