第一题：两数相加(简单题，主要是为了复习链表)
（不会吧不会吧，真的有人这题都能提交错吗，哦，原来是我阿，那没事了）
题目描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例图：
测试用例：
问题分析：主要是模仿大数相加，用链表的方式来模拟计算机做加法运算。
可能考虑出现解决该问题：链表长度不一样，我们需要先遍历完较小的链表加和，再计算进位，再对较长的链表进行剩余的遍历，我们设置一个指针用来遍历，一个头节点用来返回整个链表。
（这里手画图）
C++（很不熟悉，基本都用python了，但是博士申请得上机选定用c++，只能硬磕）
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/classSolution{public:
ListNode*addTwoNumbers(ListNode* l1, ListNode* l2){
//从这里看起
ListNodejg(0);//创建一个头节点
ListNode *l3 = &jg;//创建一个遍历指针
int flag; //设置进位
flag=0;//初始化进位
while(l1 !=nullptr && l2 !=nullptr) //如果俩链表都不为空
{
int s=0;
s=l1->val+l2->val+flag; //求和并累加进位
cout<<l1->val<<endl;
cout<<l2->val<<endl;
cout<<"这里是打印每俩个数的加和"<<endl;
cout<<s<<endl;
cout<<"结束"<<endl;
flag=s>=10? 1:0;
l3->next=new ListNode(s%10);
cout<<"这里是打印对于每一个链表的下一个数"<<endl;
cout<<l3->next->val<<endl;
cout<<"这里是打印对于每一个链表的下一个数"<<endl;
l1=l1->next;
l2=l2->next;
l3=l3->next;
//cout<<l3->val<<endl; }
while(l1 !=nullptr) //已经循环完最小的链表了，我们需要看看剩下的链表在哪里，如果在l1里，则加完它。
{
int s=0;
s=l1->val+flag;
l3->next=new ListNode(s%10);
flag=s>=10?1:0;
l1=l1->next;
l3=l3->next;
}
while(l2 !=nullptr)//已经循环完最小的链表了，我们需要看看剩下的链表在哪里，如果在l2则加完它。
{
int s=0;
s=l2->val+flag;
l3->next=new ListNode(s%10);
flag=s>=10?1:0;
l2=l2->next;
l3=l3->next;
}
if(flag) //如果加到最后，还有一个进位怎么办，我们还需要创建一个节点来保存它
{
l3->next=new ListNode(flag);
}
return jg.next;//返回头节点的next
}
};
第二题 寻找两个正序数组的中位数
暴力合并求中值很简单，但是光看题解的方法我就看了一个小时才会（我好菜）
题目描述：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
测试用例：
首先看非进阶的方式，合并排序，没有什么好说的，给出实现方法。因为这个题目它不会出现重复值，所以我们也没有必要去重。
python 实现：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def findMid(num):
if len(num) % 2 == 0: //如果是偶数数组
return (num[int(len(num)/2)] + num[int((len(num))/2-1)]) / 2 //取中间俩数求和
else :
return num[int((len(num)-1)/2)] * 2 / 2 //取中间一个数
num = sorted(nums1 + nums2) //数据相加排序就可以了
return findMid(num) //返回结果
python的好处在于可以直接相加 nums1 + nums2 就可以合并数组，如果是C++，则需要我们开一个大数组，设置俩标记符i和j，从i=0和j=0开始，每一次比较俩数的大小，小的数就放进新数组，并且小的数组的下标++。
简单的方法直接说完到难的方法
二分方法（听说是408真题？？）
可以看题解一大堆文字哔哔哔，但是基本还是摸不着头脑，但是可以这样理解。
首先我们有俩个有顺序的数组（从小到大）
分别为N1=[1,2,3,4]
和N2=[3,5,7,9,10]
我们可以使用一个小技巧
我们分别找第 (m+n+1) / 2 个元素，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数组均适用。
其中m为N1的长度，n为N2的长度，分别为4和5
我们来验证一下，对于N1和N2的合并数组N3=[1,2,3,3,4,5,7,9,10]
(m+n+1) / 2=5 (m+n+2) / 2=int(5.5)=5
对于奇数组中位数第五个，验证无问题（你非要我数学证明那我就没办法了qaq）
下一步，我们可以通过找第k小数的方法来解决它，对于上面的例子，我们用找第5小数来计算，
//找第k小数
public int find(int[] nums1, int i, int[] nums2, int j, int k){
if( i >= nums1.length) return nums2[j + k - 1];//i是nums1的起始标识，如果过界了，我们需要从nums2里找中位数，直接取j + k - 1，为什么？我也不知道大佬解惑
if( j >= nums2.length) return nums1[i + k - 1];//j是nums1的起始标识，如果过界了，我们需要从nums1里找中位数，直接取i + k - 1，为什么？我也不知道大佬解惑
//k为1时，指的是迭代到边界了，我们直接返回俩数值最小值
if(k == 1){
return Math.min(nums1[i], nums2[j]);
}
int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : 10000000;
int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : 10000000;
if(midVal1 < midVal2){
return find(nums1, i + k / 2, nums2, j , k - k / 2);
}else{
return find(nums1, i, nums2, j + k / 2 , k - k / 2);
}
}
上面代码的思路如果同学(菜鸡申请py交易)们想理解的话可以这么理解，每次都会计算俩个数组的中间值，然后把中间值对比，如果中间值小的数组的中间值前一半的部分就会丢弃（通过什么方式丢弃 i+k/2或者j+k/2），然后剩下的接着比，一直到i或j越界为止。或者k==1为止。
对我来说，记住findkth（）函数就很好了，再理解原理（相当于走了一条捷径）
（但是总所周知的是，所有捷径都有代价，读书如此，做人亦是如此）
此题结束。
第三题 最长回文子串（动态规划，Manacher 算法）
中等难度题目
其实主要动态规划做的不够多，不知道怎么去匹配问题。
这里先偷一张图，看看大佬的动态规划思路是什么样的
大佬链接在这里
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
问题分析：dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。
dp二维数组里一共有俩个值，分别为true和false，分别代表s[i..j]是否为回文数。
分类思考
（1）假如s[i..j]的长度只有1，那它肯定是回文数
（3）假如s[i..j]的长度有大于等于2（>=2）,如果dp[i+1][j-1]是回文数，并且，注意是并且，对于dp[i+1][j-1]新加入的数s[i]==s[j]，那么dp[i][j]是true,s[i..j]是回文数。
下面开始填表（没有时间画图，我就只能偷了（什么，读书人的事情不算偷，那没事了））
下面直接给其他人代码了。（我会自己补上的，qaq）（主要是太菜了，光看理论就看了挺久）
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s) #获取s的值，没有什么问题
if size < 2:
return s #如果小于2，肯定是回文数，我们直接返回就可以了。
dp = [[False for _ in range(size)] for _ in range(size)] #构建二维数组，附上初值
max_len = 1 //记录最大长度
start = 0
for i in range(size): //初始化
dp[i][i] = True //因为每一个s[i][i]的长度都是1，所以都是回文数
for j in range(1, size)://第一个循环
for i in range(0, j): //第二个循环
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j]: //如果dp[i][j]==true
cur_len = j - i + 1 //每次更新就更新一下最大长度
if cur_len > max_len:
max_len = cur_len
start = i //更新start的起始位置
return s[start:start + max_len] //返回回文串
第一个方法结束。
第二个方法Manacher算法
从每个点出发，向俩边寻找对比，最后p里最大的值就是我们要的，最大值位置对应的坐标为回文中心。
class Solution:
# Manacher 算法
def longestPalindrome(self, s: str) -> str:
# 特判
size = len(s)
if size < 2:
return s
# 得到预处理字符串
t = "#"
for i in range(size):
t += s[i]
t += "#"
# 新字符串的长度
t_len = 2 * size + 1
# 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
max_len = 1
# 原始字符串的最长回文子串的起始位置，与 max_len 必须同时更新
start = 0
for i in range(t_len):
cur_len = self.__center_spread(t, i)
if cur_len > max_len:
max_len = cur_len
start = (i - max_len) // 2
return s[start: start + max_len]
def __center_spread(self, s, center):
size = len(s)
i = center - 1
j = center + 1
step = 0
while i >= 0 and j < size and s[i] == s[j]:
i -= 1
j += 1
step += 1
return step
