又要從頭開始練一遍了 我都忘了 姆咪 5. Longest Palindromic Substring def longestPalindrome(self, s: str) -> str: # n = len(s) # cur_len = 1 # ans = s[0] # dp = [[False for i in range(n)] for i in range(n)] # for i in range(n): # dp[i][i] = True # for j in range(n): # for i in range(j): # dp[i][j] = (dp[i+1][j-1] if (i+1)<=(j-1) else True) and s[i]==s[ j] # if dp[i][j] is True and (j-i+1)>cur_len: # ans = s[i:j+1] # cur_len = j-i+1 # manacher s = '#' + '#'.join(s) + '#' p = [1 for _ in range(len(s))] cur_mid, cur_r = 0, 0 # cur_mid: 現在長回文字串的中心 # cur_r: 此回文字串的半徑，含中心，ex:回文長度為3，則半徑是2 for i in range(1, len(s)): if i<(cur_mid+cur_r) and (2*cur_mid-i)>=0: # print(i, p[2*cur_mid-i], cur_mid, cur_r) p[i] = min(p[2*cur_mid-i], cur_mid+cur_r-i) # 這邊要非常注意要卡一個min=cur_mid+cur_r-i，因為此(i+初始半徑-1)不 可能超過現有最長回文字串的最右端 # 最右端是cur_mid+cur_r-1，所以初始半徑最大值是cur_mid+cur_r-1 - i + 1 = cur_mid+cur_r-i else: p[i] = 1 # expand while i-p[i]>=0 and i+p[i]<len(s) and s[i-p[i]]==s[i+p[i]]: p[i] += 1 # update cur_mid and cur_r if p[i]>=cur_r: cur_mid = i cur_r = p[i] return s[cur_mid-cur_r+1:cur_mid+cur_r].replace('#', '') 7. Reverse Integer def reverse(self, x: int) -> int: sign = x<0 x = abs(x) ans = 0 while x: if ans > (2**31-1)//10: return 0 elif (ans*10) > (2**31-1)-x%10: return 0 ans = ans*10 + x%10 x = x//10 return -ans if sign else ans 練習寫一下overflow判斷 假裝自己不是python 8. String to Integer (atoi) def myAtoi(self, s: str) -> int: idx = 0 n = len(s) # leading white spaces while idx<n and s[idx]==' ': idx += 1 # sign sign = False if idx<n and s[idx]=='-': sign = True idx += 1 elif idx<n and s[idx]=='+': idx += 1 # calculate ans = 0 while idx<n and ord(s[idx])>=ord('0') and ord(s[idx])<=ord('9'): if ans>(2**31-1)//10: return 2**31-1 if sign is False else -2**31 if sign is False and ans*10>(2**31-1)-int(s[idx]): return 2**31-1 if sign and ans*10>(2**31)-int(s[idx]): return -2**31 ans = ans*10 + int(s[idx]) idx += 1 return ans if sign is False else -ans 9. Palindrome Number def isPalindrome(self, x: int) -> bool: if x<0: return False elif x==0: return True else: l_digit_idx = floor(log10(x)) r_digit_idx = 0 while r_digit_idx<l_digit_idx: l_digit = (x//(10**l_digit_idx)) % 10 r_digit = x%10 if l_digit != r_digit: return False x = x//10 l_digit_idx -= 2 return True 在忙什麼 哈哈 -- https://i.imgur.com/wRnmv7s.jpeg https://i.imgur.com/mceoqQj.jpeg -- ※ 發信站: 批踢踢實業坊(www.ptt-club.com.tw), 來自: 220.132.58.28 (臺灣) ※ 文章網址: https://www.ptt-club.com.tw/Marginalman/M.1751867666.A.0F0

→ yam276: 大師 07/07 13:57