又要從頭開始練一遍了
我都忘了
姆咪
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
在忙什麼 哈哈