Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/24 10:06)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串760/1548 (看更多)

564. Find the Closest Palindrome ## 思路迴文就把前半數字複製到後半因為有多種case, 所以產生所有可能case的迴文取跟原數字差值最小的迴文 1. 一般case: 12345 -> 12321 2. 加減位數: 99 -> 101, 1000 -> 999 3. 位數不變, 但中間值-1: 9500 -> 9449 4. 11~15 -> 9 吃了幾個WA 煩 ## Code ```python class Solution: def nearestPalindromic(self, n: str) -> str: if len(n) == 1: return str(int(n)-1) def get_palindrome(s): res = list(s) m = len(s)//2 for i in range(m): res[~i] = res[i] # corner case: n is palindromic output = ''.join(res) if output != n: return output # 12021 -> 12121 if len(res) & 1: res[m] = str(int(res[m])-1) if res[m] != '0' else str(int(res[m])+1) else: res[m-1] = res[m] = str(int(res[m])-1) if res[m] != '0' else str(int(res[m])+1) return ''.join(res) m = len(n)//2 n1 = str(int(n) + 10**m) # 99 -> 101 n2 = str(int(n) - 10**m) # 9500 -> 9449 n3 = str(int(n) - 10**(m-1)) # 1000 -> 999 res = '' curr_min = float('inf') for s in n2, n3, n, n1: palindrome = get_palindrome(s) if len(s) > 1 else '9' diff = abs(int(palindrome) - int(n)) if diff < curr_min: curr_min = diff res = palindrome return res ``` -- http://i.imgur.com/OLvBn3b.jpg