. Numéros lexicographiques

Mary-Kate Olsen
Libérer: 2024-09-21 12:16:09
original
529 Les gens l'ont consulté

. Lexicographical Numbers

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 :

  • Entrée : n = 13
  • Sortie : [1,10,11,12,13,2,3,4,5,6,7,8,9]

Exemple 2 :

  • Entrée : n = 2
  • Sortie : 4
  • Explication : [1,2]

Contraintes :

  • 1 <= n <= 5*104

Solution :

Nous pouvons l'aborder en utilisant une stratégie de type Depth-First Search (DFS).

Informations clés :

  • L'ordre lexicographique est essentiellement un parcours de pré-ordre sur un arbre virtuel n-aire, où le nœud racine commence à 1 et chaque nœud a jusqu'à 9 enfants, qui sont formés en ajoutant des chiffres (0 à 9).
  • Nous pouvons simuler ce parcours de précommande en commençant par 1 et en ajoutant des nombres à plusieurs reprises, en nous assurant de ne pas dépasser le n donné.

Approche:

  1. Commencez par le chiffre 1 et essayez d'aller plus loin en multipliant par 10 (c'est-à-dire le nombre lexicographique suivant avec le chiffre suivant).
  2. S'il n'est pas possible d'aller plus loin (multiplier par 10) (c'est-à-dire qu'il dépasse n), incrémentez le nombre en vous assurant qu'il n'introduit pas de saut invalide entre les dizaines (c'est-à-dire en passant de 19 à 20).
  3. Nous revenons en arrière lorsque le numéro actuel ne peut pas être prolongé davantage et passons au prochain numéro valide.
  4. Continuez jusqu'à ce que tous les nombres jusqu'à n soient traités.

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]
Copier après la connexion

Entrée : n = 2

  1. Commencez à 1.
  2. Passer à 2.

Sortir:

[1, 2]
Copier après la connexion

Complexité temporelle :

  • O(n) puisque chaque nombre de 1 à n est traité exactement une fois.

Complexité spatiale :

  • O(1) un espace supplémentaire est utilisé (sans tenir compte de l'espace utilisé pour le tableau de résultats).

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!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal