# @lc code=start
class Solution:
def myAtoi(self, s: str) -> int:
s=s.lstrip()+" "
j=0
if s[0]=="-" and s[1] in ["0","1","2","3","4","5","6","7","8","9"]:
for i in s[1:]:
re="-"
j=j+1
while i not in ["0","1","2","3","4","5","6","7","8","9"] or i==".":
return int(s[0:j]) if int(s[0:j])>-2**31 else -2**31
elif s[0] =="+" and s[1] in ["0","1","2","3","4","5","6","7","8","9"]:
for i in s[1:]:
j=j+1
while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
return int(s[1:j]) if int(s[1:j])<2**31-1 else 2**31-1
elif s[0] in ["0","1","2","3","4","5","6","7","8","9"]:
for i in s[1:]:
j=j+1
while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
return int(s[0:j]) if int(s[0:j])<2**31-1 else 2**31-1
else:return 0
# @lc code=end
# [5] 最长回文子串
#
# @lc code=start
class Solution:
def longestPalindrome(self, s: str) -> str:
length=len(s)
mx=""
if length ==1:
return s
if length ==2 and s[0]==s[1]:
return s
elif length ==2 and s[0]!=s[1]:
return s[0]
#对于回文串中心是单个元素
for i in range(length):
start =end = i
if i ==0: mx=s[0]
else:
for j in range(i):
start -=1
end +=1
#if start>=0 and end<length:
# print(i-j-1,i+j+1)
if start>=0 and end<length and s[i-j-1]==s[i+j+1]:
mx=s[i-j-1:i+j+1+1] if 2*j+3>len(mx) else mx
else:break
#对于回文串中心是相邻两个元素的情况：
for i in range(length):
end = i
start =i-1
if i ==0: continue
if i ==1 and s[0]==s[1]:
mx=s[0:2] if 2>len(mx) else mx
print(mx)
continue
elif s[i]==s[i-1]:
mx=s[i-1:i+1] if 2>=len(mx) else mx
print(mx)
for j in range(i):
start -=1
end +=1
if start>=0 and end<length and s[i-1-j-1]==s[i+j+1]:
mx=s[i-1-j-1:i+j+1+1] if 2*j+4>len(mx) else mx
else:break
else:continue
return mx
# @lc code=end
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
max_len = 1
begin = 0
# dp[i][j] 表示 s[i..j] 是否是回文串
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 递推开始
# 先枚举子串长度
for L in range(2, n + 1):
# 枚举左边界，左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
j = L + i - 1
# 如果右边界越界，就可以退出当前循环
if j >= n:
break
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
# 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
class Solution:
def expandAroundCenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0
for i in range(len(s)):
left1, right1 = self.expandAroundCenter(s, i, i)
left2, right2 = self.expandAroundCenter(s, i, i + 1)
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start: end + 1]
当在位置 i 开始进行中心拓展时，我们可以先找到 i 关于 j 的对称点 2 * j – i。那么如果点 2 * j – i 的臂长等于 n，我们就可以知道，点 i 的臂长至少为 min(j + length – i, n)。那么我们就可以直接跳过 i 到 i + min(j + length – i, n) 这部分，从 i + min(j + length – i, n) + 1 开始拓展。
class Solution:
def expand(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return (right - left - 2) // 2
def longestPalindrome(self, s: str) -> str:
end, start = -1, 0
s = '#' + '#'.join(list(s)) + '#'
arm_len = []
right = -1
j = -1
for i in range(len(s)):
if right >= i:
i_sym = 2 * j - i
min_arm_len = min(arm_len[i_sym], right - i)
cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
else:
cur_arm_len = self.expand(s, i, i)
arm_len.append(cur_arm_len)
if i + cur_arm_len > right:
j = i
right = i + cur_arm_len
if 2 * cur_arm_len + 1 > end - start:
start = i - cur_arm_len
end = i + cur_arm_len
return s[start+1:end+1:2]
List=[i for item in List for i in item if i!=-1 and i<length]
最后根据一维数组对应位置的值就是新字符串对应下标的字符
for j in range(length):
string[j]=s[List[j]]
return "".join(string)
其中numrows=1的 情况要单独考虑
# @lc code=start
class Solution:
def convert(self, s: str, numRows: int) -> str:
length=len(s)
if length<=numRows or numRows==1 :
return s
row=(length//((numRows-1)*2)+1)*2
List=[[-1 for m in range(numRows)] for l in range(row)]
nextstart=0
#第i行
for i in range(row):
#如果是偶数行：
if(i % 2) == 0:
List[i]=[j for j in range(nextstart,nextstart+numRows)]
nextstart=nextstart+(numRows-1)*2
else:
List[i][0]=-1
List[i][numRows-1]=-1
List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1][numRows-1]+1+numRows-2))[::-1]
List=list(list(i) for i in zip(*List))
List=[i for item in List for i in item if i!=-1 and i<length]
string=list(range(length))
for j in range(length):
string[j]=s[List[j]]
return "".join(string)
改进：
方法一：按行排序 思路
通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
算法
我们可以使用 \(\text{min}( \text{numRows}, \text{len}(s))\) 个列表来表示 Z 字形图案中的非空行。
