![. Find the Closest Palindrome](https://img.php.cn/upload/article/000/000/000/172453902498032.jpg)
564. Trouvez le palindrome le plus proche
Difficulté :Difficile
Sujets :Mathématiques, Cordes
Étant donné une chaîne n représentant un entier, renvoie _l'entier le plus proche (sans lui-même), qui est un palindrome-. S'il y a égalité, retournezle plus petit.
Le plus proche est défini comme la différence absolue minimisée entre deux entiers.
Exemple 1 :
- Entrée :n = "123"
- Sortie :"121"
Exemple 2 :
- Entrée :n = "1"
- Sortie :"0"
- Explication :0 et 2 sont les palindromes les plus proches mais on renvoie le plus petit qui est 0.
Contraintes :
- 1 <= n.longueur <= 18
- n se compose uniquement de chiffres.
- n n'a pas de zéros non significatifs.
- n représente un entier compris dans la plage [1, 1018- 1].
Indice :
- La force brute fonctionnera-t-elle pour résoudre ce problème ? Pensez à autre chose.
- Prenez quelques exemples comme 1234, 999,1000, etc. et vérifiez leurs palindromes les plus proches. Combien de cas différents sont possibles ?
- Devons-nous considérer uniquement la moitié gauche ou la moitié droite de la corde, ou les deux ?
- Essayez de trouver le palindrome le plus proche de ces nombres : 12932, 99800, 12120. Avez-vous observé quelque chose ?
Solution :
Nous nous concentrerons sur la création d'une fonction qui génère des candidats palindromes potentiels, puis sélectionne celui le plus proche du nombre saisi.
Approche de la solution :
Identifier les candidats au Palindrome:
- Miroir la première moitié du nombre pour former un palindrome.
- Considérez les cas extrêmes comme si tous les chiffres étaient 9, 100...001 ou 99...99.
- Générez des palindromes en modifiant le milieu du nombre vers le haut ou vers le bas de 1.
Calculez le palindrome le plus proche:
- Pour chaque candidat palindrome, calculez la différence absolue avec le nombre d'origine.
- Rendez le palindrome avec la plus petite différence. S'il y a égalité, rendez le plus petit palindrome.
Implémentons cette solution en PHP :564. Trouvez le palindrome le plus proche
Explication:
- générer Palindrome($firstHalf, $isOddLength) :
- Cette fonction d'assistance crée un palindrome en reflétant la première moitié du nombre.
Copier après la connexion
Étuis Edge:
- Les palindromes générés à partir de nombres comme 100...001 ou 99...99 sont traités en vérifiant explicitement ces cas.
Logique principale:
- Nous calculons les palindromes possibles puis trouvons le plus proche en comparant les différences absolues.
Cette solution réduit efficacement les candidats palindromes possibles et sélectionne le plus proche en ne considérant que quelques options, ce qui la rend beaucoup plus rapide que les approches par force brute.
Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile audépôtsur 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!