. Finden Sie das nächstgelegene Palindrom

564. Finden Sie das nächstgelegene Palindrom

Schwierigkeit:Schwer

Themen:Mathe, String

Gegeben sei eine Zeichenfolge n, die eine Ganzzahl darstellt, gib _die nächstgelegene Ganzzahl (ohne sich selbst) zurück, bei der es sich um ein Palindrom handelt. Wenn es einen Gleichstand gibt, geben Sie den kleineren zurück.

Der nächste Wert ist definiert als die minimale absolute Differenz zwischen zwei ganzen Zahlen.

Beispiel 1:

• Eingabe: n = "123"
• Ausgabe: „121“

Beispiel 2:

• Eingabe: n = „1“
• Ausgabe: „0“
• Erklärung: 0 und 2 sind die nächsten Palindrome, aber wir geben das kleinste zurück, das 0 ist.

Einschränkungen:

• 1 <= n.length <= 18
• n besteht nur aus Ziffern.
• n hat keine führenden Nullen.
• n stellt eine ganze Zahl im Bereich [1, 10¹⁸ - 1] dar.

Hinweis:

1. Wird Brute Force dieses Problem lösen? Denken Sie an etwas anderes.
2. Nehmen Sie einige Beispiele wie 1234, 999,1000 usw. und überprüfen Sie die nächsten Palindrome. Wie viele verschiedene Fälle sind möglich?
3. Müssen wir nur die linke Hälfte oder die rechte Hälfte der Saite oder beides berücksichtigen?
4. Versuchen Sie, das nächstgelegene Palindrom dieser Zahlen zu finden – 12932, 99800, 12120. Haben Sie etwas beobachtet?

Lösung:

Wir konzentrieren uns auf die Erstellung einer Funktion, die potenzielle Palindromkandidaten generiert und dann denjenigen auswählt, der der Eingabenummer am nächsten kommt.

Lösungsansatz:

1. Palindrom-Kandidaten identifizieren:

   • Spiegeln Sie die erste Hälfte der Zahl, um ein Palindrom zu bilden.
   • Betrachten Sie Randfälle, bei denen alle Ziffern 9, 100...001 oder 99...99 sind.
   • Generieren Sie Palindrome, indem Sie die Mitte der Zahl um 1 nach oben oder unten ändern.

2. Berechnen Sie das nächstgelegene Palindrom:

   • Berechnen Sie für jeden Palindrom-Kandidaten die absolute Differenz zur ursprünglichen Zahl.
   • Gib das Palindrom mit der kleinsten Differenz zurück. Bei Gleichstand geben Sie das kleinere Palindrom zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 564. Finden Sie das nächstgelegene Palindrom

<?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>
  
  
  Erläuterung:
</h3>

<ul>
<li>
<strong>generatePalindrome($firstHalf, $isOddLength)</strong>:

<ul>
<li>Diese Hilfsfunktion erstellt ein Palindrom, indem sie die erste Hälfte der Zahl spiegelt.
</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;
}
?>

• Edge Cases:

  • Palindrome, die aus Zahlen wie 100...001 oder 99...99 generiert werden, werden durch explizite Prüfung dieser Fälle behandelt.

• Hauptlogik:

  • Wir berechnen mögliche Palindrome und finden dann das nächstgelegene, indem wir absolute Differenzen vergleichen.

Diese Lösung schränkt mögliche Palindrom-Kandidaten effizient ein und wählt den nächstgelegenen aus, indem sie nur wenige Optionen berücksichtigt, was sie viel schneller macht als Brute-Force-Ansätze.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Finden Sie das nächstgelegene Palindrom. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!