Matrice spirale IV

2326. Matrice spirale IV

Difficulté :Moyen

Sujets : Tableau, liste chaînée, matrice, simulation

On vous donne deux entiers m et n, qui représentent les dimensions d'une matrice.

Vous recevez également la tête d'une liste chaînée d'entiers.

Générer une matrice m x n qui contient les entiers de la liste chaînée présentée dans l'ordre spirale (dans le sens des aiguilles d'une montre), en partant du haut gauche de la matrice . S'il reste des espaces vides, remplissez-les avec -1.

Renvoyer la matrice générée.

Exemple 1 :

• Entrée : m = 3, n = 5, tête = [3,0,2,6,8,1,7,9,4,2,5,5,0]
• Sortie : [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
• Explication :
  • Le diagramme ci-dessus montre comment les valeurs sont imprimées dans la matrice.
  • Notez que les espaces restants dans la matrice sont remplis avec -1.

Exemple 2 :

• Entrée : m = 1, n = 4, tête = [0,1,2]
• Sortie : [[0,1,2,-1]]
• Explication :
  • Le diagramme ci-dessus montre comment les valeurs sont imprimées de gauche à droite dans la matrice.
  • Le dernier espace de la matrice est défini sur -1.

Exemple 3 :

• Entrée : coût = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Sortie : 10

Contraintes :

• 1 <= m, n <= 10⁵
• 1 <= m, n <= 10⁵
• Le nombre de nœuds dans la liste est compris entre [1, m * n].
• 0 <= Node.val <= 1000

Indice :

1. Tout d'abord, générez une matrice m x n remplie de -1.
2. Naviguez dans la matrice en (i, j) à l'aide d'un vecteur directeur ⟨di, dj⟩. En (i, j), vous devez décider si vous pouvez continuer dans la direction actuelle.
3. Si vous ne pouvez pas continuer, faites pivoter le vecteur de direction de 90 degrés dans le sens des aiguilles d'une montre.

Solution :

Nous allons simuler un parcours en spirale d'une matrice m x n, en la remplissant avec les valeurs d'une liste chaînée. Les positions restantes qui n'ont pas de valeurs de liste chaînées correspondantes seront remplies avec -1.

Voici comment la solution est structurée :

1. Initialisation de la matrice : On crée d'abord une matrice m x n initialisée avec -1.
2. Vecteurs de direction : Le mouvement en spirale peut être contrôlé à l'aide d'un vecteur de direction qui parcourt les directions droite, bas, gauche et haut. Cela garantit que nous parcourons la matrice en spirale.
3. Itération de liste chaînée : nous parcourons la liste chaînée, en plaçant les valeurs dans la matrice dans l'ordre en spirale.
4. Gestion des limites : Nous vérifions si nous avons atteint la limite ou rencontré une cellule déjà remplie. Si c'est le cas, on change de direction (dans le sens des aiguilles d'une montre).

Implémentons cette solution en PHP : 2326. Matrice spirale IV

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);
?>





  
  
  Explication:



Initialisation de la matrice : La matrice est initialisée avec -1 afin que tous les espaces non remplis restent -1 par défaut.

Mouvement en spirale :


Le vecteur de direction dirs gère le mouvement dans quatre directions : droite, bas, gauche et haut.
L'index dirIndex garde une trace de la direction actuelle. Après avoir parcouru une direction, nous calculons la position suivante et vérifions si elle est valide. Sinon, on change de direction.



Parcours de liste liée :


Nous parcourons les nœuds de la liste chaînée, en plaçant les valeurs dans la matrice une par une, en suivant l'ordre en spirale.



Changement de limite et de direction :


Lorsque nous rencontrons une position invalide (hors limites ou déjà remplie), nous faisons pivoter la direction de 90 degrés (c'est-à-dire changeons le vecteur de direction).





  
  
  Complexité temporelle :



Remplir la matrice prend O(m * n) car nous parcourons chaque cellule une fois. Par conséquent, la complexité temporelle est O(m * n), ce qui est efficace compte tenu des contraintes.


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!