Faire pivoter la boîte

1861. Faire pivoter la boîte

Difficulté :Moyen

Sujets : Tableau, deux pointeurs, matrice

Vous recevez une matrice m x n de boîte de caractères représentant une vue latérale d'une boîte. Chaque cellule de la boîte est l'une des suivantes :

• Une pierre '#'
• Un obstacle fixe '*'
• Vide '.'

La boîte tourne 90 degrés dans le sens des aiguilles d'une montre, ce qui fait tomber certaines pierres à cause de la gravité. Chaque pierre tombe jusqu'à ce qu'elle atterrisse sur un obstacle, une autre pierre ou le fond de la boîte. La gravité n'affecte pas la position des obstacles, et l'inertie de la rotation de la boîte n'affecte pas la position horizontale des pierres.

Il est garanti que chaque pierre de la boîte repose sur un obstacle, une autre pierre ou le fond de la boîte.

Renvoyer une matrice n x m représentant la boîte après la rotation décrite ci-dessus.

Exemple 1 :

• Saisie : case = [["#",".","#"]]
• Sortie : [["."], ["#"], ["#"]]

Exemple 2 :

• Saisie : case = [["#",".","","."], ["#","#","","."] ]
• Sortie : [["#","."], ["#","#"], ["",""], [".",". "]]

Exemple 3 :

• Saisie : case = [["#","#","",".","","."], ["#","#", "#","*",".","."], ["#","#","#",".","#","."]]
• Sortie : [[".","#","#"], [".","#","#"], ["#","#"," "], ["#","","."], ["#",".","*"], ["#",".","."]]

Contraintes :

• m == box.length
• n == boîte[i].longueur
• 1 <= m, n <= 500
• box[i][j] est soit '#', '*' ou '.'.

Indice :

1. Faites pivoter la boîte en utilisant la relation rotatedBox[i][j] = box[m - 1 - j][i].
2. Commencez à itérer à partir du bas de la boîte et pour chaque cellule vide, vérifiez s'il y a une pierre au-dessus sans obstacle entre elles.

Solution :

Nous devons suivre quelques étapes distinctes :

1. Faire pivoter la boîte : Nous faisons d'abord pivoter la matrice de 90 degrés dans le sens des aiguilles d'une montre. La matrice pivotée aura n lignes et m colonnes, où n est le nombre de colonnes dans la boîte d'origine et m est le nombre de lignes.

2. Effet de gravité : Après la rotation, nous devons simuler l'effet de la gravité. Cela signifie que toutes les pierres ('#') doivent "tomber" au bas de leur nouvelle colonne, en s'arrêtant uniquement lorsqu'elles rencontrent un obstacle ('*') ou une autre pierre ('#').

Approche:

1. Rotation : Après la rotation, l'élément en position [i][j] dans la matrice d'origine sera placé en position [j][m-1-i] dans la matrice pivotée. matrice.

2. Simulation gravitationnelle : Nous devons traiter chaque colonne de bas en haut. S'il y a une pierre (« # »), elle tombera jusqu'à atteindre un obstacle ou le fond. Si la cellule est vide ('.'), elle peut contenir une pierre.

Explication étape par étape :

1. Créez une nouvelle matrice pour la boîte pivotée.
2. Parcourir chaque colonne de la matrice pivotée (après rotation).
3. Simulez la gravité pour chaque colonne en commençant par le bas et en remontant. Placez les pierres ('#') le plus bas possible en laissant les obstacles ('*') en place.
4. Renvoyer la matrice pivotée finale.

Implémentons cette solution en PHP : 1861. Faire pivoter la boîte

<?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>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Simuler la gravité</strong> :</p>

<ul>
<li>Parcourez chaque rangée de droite à gauche. Utilisez un pointeur (emptySlot) pour savoir où la prochaine pierre devrait tomber.</li>
<li>Si une pierre (#) est rencontrée, déplacez-la vers le emptySlot, puis décrémentez emptySlot.</li>
<li>Si un obstacle (*) est rencontré, réinitialisez emptySlot à la position juste avant l'obstacle.</li>
</ul>
</li>
<li>
<p><strong>Faire pivoter la matrice</strong> :</p>

<ul>
<li>Créez une nouvelle matrice où l'élément en [i][j] dans la boîte pivotée est extrait de [m - 1 - j][i] de la boîte d'origine.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple de sortie
</h3>

<h4>
  
  
  Saisir:
</h4>



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

Sortir:

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

Saisir:

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

Sortir:

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

Complexité temporelle

1. Simulation de la gravité : O(m x n), lorsque nous parcourons chaque élément de la matrice.
2. Rotation : O(m x n), lorsque nous créons la matrice pivotée.

Total : O(m x n).

Complexité spatiale

• O(m x n) pour la matrice pivotée.

Cette solution est efficace et respecte les contraintes du problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!