。找到最近的回文

564。找出最近的回文

難度：難

主題：數學、字串

給定一個表示整數的字串 n，傳回_最接近的整數（不包括其本身），它是一個回文-。如果存在平局，則返回較小的。

最接近的定義為兩個整數之間的絕對差最小化。

範例1：

• 輸入： n = "123"
• 輸出：「121」

範例2：

• 輸入： n = "1"
• 輸出：「0」
• 解釋： 0 和 2 是最接近的回文，但我們回傳最小的 0。

約束：

• 1
• n 僅由數字組成。
• n 沒有前導零。
• n 表示 [1, 10¹⁸ - 1].
範圍內的整數

提示：

1. 暴力破解可以解決這個問題嗎？想點別的事吧。
2. 舉一些例子，如 1234、999、1000 等，並檢查它們最接近的回文。可能有多少種不同的情況？
3. 我們是否必須只考慮字串的左半部分或右半部分，還是兩者都考慮？
4. 試著找出這些數字中最接近的回文數 - 12932、99800、12120。你觀察到什麼了嗎？

解：

我們將專注於建立一個函數來產生潛在的回文候選，然後選擇最接近輸入數字的一個。

解決辦法：

1. 辨識回文候選:

   • 鏡像數字的前半部以形成回文。
   • 考慮邊緣情況，例如所有數字均為 9、100...001 或 99...99。
   • 透過將數字中間向上或向下修改 1 來產生回文。

2. 計算最近的回文:

   • 對於每個回文候選，計算與原始數字的絕對差。
   • 傳回差異最小的回文。如果存在平局，則返回較小的回文。

讓我們用 PHP 實作這個解決方案：564。找出最近的回文

<?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"
?>

解釋：

• 產生回文($firstHalf, $isOddLength):
  • 這個輔助函數透過鏡像數字的前半部來建立回文。

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

• 邊緣情況：

  • 透過明確檢查這些情況來處理從 100...001 或 99...99 等數字產生的回文。

• 主要邏輯:

  • 我們計算可能的回文，然後透過比較絕對差異找到最接近的回文。

該解決方案有效地縮小了可能的回文候選範圍，並透過僅考慮幾個選項來選擇最接近的一個，使其比暴力方法快得多。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。找到最近的回文的詳細內容。更多資訊請關注PHP中文網其他相關文章！