。找到最近的回文

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。找到最近的回文

雷雷

解釋：

• 產生回文（$firstHalf，$isOddLength）：
  • 此輔助函數透過鏡像數字的前半部來建立回文。

雷雷

• 邊緣案例:

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

• 主要邏輯:

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

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

聯絡連結

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

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

• 領英
• GitHub

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