. Échange maximum

670. Échange maximum

Difficulté :Moyen

Sujets : Mathématiques, gourmand

Vous recevez un nombre entier. Vous pouvez échanger deux chiffres au maximum une fois pour obtenir le nombre de valeur maximale.

Renvoyer le nombre de valeur maximale que vous pouvez obtenir.

Exemple 1 :

• Entrée : num = 2736
• Sortie : 7236
• Explication : Intervertissez le chiffre 2 et le chiffre 7.

Exemple 2 :

• Entrée : num = 9973
• Sortie : 9973
• Explication :Pas d'échange.

Contraintes :

• 0 <= num <= 10⁸

Solution :

On peut suivre une approche gourmande. Voici une explication étape par étape et la solution :

Approche:

1. Convertir le nombre en tableau : étant donné que les chiffres doivent être échangés, la conversion du nombre en un tableau de chiffres facilite l'accès et la manipulation des chiffres individuels.
2. Suivez l'occurrence la plus à droite de chaque chiffre : stockez la position la plus à droite de chaque chiffre (0-9) dans un tableau.
3. Trouvez la meilleure opportunité d'échange : parcourez les chiffres du numéro de gauche à droite et pour chaque chiffre, vérifiez s'il y a un chiffre supérieur qui apparaît plus tard. Si c'est le cas, échangez-les pour maximiser le nombre.
4. Effectuez l'échange et la rupture : Dès que l'échange optimal est trouvé, effectuez l'échange et rompez la boucle.
5. Convertir le tableau en nombre : après l'échange, reconvertissez le tableau de chiffres en nombre et renvoyez-le.

Implémentons cette solution en PHP : 670. Échange maximum

  
  
  Explication:




Étape 1 : strval($num) convertit l'entier en chaîne et str_split($numStr) le divise en un tableau de chiffres.

Étape 2 : Le dernier tableau garde la trace de l'index le plus à droite de chaque chiffre de 0 à 9.

Étape 3 : Nous parcourons chaque chiffre et recherchons un chiffre plus grand qui peut être échangé.

Étape 4 : Si un chiffre plus grand approprié est trouvé (qui apparaît plus tard dans le numéro), les chiffres sont échangés.

Étape 5 : Le tableau modifié est reconverti en chaîne puis en entier à l'aide de intval().



  
  
  Complexité:




Complexité temporelle : O(n), où n est le nombre de chiffres dans num. En effet, nous effectuons un passage par le numéro pour remplir le dernier tableau et un autre passage pour trouver l'échange optimal.

Complexité spatiale : O(1) (en ignorant la taille d'entrée) puisque le dernier tableau est fixé avec 10 éléments.


Cette solution trouve efficacement la valeur maximale en échangeant les chiffres une seule fois, selon les besoins.

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!