. Trouvez le palindrome le plus proche

564. Trouvez le palindrome le plus proche

Difficulté : Difficile

Sujets : Mathématiques, Chaîne

É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é, retournez le 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, 10¹⁸ - 1].

Indice :

1. La force brute fonctionnera-t-elle pour résoudre ce problème ? Pensez à autre chose.
2. Prenons quelques exemples comme 1234, 999,1000, etc. et vérifiez leurs palindromes les plus proches. Combien de cas différents sont possibles ?
3. Doit-on considérer uniquement la moitié gauche ou la moitié droite de la corde ou les deux ?
4. 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 :

1. 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.

2. Calculer le palindrome le plus proche :

   • Pour chaque candidat palindrome, calculez la différence absolue avec le nombre d'origine.
   • Renvoyer 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

<?php
/**
* @param String $n
* @return String
*/
function nearestPalindromic($n) {
    ...
    ...
    ...
    /**
     * go to https://github.com/mah-shamim/leet-code-in-php/tree/main/algorithms/000564-find-the-closest-palindrome/solution.php
     */
}

function generatePalindrome($firstHalf, $isOddLength) {
    ...
    ...
    ...
}

// Example usage
echo nearestPalindromic("123"); // Output: "121"
echo nearestPalindromic("1");   // Output: "0"
?>




<h3>
  
  
  Explication:
</h3>

<ul>
<li>
<strong>générer Palindrome($firstHalf, $isOddLength)</strong> :

<ul>
<li>Cette fonction d'assistance crée un palindrome en reflétant la première moitié du nombre.
</li>
</ul>


</li>

</ul>

<pre class="brush:php;toolbar:false"><?php
/**
* @param $firstHalf
* @param $isOddLength
* @return string
*/
function generatePalindrome($firstHalf, $isOddLength) {
    $secondHalf = strrev(substr($firstHalf, 0, $isOddLength ? -1 : $firstHalf));
    return $firstHalf . $secondHalf;
}
?>

• Cas 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 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!