386. Numéros lexicographiques
Difficulté :Moyen
Sujets : Recherche en profondeur d'abord, Trie
Étant donné un entier n, renvoie tous les nombres de la plage [1, n] triés par ordre lexicographique.
Vous devez écrire un algorithme qui s'exécute en temps O(n) et utilise un espace supplémentaire O(1).
Exemple 1 :
Exemple 2 :
Contraintes :
Solution :
Nous pouvons l'aborder en utilisant une stratégie de type Depth-First Search (DFS).
Implémentons cette solution en PHP : 386. Numéros lexicographiques
<?php /** * @param Integer $n * @return Integer[] */ function lexicalOrder($n) { ... ... ... /** * go to ./solution.php */ } // Example usage $n1 = 13; print_r(lexicalOrder($n1)); $n2 = 2; print_r(lexicalOrder($n2)); ?> <h3> Explication: </h3> <ul> <li>Nous maintenons un numéro actuel et essayons d'aller le plus loin possible en le multipliant par 10 pour obtenir le numéro lexicographique suivant.</li> <li>Quand on ne peut pas multiplier (car il dépasserait n), on incrémente le nombre. Nous traitons les cas où l'incrément mène à des nombres comme 20, 30, etc., en vérifiant les zéros à droite et en ajustant le nombre actuel en conséquence.</li> <li>La boucle continue jusqu'à ce que nous ayons ajouté tous les nombres jusqu'à n dans l'ordre lexicographique.</li> </ul> <h3> Exemple de procédure pas à pas : </h3> <h4> Entrée : n = 13 </h4> <ol> <li>Commencez à 1.</li> <li>Multipliez 1 par 10 -> 10.</li> <li>Ajoutez 11, 12, 13.</li> <li>Retournez à 2 et continuez à incrémenter jusqu'à 9.</li> </ol> <h4> Sortir: </h4> <pre class="brush:php;toolbar:false">[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2]
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 :
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!