Drehen der Box

1861. Drehen der Box

Schwierigkeit:Mittel

Themen:Array, Zwei Zeiger, Matrix

Sie erhalten eine mxn-Matrix von Zeichenboxen, die eine Seitenansicht einer Box darstellt. Jede Zelle der Box ist eine der folgenden:

• Ein Stein „#“
• Ein stationäres Hindernis '*'
• Leeres '.'

Die Kiste wird um 90 Grad im Uhrzeigersinn gedreht, wodurch einige der Steine ​​aufgrund der Schwerkraft herunterfallen. Jeder Stein fällt herunter, bis er auf einem Hindernis, einem anderen Stein oder dem Boden der Kiste landet. Die Schwerkraft hat keinen Einflussauf die Positionen der Hindernisse und die Trägheit durch die Drehung der Kiste hat keinen Einflussauf die horizontalen Positionen der Steine.

Es ist garantiert, dass jeder Stein in der Kiste auf einem Hindernis, einem anderen Stein oder dem Boden der Kiste aufliegt.

Gib eine n x m-Matrix zurück, die die Box nach der oben beschriebenen Drehung darstellt.

Beispiel 1:

• Eingabe: box = [["#",".","#"]]
• Ausgabe: [["."], ["#"], ["#"]]

Beispiel 2:

• Eingabe: box = [["#",".","","."], ["#","#","","."] ]
• Ausgabe: [["#","."], ["#","#"], ["",""], [".",". "]]

Beispiel 3:

• Eingabe: box = [["#","#","",".","","."], ["#","#", „#“, „*“, „.“, „.“], [“#“, „#“, „#“, „.“, „#“, „.“]]
• Ausgabe: [[".","#","#"], [".","#","#"], ["#","#"," "], ["#","","."], ["#",".","*"], ["#",".","."]]

Einschränkungen:

• m == box.length
• n == box[i].length
• 1 <= m, n <= 500
• box[i][j] ist entweder '#', '*' oder '.'.

Hinweis:

1. Drehen Sie die Box mithilfe der Beziehung rotatedBox[i][j] = box[m - 1 - j][i].
2. Beginnen Sie mit der Iteration am unteren Rand der Box und prüfen Sie für jede leere Zelle, ob sich darüber ein Stein befindet, zwischen dem sich keine Hindernisse befinden.

Lösung:

Wir müssen ein paar klare Schritte befolgen:

1. Drehen Sie die Box: Wir drehen zunächst die Matrix um 90 Grad im Uhrzeigersinn. Die gedrehte Matrix hat n Zeilen und m Spalten, wobei n die Anzahl der Spalten im Originalfeld und m die Anzahl der Zeilen ist.

2. Schwerkrafteffekt: Nach der Drehung müssen wir den Effekt der Schwerkraft simulieren. Das bedeutet, dass alle Steine ​​('#') auf das Ende ihrer neuen Spalte „fallen“ sollten und erst anhalten, wenn sie auf ein Hindernis ('*') oder einen anderen Stein ('#') stoßen.

Ansatz:

1. Rotation: Nach der Rotation wird das Element an Position [i][j] in der ursprünglichen Matrix an Position [j][m-1-i] in der gedrehten Matrix platziert Matrix.

2. Schwerkraftsimulation: Wir müssen jede Spalte von unten nach oben bearbeiten. Wenn ein Stein ('#') vorhanden ist, fällt er herunter, bis er ein Hindernis oder den Boden erreicht. Wenn die Zelle leer ist ('.'), kann sie einen Stein enthalten.

Schritt-für-Schritt-Erklärung:

1. Erstellen Sie eine neue Matrix für die gedrehte Box.
2. Durchlaufen Sie jede Spalte der gedrehten Matrix (nach der Drehung).
3. Simulieren Sie die Schwerkraft für jede Säule, indem Sie unten beginnen und sich nach oben bewegen. Platzieren Sie Steine ​​('#') so weit unten wie möglich und lassen Sie Hindernisse ('*') an Ort und Stelle.
4. Gibt die endgültige gedrehte Matrix zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 1861. Drehen der Box

<?php
function rotateTheBox($box) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$box = [
    ["#", ".", "#"],
];
print_r(rotateTheBox($box));

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];
print_r(rotateTheBox($box));

$box = [
    ["#", "#", "*", ".", "*", "."],
    ["#", "#", "#", "*", ".", "."],
    ["#", "#", "#", ".", "#", "."],
];
print_r(rotateTheBox($box));
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Schwerkraft simulieren</strong>:</p>

<ul>
<li>Durchlaufen Sie jede Reihe von rechts nach links. Verwenden Sie einen Zeiger (emptySlot), um zu verfolgen, wo der nächste Stein fallen soll.</li>
<li>Wenn ein Stein (#) angetroffen wird, verschieben Sie ihn in den emptySlot und dekrementieren Sie dann emptySlot.</li>
<li>Wenn ein Hindernis (*) auftritt, setzen Sie emptySlot auf die Position direkt vor dem Hindernis zurück.</li>
</ul>
</li>
<li>
<p><strong>Matrix drehen</strong>:</p>

<ul>
<li>Erstellen Sie eine neue Matrix, in der das Element bei [i][j] in der gedrehten Box aus [m - 1 - j][i] der Originalbox entnommen wird.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispielausgabe
</h3>

<h4>
  
  
  Eingang:
</h4>



<pre class="brush:php;toolbar:false">$box = [
    ["#", ".", "#"],
];

Ausgabe:

[
    [".",],
    ["#",],
    ["#",],
]

Eingang:

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];

Ausgabe:

[
    ["#", "."],
    ["#", "#"],
    ["*", "*"],
    [".", "."],
]

Zeitkomplexität

1. Schwerkraftsimulation: O(m x n), während wir jedes Element in der Matrix durchlaufen.
2. Rotation: O(m x n), während wir die gedrehte Matrix erstellen.

Gesamt: O(m x n).

Weltraumkomplexität

• O(m x n) für die gedrehte Matrix.

Diese Lösung ist effizient und berücksichtigt die Randbedingungen des Problems.

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 vonDrehen der Box. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!