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

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

難易度: 中

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

行列の次元を表す 2 つの整数 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. まず、-1 で満たされた m x n 行列を生成します。
2. 方向ベクトル ⟨di, dj⟩ を使用して、(i, j) の行列内を移動します。 (i, j) では、現在の方向に進み続けることができるかどうかを判断する必要があります。
3. 先に進めない場合は、方向ベクトルを時計回りに 90 度回転してください。

解決策:

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

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

1. 行列の初期化: まず、-1 で初期化された m x n 行列を作成します。
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 は、右、下、左、上の 4 方向の動きを管理します。
   • インデックス dirIndex は現在の方向を追跡します。一方向に移動した後、次の位置を計算し、それが有効かどうかを確認します。そうでない場合は、方向を変更します。

3. リンクリストトラバーサル:

   • リンクされたリストのノードをたどって、スパイラル順序に従って行列に値を 1 つずつ配置します。

4. 境界と方向の変更:

   • 無効な位置 (範囲外またはすでに埋められている) に遭遇した場合、方向を 90 度回転します (つまり、方向ベクトルを変更します)。

時間計算量:

• すべてのセルを 1 回走査するため、行列を埋めるには O(m * n) かかります。したがって、時間計算量は O(m * n) であり、制約を考慮すると効率的です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がスパイラル マトリックス IVの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。