564. Find the Closest Palindrome

📋 Đề Bài

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

1 <= n.length <= 18
n consists of only digits.
n does not have leading zeros.
n is representing an integer in the range [1, 10¹⁸ - 1].

🧠 Thuật Toán & Kỹ Thuật

Binary Search (Tìm kiếm nhị phân)

⏱️ Thời gian O(log n)

💾 Không gian O(n)

💻 Lời Giải

Python 0564-find-the-closest-palindrome.py

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        n = int(n)
        
        def convertNum(num):
            s = list(str(num))
            l = (len(s) - 1) // 2
            r = (len(s)) // 2
            
            while l >= 0:
                s[r] = s[l]
                l -= 1
                r += 1
                
            s = ''.join(s)
                
            return int(s)
        
        left = 0
        right = 10**18
        min_nump = 0
        
        while left <= right:
            mid = (left + right) // 2
            mid_pl = convertNum(mid)
            
            if mid_pl < n:
                min_nump = mid_pl
                left = mid + 1
            else:
                right = mid - 1
                
        left = 0
        right = 10**18
        max_nump = 0
        
        while left <= right:
            mid = (left + right) // 2
            mid_pl = convertNum(mid)
            
            if mid_pl > n:
                max_nump = mid_pl
                right = mid - 1
            else:
                left = mid + 1
                
        if max_nump - n >= n - min_nump:
            return str(min_nump)
        
        return str(max_nump)