第一題：兩數(shù)相加(簡單題，主要是為了復(fù)習(xí)鏈表)

（不會(huì)吧不會(huì)吧，真的有人這題都能提交錯(cuò)嗎，哦，原來是我阿，那沒事了）

題目描述：

給你兩個(gè)?非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照?逆序?的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ)?一位?數(shù)字。

請你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0?開頭。

示例圖：

測試用例：

問題分析：主要是模仿大數(shù)相加，用鏈表的方式來模擬計(jì)算機(jī)做加法運(yùn)算。

可能考慮出現(xiàn)解決該問題：鏈表長度不一樣，我們需要先遍歷完較小的鏈表加和，再計(jì)算進(jìn)位，再對較長的鏈表進(jìn)行剩余的遍歷，我們設(shè)置一個(gè)指針用來遍歷，一個(gè)頭節(jié)點(diǎn)用來返回整個(gè)鏈表。

（這里手畫圖）

C++（很不熟悉，基本都用python了，但是博士申請得上機(jī)選定用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);//創(chuàng)建一個(gè)頭節(jié)點(diǎn)

? ? ? ? ListNode *l3 = &jg;//創(chuàng)建一個(gè)遍歷指針

? ? ? ? int flag; //設(shè)置進(jìn)位

? ? ? ? flag=0;//初始化進(jìn)位

? ? ? ? while(l1 !=nullptr && l2 !=nullptr) //如果倆鏈表都不為空

? ? ? ? {

? ? ? ? ? ? int s=0;

? ? ? ? ? ? s=l1->val+l2->val+flag; //求和并累加進(jìn)位

? ? ? ? ? ? cout<<l1->val<<endl;

? ? ? ? ? ? cout<<l2->val<<endl;

? ? ? ? ? ? cout<<"這里是打印每倆個(gè)數(shù)的加和"<<endl;

? ? ? ? ? ? cout<<s<<endl;

? ? ? ? ? ? cout<<"結(jié)束"<<endl;

? ? ? ? ? ? flag=s>=10? 1:0;

? ? ? ? ? ? l3->next=new ListNode(s%10);

? ? ? ? ? ? cout<<"這里是打印對于每一個(gè)鏈表的下一個(gè)數(shù)"<<endl;

? ? ? ? ? ? cout<<l3->next->val<<endl;

? ? ? ? ? ? cout<<"這里是打印對于每一個(gè)鏈表的下一個(gè)數(shù)"<<endl;

? ? ? ? ? ? l1=l1->next;

? ? ? ? ? ? l2=l2->next;

? ? ? ? ? ? l3=l3->next;

? ? ? ? ? ? //cout<<l3->val<<endl;? ? ? ? }

? ? ? ? while(l1 !=nullptr) //已經(jīng)循環(huán)完最小的鏈表了，我們需要看看剩下的鏈表在哪里，如果在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)//已經(jīng)循環(huán)完最小的鏈表了，我們需要看看剩下的鏈表在哪里，如果在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) //如果加到最后，還有一個(gè)進(jìn)位怎么辦，我們還需要?jiǎng)?chuàng)建一個(gè)節(jié)點(diǎn)來保存它

? ? ? ? {

? ? ? ? ? ? l3->next=new ListNode(flag);

? ? ? ? }

? ? ? ? return jg.next;//返回頭節(jié)點(diǎn)的next

? ? }

};

第二題?尋找兩個(gè)正序數(shù)組的中位數(shù)

暴力合并求中值很簡單，但是光看題解的方法我就看了一個(gè)小時(shí)才會(huì)（我好菜）

題目描述：給定兩個(gè)大小為 m 和 n 的正序（從小到大）數(shù)組?nums1 和?nums2。請你找出并返回這兩個(gè)正序數(shù)組的中位數(shù)。

進(jìn)階：你能設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(log (m+n)) 的算法解決此問題嗎？

測試用例：

首先看非進(jìn)階的方式，合并排序，沒有什么好說的，給出實(shí)現(xiàn)方法。因?yàn)檫@個(gè)題目它不會(huì)出現(xiàn)重復(fù)值，所以我們也沒有必要去重。

python 實(shí)現(xiàn)：

class?Solution:

????def?findMedianSortedArrays(self,?nums1:?List[int],?nums2:?List[int])?->?float:????????

????????def?findMid(num):

????????????if?len(num)?%?2?==?0: //如果是偶數(shù)數(shù)組

????????????????return?(num[int(len(num)/2)]?+?num[int((len(num))/2-1)])?/?2? //取中間倆數(shù)求和

????????????else?:

????????????????return?num[int((len(num)-1)/2)]?*?2?/?2? //取中間一個(gè)數(shù)

????????num?=?sorted(nums1?+?nums2) //數(shù)據(jù)相加排序就可以了

????????return?findMid(num) //返回結(jié)果

python的好處在于可以直接相加 nums1?+?nums2 就可以合并數(shù)組，如果是C++，則需要我們開一個(gè)大數(shù)組，設(shè)置倆標(biāo)記符i和j，從i=0和j=0開始，每一次比較倆數(shù)的大小，小的數(shù)就放進(jìn)新數(shù)組，并且小的數(shù)組的下標(biāo)++。

簡單的方法直接說完到難的方法

二分方法（聽說是408真題？？）

可以看題解一大堆文字嗶嗶嗶，但是基本還是摸不著頭腦，但是可以這樣理解。

首先我們有倆個(gè)有順序的數(shù)組（從小到大）

分別為N1=[1,2,3,4]

和N2=[3,5,7,9,10]

我們可以使用一個(gè)小技巧

我們分別找第 (m+n+1) / 2 個(gè)元素，和 (m+n+2) / 2 個(gè)，然后求其平均值即可，這對奇偶數(shù)組均適用。

其中m為N1的長度，n為N2的長度，分別為4和5

我們來驗(yàn)證一下，對于N1和N2的合并數(shù)組N3=[1,2,3,3,4,5,7,9,10]

?(m+n+1) / 2=5? ??(m+n+2) / 2=int(5.5)=5

對于奇數(shù)組中位數(shù)第五個(gè)，驗(yàn)證無問題（你非要我數(shù)學(xué)證明那我就沒辦法了qaq）

下一步，我們可以通過找第k小數(shù)的方法來解決它，對于上面的例子，我們用找第5小數(shù)來計(jì)算，

//找第k小數(shù)

?public?int?find(int[]?nums1,?int?i,?int[]?nums2,?int?j,?int?k){

????????if(?i?>=?nums1.length)?return?nums2[j?+?k?-?1];//i是nums1的起始標(biāo)識(shí)，如果過界了，我們需要從nums2里找中位數(shù)，直接取j?+?k?-?1，為什么？我也不知道大佬解惑

????????if(?j?>=?nums2.length)?return?nums1[i?+?k?-?1];//j是nums1的起始標(biāo)識(shí)，如果過界了，我們需要從nums1里找中位數(shù)，直接取i +?k?-?1，為什么？我也不知道大佬解惑

? ? ? ? //k為1時(shí)，指的是迭代到邊界了，我們直接返回倆數(shù)值最小值

????????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);

????????}????????

????}

上面代碼的思路如果同學(xué)(菜雞申請py交易)們想理解的話可以這么理解，每次都會(huì)計(jì)算倆個(gè)數(shù)組的中間值，然后把中間值對比，如果中間值小的數(shù)組的中間值前一半的部分就會(huì)丟棄（通過什么方式丟棄 i+k/2或者j+k/2），然后剩下的接著比，一直到i或j越界為止?；蛘遦==1為止。

對我來說，記住findkth（）函數(shù)就很好了，再理解原理（相當(dāng)于走了一條捷徑）

（但是總所周知的是，所有捷徑都有代價(jià)，讀書如此，做人亦是如此）

此題結(jié)束。

第三題?最長回文子串（動(dòng)態(tài)規(guī)劃，Manacher 算法）

中等難度題目

其實(shí)主要?jiǎng)討B(tài)規(guī)劃做的不夠多，不知道怎么去匹配問題。

這里先偷一張圖，看看大佬的動(dòng)態(tài)規(guī)劃思路是什么樣的

大佬鏈接在這里

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]?定義為左閉右閉區(qū)間，可以取到?s[i]?和?s[j]。

dp二維數(shù)組里一共有倆個(gè)值，分別為true和false，分別代表s[i..j]是否為回文數(shù)。

分類思考

（1）假如s[i..j]的長度只有1，那它肯定是回文數(shù)

（3）假如s[i..j]的長度有大于等于2（>=2）,如果dp[i+1][j-1]是回文數(shù)，并且，注意是并且，對于dp[i+1][j-1]新加入的數(shù)s[i]==s[j]，那么dp[i][j]是true,s[i..j]是回文數(shù)。

下面開始填表（沒有時(shí)間畫圖，我就只能偷了（什么，讀書人的事情不算偷，那沒事了））

下面直接給其他人代碼了。（我會(huì)自己補(bǔ)上的，qaq）（主要是太菜了，光看理論就看了挺久）

class Solution:

? ? def longestPalindrome(self, s: str) -> str:

? ? ? ? size = len(s) #獲取s的值，沒有什么問題

? ? ? ? if size < 2:

? ? ? ? ? ? return s #如果小于2，肯定是回文數(shù)，我們直接返回就可以了。

? ? ? ? dp = [[False for _ in range(size)] for _ in range(size)] #構(gòu)建二維數(shù)組，附上初值

? ? ? ? max_len = 1 //記錄最大長度

? ? ? ? start = 0

? ? ? ? for i in range(size): //初始化

? ? ? ? ? ? dp[i][i] = True? //因?yàn)槊恳粋€(gè)s[i][i]的長度都是1，所以都是回文數(shù)

? ? ? ? for j in range(1, size)://第一個(gè)循環(huán)

? ? ? ? ? ? for i in range(0, j): //第二個(gè)循環(huán)

? ? ? ? ? ? ? ? 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] //返回回文串

第一個(gè)方法結(jié)束。

第二個(gè)方法Manacher算法

從每個(gè)點(diǎn)出發(fā)，向倆邊尋找對比，最后p里最大的值就是我們要的，最大值位置對應(yīng)的坐標(biāo)為回文中心。

class Solution:

? ? # Manacher 算法

? ? def longestPalindrome(self, s: str) -> str:

? ? ? ? # 特判

? ? ? ? size = len(s)

? ? ? ? if size < 2:

? ? ? ? ? ? return s

? ? ? ? # 得到預(yù)處理字符串

? ? ? ? t = "#"

? ? ? ? for i in range(size):

? ? ? ? ? ? t += s[i]

? ? ? ? ? ? t += "#"

? ? ? ? # 新字符串的長度

? ? ? ? t_len = 2 * size + 1

? ? ? ? # 當(dāng)前遍歷的中心最大擴(kuò)散步數(shù)，其值等于原始字符串的最長回文子串的長度

? ? ? ? max_len = 1

? ? ? ? # 原始字符串的最長回文子串的起始位置，與 max_len 必須同時(shí)更新

? ? ? ? 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