最长回文子串
题目
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
分析
暴力求解很容易想到，遍历所有可能的子串然后从中找到最长的一个回文子串。
可以使用动态规划的方法进行优化。这里顺便复习一下动态规划：
所谓动态规划，核心思想就是利用之前算过的结果快速推算新的计算结果。通常的实现方法是把之前算的结果存在数组中。
分析问题时用递归的思想去考虑，类似于数学归纳法。若要知道当前问题的答案，只需要知道他上一步，再处理一步即可。
最后通过递归终止条件，也就是最简单的情况结束，这就是所谓的动态规划的状态转移方程和边界条件。
所以本题中，可以通过数学归纳的思想，找到动态规划的求解方法。首先，单个字符，两个相连的相同字符都是回文串。接下来，对于其他回文串，如果两头各加一个相同字符，得到的新串是回文串。所以动态规划的状态转移方程可以写为：
P(i,j)=P(i+1,j−1)∧(S**i==S**j)
通过一个二维数组 dp[][] , dp[i][j] = True 就表示从第i字符到第j字符之间的子串是回文串。这样就可以在后续判断更长的子串是不是回文串的时候查询，来利用已经计算好的结果来节约时间。
代码示例：
class Solution:
def longestPalindrome(self, s: str) -> str:
total = len(s)
dp = [[False] * total for _ in range(total)]
ans=""
noPalindrome=True
for l in range(total):
noPalindrome=True
for i in range(total):
j = i + l
if j >= total:
break
if l == 0:
dp[i][j] = True
elif l == 1:
dp[i][j] = s[i] == s[j]
else:
dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
if dp[i][j] and noPalindrome:
ans=s[i:j+1]
noPalindrome=False
return ans
算法分析：时间复杂度 O(n^2) 空间复杂度 O(n^2)
另一种方法是中心扩展法，也就是以每个字符为中心，向外寻找最长的回文串。空间复杂度为O(1)
整数反转
题目
给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号），只能存取32位的整数。
输入：x = -123
输出：-321
分析
对整数进行反转，本题不建议通过字符串来做，会徒增很多无用功导致效率变慢，而且在判断溢出上也较为麻烦。
反转整数，其实就是每次取出原数的最后一位，从后面压入新数中。数学上就是每次把前一次的结果乘10再加上新的一位。判断溢出时，需要在计算下一次的结果前进行预测。
另外还需要考虑到负数的情况，先将符号记录下来按照正数处理，然后给结果加上符号。还要注意正负数判断溢出的条件差1，要进行区分。
示例代码：
class Solution:
def reverse(self, x: int) -> int:
res = 0
up = 2 ** 31 - 1
down = -2 ** 31
flag = x < 0
if flag:
x = -x
while x != 0:
num = x % 10
x //= 10
if not flag and (res > up // 10 or (res == up // 10 and num > 7)):
return 0
if flag and (res > up // 10 or (res == up // 10 and num > 8)):
return 0
res = res * 10 + num
if flag:
res = -res
return res
判断溢出总结
这个题涉及到了对溢出的判断，因此顺便总结一下对整数大数溢出的几种判断方法。
两数相加
符号相反的两个数相加不会溢出；符号相同的两数，如果相加的结果符号变化了，则表示溢出了。
两数相乘
不能通过符号来判断是否溢出。但是可以用结果做逆运算，把结果除以其中一个乘数，如果不能得到另一个乘数，则表示溢出了。
其实上面的两数相加也可以用类似的方法判断，但是符号判断已经足够便利。
对一个数固定的操作
上面两种溢出判断都建立在溢出后不能得到正确结果的前提上，而且要先计算结果才知道是不是错了。但是也可以预先对操作结果进行判断。
例如将一个数乘10。最好可以在溢出前就对这个数需要满足的条件进行判断。如果这个数本身已经大于 MaxInt/10 那么它乘10的结果就会溢出。
