Trouver un moyen efficace

Salut les amis ! Aujourd'hui, j'ai résolu trois problèmes sur LeetCode : Unique Paths, Spiral Matrix et N-Queens. Passons en revue ces problèmes.

Problème de chemins uniques

On nous donne deux nombres, représentant le nombre de lignes et le nombre de colonnes. Notre tâche est de trouver le nombre total de chemins uniques pour atteindre la position (m-1,n-1) à partir de (0,0). Pour résoudre ce problème, nous pouvons suivre une approche récursive. Nous pouvons partir de (0,0) trouver récursivement les étapes pour voyager vers la droite et le bas jusqu'à ce que nous atteignions la position requise. Pour trouver des chemins totalement uniques, nous ajouterions les bonnes étapes aux étapes inférieures et les renverrions. Cependant, cette approche présente un petit problème : les solutions peuvent se répéter plusieurs fois. Pour surmonter ce problème, l’approche alternative consiste à utiliser la matrice DP. Nous créons une matrice DP avec le même nombre de lignes et de colonnes en entrée et nous initialisons toutes les positions de la matrice DP avec 1. Enfin, nous renvoyons la valeur dans la cellule latérale de la matrice DP sous forme de nombre total hors chemins uniques.

Matrice spirale

On nous donne une matrice et nous devons retourner une liste contenant les éléments de la matrice dans l'ordre en spirale. Pour résoudre ce problème, nous pouvons utiliser les limites d’indexation comme conditions pour exécuter une boucle. Nous parcourons de gauche à droite la matrice, nous pouvons en utiliser une pour la boucle. Ensuite, nous passons du coin supérieur droit au coin inférieur droit avec une autre boucle. Nous traversons du coin inférieur droit au coin inférieur gauche en utilisant une troisième boucle. Enfin, nous passons du coin inférieur gauche au coin supérieur gauche avec une quatrième boucle. De cette façon, nous utilisons quatre boucles différentes pour parcourir dans les quatre directions, en les contrôlant avec des limites d'indexation.

N-Reines

On nous donne un numéro d'entrée n, nous devons trouver le nombre de façons de placer n reines dans la matrice nxn de telle sorte que deux reines ne s'attaquent pas. Cela signifie qu'il n'y a pas deux reines dans la même ligne, colonne ou diagonale. Pour résoudre ce problème, nous pouvons utiliser les concepts de récursivité et de retour en arrière. Nous pouvons d’abord effectuer une récursion pour répéter le processus plusieurs fois. parce que nous devons trouver toutes les façons possibles de placer les reines. Un retour en arrière est effectué lorsque nous n'avons pas trouvé la bonne position pour placer la reine, nous pouvons alors remplacer « Q » par « . » et répéter le processus pour la position suivante.

Nous pouvons optimiser la solution ci-dessus en utilisant trois listes. Une liste consiste à garder une trace du nombre de lignes. disons que nous avons n lignes, nous placerons n zéros dans la liste et remplacerons le zéro respectif par un si cette ligne spécifique a une reine. Cela évitera des retours en arrière inutiles. De même, la deuxième liste concerne la diagonale inférieure et la troisième liste concerne la diagonale supérieure. Les deux listes diagonales contiennent 2n-1 éléments, tous initialement définis sur des zéros. Au fur et à mesure que nous parcourons la matrice pour placer les reines, nous mettons à jour la liste de lignes ou de diagonales respective en remplaçant 0 par 1 lorsque la reine est placée. Cela indique qu'aucune autre reine ne peut être placée dans cette diagonale ou cette rangée respective. De cette façon, cette approche fonctionne efficacement.

J'espère que mon expérience sera utile.

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!