Spiralmatrix IV

2326. Spiralmatrix IV

Schwierigkeit:Mittel

Themen: Array, verknüpfte Liste, Matrix, Simulation

Sie erhalten zwei ganze Zahlen m und n, die die Dimensionen einer Matrix darstellen.

Sie erhalten außerdem den Kopf einer verknüpften Liste von ganzen Zahlen.

Generieren Sie eine m x n-Matrix, die die ganzen Zahlen in der verknüpften Liste enthält, die in spiralförmiger Reihenfolge (im Uhrzeigersinn) dargestellt werden, beginnend oben links der Matrix . Wenn noch Leerzeichen vorhanden sind, füllen Sie diese mit -1.

Gib die generierte Matrix zurück.

Beispiel 1:

• Eingabe: m = 3, n = 5, Kopf = [3,0,2,6,8,1,7,9,4,2,5,5,0]
• Ausgabe: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
• Erklärung:
  • Das obige Diagramm zeigt, wie die Werte in der Matrix gedruckt werden.
  • Beachten Sie, dass die verbleibenden Leerzeichen in der Matrix mit -1 gefüllt werden.

Beispiel 2:

• Eingabe: m = 1, n = 4, Kopf = [0,1,2]
• Ausgabe: [[0,1,2,-1]]
• Erklärung:
  • Das Diagramm oben zeigt, wie die Werte von links nach rechts in der Matrix gedruckt werden.
  • Das letzte Leerzeichen in der Matrix wird auf -1 gesetzt.

Beispiel 3:

• Eingabe: Kosten = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Ausgabe: 10

Einschränkungen:

• 1 5
• 1 5
• Die Anzahl der Knoten in der Liste liegt im Bereich [1, m * n].
• 0

Hinweis:

1. Generieren Sie zunächst eine mit -1s gefüllte m x n-Matrix.
2. Navigieren Sie innerhalb der Matrix bei (i, j) mit Hilfe eines Richtungsvektors ⟨di, dj⟩. Bei (i, j) müssen Sie entscheiden, ob Sie in der aktuellen Richtung weitermachen können.
3. Wenn Sie nicht weitermachen können, drehen Sie den Richtungsvektor um 90 Grad im Uhrzeigersinn.

Lösung:

Wir simulieren eine spiralförmige Durchquerung einer m x n-Matrix und füllen sie mit Werten aus einer verknüpften Liste. Die verbleibenden Positionen, die keine entsprechenden verknüpften Listenwerte haben, werden mit -1 gefüllt.

So ist die Lösung aufgebaut:

1. Matrix-Initialisierung: Wir erstellen zunächst eine m x n-Matrix, die mit -1 initialisiert wird.
2. Richtungsvektoren: Die Spiralbewegung kann mithilfe eines Richtungsvektors gesteuert werden, der durch die Richtungen rechts, unten, links und oben wechselt. Dadurch wird sichergestellt, dass wir die Matrix spiralförmig durchlaufen.
3. Iteration verknüpfter Listen: Wir durchlaufen die verknüpfte Liste und platzieren Werte in spiralförmiger Reihenfolge in der Matrix.
4. Grenzbehandlung: Wir prüfen, ob wir die Grenze erreicht haben oder auf eine bereits gefüllte Zelle stoßen. Wenn ja, ändern wir die Richtung (im Uhrzeigersinn).

Lassen Sie uns diese Lösung in PHP implementieren: 2326. Spiralmatrix 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);
?>

Erläuterung:

1. Matrix-Initialisierung: Die Matrix wird mit -1 initialisiert, sodass alle nicht ausgefüllten Leerzeichen standardmäßig -1 bleiben.

2. Spiralbewegung:

   • Der Richtungsvektor dirs verwaltet Bewegungen in vier Richtungen: rechts, unten, links und oben.
   • Der Index dirIndex verfolgt die aktuelle Richtung. Nachdem wir uns in eine Richtung bewegt haben, berechnen wir die nächste Position und prüfen, ob sie gültig ist. Wenn nicht, ändern wir die Richtung.

3. Verknüpfte Listendurchquerung:

   • Wir durchlaufen die Knoten der verknüpften Liste und platzieren Werte nacheinander in der Matrix, wobei wir der Spiralreihenfolge folgen.

4. Grenz- und Richtungsänderung:

   • Wenn wir auf eine ungültige Position stoßen (außerhalb der Grenzen oder bereits besetzt), drehen wir die Richtung um 90 Grad (d. h. ändern den Richtungsvektor).

Zeitkomplexität:

• Das Füllen der Matrix erfordert O(m * n), da wir jede Zelle einmal durchlaufen. Daher beträgt die Zeitkomplexität O(m * n), was angesichts der Einschränkungen effizient ist.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonSpiralmatrix IV. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!