スパイラルマトリックス IV-PHPチュートリアル-php.cn

スパイラルマトリックス IV

王林

リリース： 2024-09-10 06:35:02

オリジナル

1130 人が閲覧しました

2326。スパイラル・マトリックス IV

難易度: 中

トピック: 配列、リンクリスト、行列、シミュレーション

行列の次元を表す 2 つの整数 m と n が与えられます。

整数のリンクされたリストの先頭も与えられます。

行列の左上から開始して、スパイラル 順 (時計回り) で示されるリンクリスト内の整数を含む m x n 行列を生成します。。空きスペースが残っている場合は、-1 を埋めます。

生成された行列を返します。

例 1:

Spiral Matrix IV

入力: 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:

Spiral Matrix IV

入力: 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 行列を生成します。
方向ベクトル ⟨di, dj⟩ を使用して、(i, j) の行列内を移動します。 (i, j) では、現在の方向に進み続けることができるかどうかを判断する必要があります。
先に進めない場合は、方向ベクトルを時計回りに 90 度回転してください。

解決策:

m x n 行列のスパイラルトラバーサルをシミュレートし、リンクリストの値を行列に入力します。対応するリンクリストの値がない残りの位置は、-1 で埋められます。

ソリューションの構造は次のとおりです:

行列の初期化: まず、-1 で初期化された m x n 行列を作成します。
方向ベクトル: 螺旋の動きは、右、下、左、上方向を循環する方向ベクトルを使用して制御できます。これにより、行列を螺旋状に横断することが保証されます。
リンクリストの反復: リンクリストをたどって、値をスパイラル順に行列に配置します。
境界処理: 境界に到達したか、すでに塗りつぶされているセルに遭遇したかどうかを確認します。その場合は、方向を変更します (時計回り)。

このソリューションを 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 は、右、下、左、上の 4 方向の動きを管理します。
- インデックス dirIndex は現在の方向を追跡します。一方向に移動した後、次の位置を計算し、それが有効かどうかを確認します。そうでない場合は、方向を変更します。
リンクリストトラバーサル:
- リンクされたリストのノードをたどって、スパイラル順序に従って行列に値を 1 つずつ配置します。
境界と方向の変更:
- 無効な位置 (範囲外またはすでに埋められている) に遭遇した場合、方向を 90 度回転します (つまり、方向ベクトルを変更します)。