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
提示：
- 首先，生成一个 m x n 矩阵，填充 -1s。
- 借助方向向量 ⟨di, dj⟩ 在矩阵 (i, j) 处导航。在(i,j)处，你需要决定是否可以继续沿着当前的方向前进。
- 如果无法继续前进，请将方向向量顺时针旋转 90 度。
解决方案：
我们将模拟 m x n 矩阵的螺旋遍历，并用链表中的值填充它。其余没有对应链表值的位置将用-1填充。
解决方案的结构如下：
-
矩阵初始化：我们首先创建一个 m x n 矩阵，初始化为 -1。
-
方向向量：可以使用循环向右、向下、向左和向上方向的方向向量来控制螺旋运动。这确保我们以螺旋方式遍历矩阵。
-
链表迭代：我们遍历链表，将值按螺旋顺序放入矩阵中。
-
边界处理：我们检查是否已到达边界或遇到已填充的单元格。如果是这样，我们改变方向（顺时针）。
让我们用 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。
-
螺旋运动：
- 方向向量 dirs 管理四个方向的移动：右、下、左、上。
- 索引 dirIndex 跟踪当前方向。朝一个方向移动后，我们计算下一个位置并检查它是否有效。如果没有，我们就改变方向。
-
链表遍历:
- 我们遍历链表节点，将值按照螺旋顺序一一放入矩阵中。
-
边界和方向变化:
- 当我们遇到无效位置（出界或已填充）时，我们将方向旋转 90 度（即改变方向向量）。
时间复杂度：
- 填充矩阵需要 O(m * n)，因为我们遍历每个单元格一次。因此，时间复杂度为 O(m * n)，在给定约束的情况下，这是有效的。
联系链接
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
以上是螺旋矩阵 IV的详细内容。更多信息请关注PHP中文网其他相关文章！
