目錄
- 第一題:TWO SUM
- 1. 題目描述 （簡單難度）
- 2. 解法一
- 3. 解法二
- 4. 解法三
- 5. 總結
- 第二題: Add-Two-Numbers
- 1. 題目描述（中等難度）
- 2. 圖示
- 3. 思路
- 4. 代碼
- 5. 擴充
- 6. 疊代思想
- 7. 疊代代碼
- 8. 遞歸思想
- 9. 代碼
- 第三題: Longest Substring Without Repeating Characters
- 1. 題目描述（中等難度）
- 2. 解法一
- 3. 解法二
- 4. 解法三
- 5. 解法四
- 6. 總結
- 第四題 :Median of Two Sorted Arrays
- 1. 題目描述（困難難度）
- 2. 解法一
- 3. 代碼
- 4. 解法二
- 5. 代碼
- 6. 解法三
- 7. 代碼
- 8. 解法四
- 9. 總結
- 第五題: Longest Palindromic Substring
- 1. 題目描述（中等難度）
- 2. 解法一 暴力破解
- 3. 解法二 最長公共子串
- 4. 解法三 暴力破解優化
- 5. 解法四 擴充中心
- 6. 解法五 Manacher's Algorithm 馬拉車算法。
- 7. 求原字元串下标
- 8. 求每個 P [ i ]
- 8.1. 1. 超出了 R
- 8.2. 2. P [ i_mirror ] 遇到了原字元串的左邊界
- 8.3. 3. i 等于了 R
- 9. 考慮 C 和 R 的更新
- 10. 總結
- 喜歡 請點個 + 關注
第一題:TWO SUM
1. 題目描述 （簡單難度）
給定一個數組和一個目标和，從數組中找兩個數字相加等于目标和，輸出這兩個數字的下标。
2. 解法一
簡單粗暴些，兩重循環，周遊所有情況看相加是否等于目标和，如果符合直接輸出。
public int[] twoSum(int[] nums, int target) {
int []ans=new int[2];
for(int i=0;i<nums.length;i++){
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){
ans[0]=i;
ans[1]=j;
return ans;
}
}
}
return ans;
} 時間複雜度：兩層 for 循環，O（n²）
空間複雜度：O（1）
3. 解法二
在上邊的解法中看下第二個 for 循環步驟。
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){ 我們換個了解方式：
for(int j=(i+1);j<nums.length;j++){
sub=target-nums[i]
if(nums[j]==sub){ 第二層 for 循環無非是周遊所有的元素，看哪個元素等于 sub ，時間複雜度為 O（n）。
有沒有一種方法，不用周遊就可以找到元素裡有沒有等于 sub 的？
hash table ！！！
我們可以把數組的每個元素儲存為 hash 的 key，下标儲存為 hash 的 value 。
這樣隻需判斷 sub 在不在 hash 的 key 裡就可以了，而此時的時間複雜度僅為 O（1）！
需要注意的地方是，還需判斷找到的元素不是目前元素，因為題目裡講一個元素隻能用一次。
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)&&map.get(sub)!=i){
return new int[]{i,map.get(sub)};
}
}
throw new IllegalArgumentException("No two sum solution");
} 時間複雜度：比解法一少了一個 for 循環，降為 O（n）
空間複雜度：所謂的空間換時間，這裡就能展現出來， 開辟了一個 hash table ，空間複雜度變為 O（n）
4. 解法三
看解法二中，兩個 for 循環，他們長的一樣，我們當然可以把它合起來。複雜度上不會帶來什麼變化，變化僅僅是不需要判斷是不是目前元素了，因為目前元素還沒有添加進 hash 裡。
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)){
return new int[]{i,map.get(sub)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
} 5. 總結
題目比較簡單，畢竟暴力的方法也可以解決。唯一閃亮的點就是，時間複雜度從 O（n²）降為 O（n） 的時候，對 hash 的應用，有眼前一亮的感覺。
第二題: Add-Two-Numbers
1. 題目描述（中等難度）
就是兩個連結清單表示的數相加，這樣就可以實作兩個很大的數相加了，無需考慮數值 int ，float 的限制了。
由于自己實作的很亂，直接按答案的講解了。
2. 圖示
連結清單最左邊表示個位數，代表 342 + 465 =807 。
3. 思路
首先每一位相加肯定會産生進位，我們用 carry 表示。進位最大會是 1 ，因為最大的情況是無非是 9 + 9 + 1 = 19 ，也就是兩個最大的數相加，再加進位，這樣最大是 19 ，不會産生進位 2 。下邊是僞代碼。
- 初始化一個節點的頭，dummy head ，但是這個頭不存儲數字。并且将 curr 指向它。
- 初始化進位 carry 為 0 。
- 初始化 p 和 q 分别為給定的兩個連結清單 l1 和 l2 的頭，也就是個位。
- 循環，直到 l1 和 l2 全部到達 null 。
- 設定 x 為 p 節點的值，如果 p 已經到達了 null，設定 x 為 0 。
- 設定 y 為 q 節點的值，如果 q 已經到達了 null，設定 y 為 0 。
- 設定 sum = x + y + carry 。
- 更新 carry = sum / 10 。
- 建立一個值為 sum mod 10 的節點，并将 curr 的 next 指向它，同時 curr 指向變為目前的新節點。
- 向前移動 p 和 q 。
- 判斷 carry 是否等于 1 ，如果等于 1 ，在連結清單末尾增加一個為 1 的節點。
- 傳回 dummy head 的 next ，也就是個位數開始的地方。
初始化的節點 dummy head 沒有存儲值，最後傳回 dummy head 的 next 。這樣的好處是不用單獨對 head 進行判斷改變值。也就是如果一開始的 head 就是代表個位數，那麼開始初始化的時候并不知道它的值是多少，是以還需要在進入循環前單獨對它進行值的更正，不能像現在一樣隻用一個循環簡潔。
4. 代碼
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
} 時間複雜度：O（max（m，n）），m 和 n 代表 l1 和 l2 的長度。
空間複雜度：O（max（m，n）），m 和 n 代表 l1 和 l2 的長度。而其實新的 List 最大長度是 O（max（m，n））+ 1，因為我們的 head 沒有存儲值。
5. 擴充
如果連結清單存儲的順序反過來怎麼辦？
我首先想到的是連結清單先逆序計算，然後将結果再逆序呗，這就轉換到我們之前的情況了。不知道還有沒有其他的解法。下邊分析下單連結清單逆序的思路。
6. 疊代思想
首先看一下原連結清單。
總共需要添加兩個指針，pre 和 next。
初始化 pre 指向 NULL 。
然後就是疊代的步驟，總共四步，順序一步都不能錯。
- next 指向 head 的 next ，防止原連結清單丢失
- head 的 next 從原來連結清單脫離，指向 pre 。
- pre 指向 head
- head 指向 next
一次疊代就完成了，如果再進行一次疊代就變成下邊的樣子。
可以看到整個過程無非是把舊連結清單的 head 取下來，添加的新的連結清單上。代碼怎麼寫呢？
next = head -> next; //儲存 head 的 next , 以防取下 head 後丢失
head -> next = pre; //将 head 從原連結清單取下來，添加到新連結清單上
pre = head;// pre 右移
head = next; // head 右移 接下來就是停止條件了，我們再進行一次循環。
可以發現當 head 或者 next 指向 null 的時候，我們就可以停止了。此時将 pre 傳回，便是逆序了的連結清單了。
7. 疊代代碼
public ListNode reverseList(ListNode head){
if(head==null) return null;
ListNode pre=null;
ListNode next;
while(head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
} 8. 遞歸思想
- 首先假設我們實作了将單連結清單逆序的函數，ListNode reverseListRecursion(ListNode head) ，傳傳入連結表頭，傳回逆序後的連結清單頭。
-
接着我們确定如何把問題一步一步的化小，我們可以這樣想。
把 head 結點拿出來，剩下的部分我們調用函數 reverseListRecursion ，這樣剩下的部分就逆序了，接着我們把 head 結點放到新連結清單的尾部就可以了。這就是整個遞歸的思想了。
- head 結點拿出來
- 剩餘部分調用逆序函數 reverseListRecursion ，并得到了 newhead
- 将 2 指向 1 ，1 指向 null，将 newhead 傳回即可。
-
找到遞歸出口
當然就是如果結點的個數是一個，那麼逆序的話還是它本身，直接 return 就夠了。怎麼判斷結點個數是不是一個呢？它的 next 等于 null 就說明是一個了。但如果傳進來的本身就是 null，那麼直接找它的 next 會報錯，是以先判斷傳進來的是不是 null ，如果是，也是直接傳回就可以了。
9. 代碼
public ListNode reverseListRecursion(ListNode head){
ListNode newHead;
if(head==null||head.next==null ){
return head;
}
newHead=reverseListRecursion(head.next); //head.next 作為剩餘部分的頭指針
head.next.next=head; //head.next 代表新連結清單的尾，将它的 next 置為 head，就是将 head 加到最後了。
head.next=null;
return newHead;
} 第三題: Longest Substring Without Repeating Characters
1. 題目描述（中等難度）
給定一個字元串，找到沒有重複字元的最長子串，傳回它的長度。
2. 解法一
簡單粗暴些，找一個最長子串，那麼我們用兩個循環窮舉所有子串，然後再用一個函數判斷該子串中有沒有重複的字元。
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;//儲存目前得到滿足條件的子串的最大值
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++) //之是以 j<= n，是因為我們子串是 [i,j),左閉右開
if (allUnique(s, i, j)) ans = Math.max(ans, j - i); //更新 ans
return ans;
}
public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>();//初始化 hash set
for (int i = start; i < end; i++) {//周遊每個字元
Character ch = s.charAt(i);
if (set.contains(ch)) return false; //判斷字元在不在 set 中
set.add(ch);//不在的話将該字元添加到 set 裡邊
}
return true;
} 時間複雜度：兩個循環，加上判斷子串滿足不滿足條件的函數中的循環，O（n³）。
空間複雜度：使用了一個 set，判斷子串中有沒有重複的字元。由于 set 中沒有重複的字元，是以最長就是整個字元集，假設字元集的大小為 m ，那麼 set 最長就是 m 。另一方面，如果字元串的長度小于 m ，是 n 。那麼 set 最長也就是 n 了。綜上，空間複雜度為 O（min（m，n））。
3. 解法二
遺憾的是上邊的算法沒有通過 leetCode，時間複雜度太大，造成了逾時。我們怎麼來優化一下呢？
上邊的算法中，我們假設當 i 取 0 的時候，
j 取 1，判斷字元串 str[0,1) 中有沒有重複的字元。
j 取 2，判斷字元串 str[0,2) 中有沒有重複的字元。
j 取 3，判斷字元串 str[0,3) 中有沒有重複的字元。
j 取 4，判斷字元串 str[0,4) 中有沒有重複的字元。
做了很多重複的工作，因為如果 str[0,3) 中沒有重複的字元，我們不需要再判斷整個字元串 str[0,4) 中有沒有重複的字元，而隻需要判斷 str[3] 在不在 str[0,3) 中，不在的話，就表明 str[0,4) 中沒有重複的字元。
如果在的話，那麼 str[0,5) ，str[0,6) ，str[0,7) 一定有重複的字元，是以此時後邊的 j 也不需要繼續增加了。i ++ 進入下次的循環就可以了。
此外，我們的 j 也不需要取 j + 1，而隻需要從目前的 j 開始就可以了。
綜上，其實整個關于 j 的循環我們完全可以去掉了，此時可以了解變成了一個「滑動視窗」。
整體就是橘色視窗在依次向右移動。
判斷一個字元在不在字元串中，我們需要可以周遊整個字元串，周遊需要的時間複雜度就是 O（n），加上最外層的 i 的循環，總體複雜度就是 O（n²）。我們可以繼續優化，判斷字元在不在一個字元串，我們可以将已有的字元串存到 Hash 裡，這樣的時間複雜度是 O（1），總的時間複雜度就變成了 O（n）。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
} 時間複雜度：在最壞的情況下，while 循環中的語句會執行 2n 次，例如 abcdefgg，開始的時候 j 一直後移直到到達第二個 g 的時候固定不變 ，然後 i 開始一直後移直到 n ，是以總共執行了 2n 次，時間複雜度為 O（n）。
空間複雜度：和上邊的類似，需要一個 Hash 儲存子串，是以是 O（min（m，n））。
4. 解法三
繼續優化，我們看上邊的算法的一種情況。
當 j 指向的 c 存在于前邊的子串 abcd 中，此時 i 向前移到 b ,此時子串中仍然含有 c，還得繼續移動，是以這裡其實可以優化。我們可以一步到位，直接移動到子串 c 的位置的下一位！
實作這樣的話，我們将 set 改為 map ，将字元存為 key ，将對應的下标存到 value 裡就實作了。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);//下标 + 1 代表 i 要移動的下個位置
}
return ans;
}
} 與解法二相比
由于采取了 i 跳躍的形式，是以 map 之前存的字元沒有進行 remove ，是以 if 語句中進行了Math.max ( map.get ( s.charAt ( j ) ) , i )，要确認得到的下标不是 i 前邊的。
還有個不同之處是 j 每次循環都進行了自加 1 ，因為 i 的跳躍已經保證了 str[ i , j] 内沒有重複的字元串，是以 j 直接可以加 1 。而解法二中，要保持 j 的位置不變，因為不知道和 j 重複的字元在哪個位置。
最後個不同之處是， ans 在每次循環中都進行更新，因為 ans 更新前 i 都進行了更新，已經保證了目前的子串符合條件，是以可以更新 ans 。而解法二中，隻有當目前的子串不包含目前的字元時，才進行更新。
時間複雜度：我們将 2n 優化到了 n ，但最終還是和之前一樣，O（n）。
空間複雜度：也是一樣的，O（min（m，n)）。
5. 解法四
和解法三思路一樣，差別的地方在于，我們不用 Hash ，而是直接用數組，字元的 ASCII 碼值作為數組的下标，數組存儲該字元所在字元串的位置。适用于字元集比較小的情況，因為我們會直接開辟和字元集等大的數組。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128];
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;//（下标 + 1） 代表 i 要移動的下個位置
}
return ans;
}
} 和解法 3 不同的地方在于，沒有了 if 的判斷，因為如果 index[ s.charAt ( j ) ] 不存在的話，它的值會是 0 ，對最終結果不會影響。
時間複雜度：O（n）。
空間複雜度：O（m），m 代表字元集的大小。這次不論原字元串多小，都會利用這麼大的空間。
6. 總結
綜上，我們一步一步的尋求可優化的地方，對算法進行了優化。又加深了 Hash 的應用，以及利用數組巧妙的實作了 Hash 的作用。
第四題 :Median of Two Sorted Arrays
1. 題目描述（困難難度）
已知兩個有序數組，找到兩個數組合并後的中位數。
2. 解法一
簡單粗暴，先将兩個數組合并，兩個有序數組的合并也是歸并排序中的一部分。然後根據奇數，還是偶數，傳回中位數。
3. 代碼
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
} 時間複雜度：周遊全部數組，O（m + n）
空間複雜度：開辟了一個數組，儲存合并後的兩個數組，O（m + n）
4. 解法二
其實，我們不需要将兩個數組真的合并，我們隻需要找到中位數在哪裡就可以了。
開始的思路是寫一個循環，然後裡邊判斷是否到了中位數的位置，到了就傳回結果，但這裡對偶數和奇數的分類會很麻煩。當其中一個數組周遊完後，出了 for 循環對邊界的判斷也會分幾種情況。總體來說，雖然複雜度不影響，但代碼會看起來很亂。然後在 這裡 找到了另一種思路。
首先是怎麼将奇數和偶數的情況合并一下。
用 len 表示合并後數組的長度，如果是奇數，我們需要知道第 （len + 1）/ 2 個數就可以了，如果周遊的話需要周遊 int ( len / 2 ) + 1 次。如果是偶數，我們需要知道第 len / 2 和 len / 2 + 1 個數，也是需要周遊 len / 2 + 1 次。是以周遊的話，奇數和偶數都是 len / 2 + 1 次。
傳回中位數的話，奇數需要最後一次周遊的結果就可以了，偶數需要最後一次和上一次周遊的結果。是以我們用兩個變量 left 和 right ，right 儲存目前循環的結果，在每次循環前将 right 的值賦給 left 。這樣在最後一次循環的時候，left 将得到 right 的值，也就是上一次循環的結果，接下來 right 更新為最後一次的結果。
循環中該怎麼寫，什麼時候 A 數組後移，什麼時候 B 數組後移。用 aStart 和 bStart 分别表示目前指向 A 數組和 B 數組的位置。如果 aStart 還沒有到最後并且此時 A 位置的數字小于 B 位置的數組，那麼就可以後移了。也就是aStart ＜ m && A[aStart] < B[bStart]。
但如果 B 數組此刻已經沒有數字了，繼續取數字B [ bStart ]，則會越界，是以判斷下 bStart 是否大于數組長度了，這樣 || 後邊的就不會執行了，也就不會導緻錯誤了，是以增加為 aStart ＜ m && ( bStart >= n || A [ aStart ] < B [ bStart ] ) 。
5. 代碼
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
} 時間複雜度：周遊 len/2 + 1 次，len = m + n ，是以時間複雜度依舊是 O（m + n）。
空間複雜度：我們申請了常數個變量，也就是 m，n，len，left，right，aStart，bStart 以及 i 。
總共 8 個變量，是以空間複雜度是 O（1）。
6. 解法三
上邊的兩種思路，時間複雜度都達不到題目的要求 O ( log ( m + n ) )。看到 log ，很明顯，我們隻有用到二分的方法才能達到。我們不妨用另一種思路，題目是求中位數，其實就是求第 k 小數的一種特殊情況，而求第 k 小數有一種算法。
解法二中，我們一次周遊就相當于去掉不可能是中位數的一個值，也就是一個一個排除。由于數列是有序的，其實我們完全可以一半兒一半兒的排除。假設我們要找第 k 小數，我們可以每次循環排除掉 k / 2 個數。看下邊一個例子。
假設我們要找第 7 小的數字。
我們比較兩個數組的第 k / 2 個數字，如果 k 是奇數，向下取整。也就是比較第 3 個數字，上邊數組中的 4 和 下邊數組中的 3 ，如果哪個小，就表明該數組的前 k / 2 個數字都不是第 k 小數字，是以可以排除。也就是 1，2，3 這三個數字不可能是第 7 小的數字，我們可以把它排除掉。将 1349 和 45678910 兩個數組作為新的數組進行比較。
更一般的情況 A [ 1 ]，A [ 2 ]，A [ 3 ]，A [ k / 2] … ，B[ 1 ]，B [ 2 ]，B [ 3 ]，B[ k / 2] … ，如果 A [ k / 2 ] < B [ k / 2 ] ，那麼 A [ 1 ]，A [ 2 ]，A [ 3 ]，A [ k / 2] 都不可能是第 k 小的數字。
A 數組中比 A [ k / 2 ] 小的數有 k / 2 - 1 個，B 數組中，B [ k / 2 ] 比 A [ k / 2 ] 大，假設 B [ k / 2 ] 前邊的數字都比 A [ k / 2 ] 小，也隻有 k / 2 - 1 個，是以比 A [ k / 2 ] 小的數字最多有 k / 2 - 1 + k / 2 - 1 = k - 2 個，是以 A [ k / 2 ] 最多是第 k - 1 小的數。而比 A [ k / 2 ] 小的數更不可能是第 k 小的數了，是以可以把它們排除。
橙色的部分表示已經去掉的數字。
由于我們已經排除掉了 3 個數字，就是這 3 個數字一定在最前邊，是以在兩個新數組中，我們隻需要找第 7 - 3 = 4 小的數字就可以了，也就是 k = 4 。此時兩個數組，比較第 2 個數字，3 < 5，是以我們可以把小的那個數組中的 1 ，3 排除掉了。
我們又排除掉 2 個數字，是以現在找第 4 - 2 = 2 小的數字就可以了。此時比較兩個數組中的第 k / 2 = 1 個數，4 == 4 ，怎麼辦呢？由于兩個數相等，是以我們無論去掉哪個數組中的都行，因為去掉 1 個總會保留 1 個的，是以沒有影響。為了統一，我們就假設 4 > 4 吧，是以此時将下邊的 4 去掉。
由于又去掉 1 個數字，此時我們要找第 1 小的數字，是以隻需判斷兩個數組中第一個數字哪個小就可以了，也就是 4 。
是以第 7 小的數字是 4 。
我們每次都是取 k / 2 的數進行比較，有時候可能會遇到數組長度小于 k / 2 的時候。
此時 k / 2 等于 3 ，而上邊的數組長度是 2 ，我們此時将箭頭指向它的末尾就可以了。這樣的話，由于 2 < 3 ，是以就會導緻上邊的數組 1，2 都被排除。造成下邊的情況。
由于 2 個元素被排除，是以此時 k = 5 ，又由于上邊的數組已經空了，我們隻需要傳回下邊的數組的第 5 個數字就可以了。
從上邊可以看到，無論是找第奇數個還是第偶數個數字，對我們的算法并沒有影響，而且在算法進行中，k 的值都有可能從奇數變為偶數，最終都會變為 1 或者由于一個數組空了，直接傳回結果。
是以我們采用遞歸的思路，為了防止數組長度小于 k / 2 ，是以每次比較 min ( k / 2，len ( 數組 ) ) 對應的數字，把小的那個對應的數組的數字排除，将兩個新數組進入遞歸，并且 k 要減去排除的數字的個數。遞歸出口就是當 k = 1 或者其中一個數字長度是 0 了。
7. 代碼
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//将偶數和奇數的情況合并，如果是奇數，會求兩次同樣的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//讓 len1 的長度小于 len2，這樣就能保證如果有數組空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
} 時間複雜度：每進行一次循環，我們就減少 k / 2 個元素，是以時間複雜度是 O（log（k）），而 k = （m + n）/ 2 ，是以最終的複雜也就是 O（log（m + n））。
空間複雜度：雖然我們用到了遞歸，但是可以看到這個遞歸屬于尾遞歸，是以編譯器不需要不停地堆棧，是以空間複雜度為 O（1）。
8. 解法四
我們首先理一下中位數的定義是什麼
中位數（又稱中值，英語：Median），統計學中的專有名詞，代表一個樣本、種群或機率分布中的一個數值，其可将數值集合劃分為相等的上下兩部分。
是以我們隻需要将數組進行切。
一個長度為 m 的數組，有 0 到 m 總共 m + 1 個位置可以切。
我們把數組 A 和數組 B 分别在 i 和 j 進行切割。
将 i 的左邊和 j 的左邊組合成「左半部分」，将 i 的右邊和 j 的右邊組合成「右半部分」。
- 當 A 數組和 B 數組的總長度是偶數時，如果我們能夠保證
-
左半部分的長度等于右半部分
i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
-
左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那麼，中位數就可以表示如下
（左半部分最大值 + 右半部分最小值 ）/ 2 。
（max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2
- 當 A 數組和 B 數組的總長度是奇數時，如果我們能夠保證
-
左半部分的長度比右半部分大 1
i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
-
左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那麼，中位數就是
左半部分最大值，也就是左半部比右半部分多出的那一個數。
max ( A [ i - 1 ] , B [ j - 1 ]）
上邊的第一個條件我們其實可以合并為 j = ( m + n + 1) / 2 - i，因為如果 m + n 是偶數，由于我們取的是 int 值，是以加 1 也不會影響結果。當然，由于 0 <= i <= m ，為了保證 0 <= j <= n ，我們必須保證 m <= n 。
m≤n,i<m,j=(m+n+1)/2−i≥(m+m+1)/2−i>(m+m+1)/2−m=0m\leq n,i<m,j=(m+n+1)/2-i\geq(m+m+1)/2-i>(m+m+1)/2-m=0m≤n,i<m,j=(m+n+1)/2−i≥(m+m+1)/2−i>(m+m+1)/2−m=0
m≤n,i>0,j=(m+n+1)/2−i≤(n+n+1)/2−i<(n+n+1)/2=nm\leq n,i>0,j=(m+n+1)/2-i\leq (n+n+1)/2-i<(n+n+1)/2=nm≤n,i>0,j=(m+n+1)/2−i≤(n+n+1)/2−i<(n+n+1)/2=n
最後一步由于是 int 間的運算，是以 1 / 2 = 0。
而對于第二個條件，奇數和偶數的情況是一樣的，我們進一步分析。為了保證 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]）），因為 A 數組和 B 數組是有序的，是以 A [ i - 1 ] <= A [ i ]，B [ i - 1 ] <= B [ i ] 這是天然的，是以我們隻需要保證 B [ j - 1 ] < = A [ i ] 和 A [ i - 1 ] <= B [ j ] 是以我們分兩種情況讨論：
- B [ j - 1 ] > A [ i ]，并且為了不越界，要保證 j != 0，i != m
- 此時很明顯，我們需要增加 i ，為了數量的平衡還要減少 j ，幸運的是 j = ( m + n + 1) / 2 - i，i 增大，j 自然會減少。
- A [ i - 1 ] > B [ j ] ，并且為了不越界，要保證 i != 0，j != n
- 此時和上邊的情況相反，我們要減少 i ，增大 j 。
上邊兩種情況，我們把邊界都排除了，需要單獨讨論。
- 當 i = 0 , 或者 j = 0 ，也就是切在了最前邊。
- 此時左半部分當 j = 0 時，最大的值就是 A [ i - 1 ] ；當 i = 0 時 最大的值就是 B [ j - 1] 。右半部分最小值和之前一樣。
- 當 i = m 或者 j = n ，也就是切在了最後邊。
-
此時左半部分最大值和之前一樣。右半部分當 j = n 時，最小值就是 A [ i ] ；當 i = m 時，最小值就是B [ j ] 。
所有的思路都理清了，最後一個問題，增加 i 的方式。當然用二分了。初始化 i 為中間的值，然後減半找中間的，減半找中間的，減半找中間的直到答案。
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
return findMedianSortedArrays(B,A); // 保證 m <= n
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
iMin = i + 1;
}
else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要減小
iMax = i - 1;
}
else { // 達到要求，并且将邊界條件列出來單獨考慮
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇數的話不需要考慮右半部分
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0; //如果是偶數的話傳回結果
}
}
return 0.0;
}
} 時間複雜度：我們對較短的數組進行了二分查找，是以時間複雜度是 O（log（min（m，n）））。
空間複雜度：隻有一些固定的變量，和數組長度無關，是以空間複雜度是 O ( 1 ) 。
9. 總結
解法二中體會到了對情況的轉換，有時候即使有了思路，代碼也不一定寫的優雅，需要多鍛煉才可以。解法三和解法四充分發揮了二分查找的優勢，将時間複雜度降為 log 級别。
第五題: Longest Palindromic Substring
1. 題目描述（中等難度）
給定一個字元串，輸出最長的回文子串。回文串指的是正的讀和反的讀是一樣的字元串，例如 “aba”，“ccbbcc”。
2. 解法一 暴力破解
暴力求解，列舉所有的子串，判斷是否為回文串，儲存最長的回文串。
public boolean isPalindromic(String s) {
int len = s.length();
for (int i = 0; i < len / 2; i++) {
if (s.charAt(i) != s.charAt(len - i - 1)) {
return false;
}
}
return true;
}
// 暴力解法
public String longestPalindrome(String s) {
String ans = "";
int max = 0;
int len = s.length();
for (int i = 0; i < len; i++)
for (int j = i + 1; j <= len; j++) {
String test = s.substring(i, j);
if (isPalindromic(test) && test.length() > max) {
ans = s.substring(i, j);
max = Math.max(max, ans.length());
}
}
return ans;
} 時間複雜度：兩層 for 循環 O（n²），for 循環裡邊判斷是否為回文，O（n），是以時間複雜度為 O（n³）。
空間複雜度：O（1），常數個變量。
3. 解法二 最長公共子串
根據回文串的定義，正着和反着讀一樣，那我們是不是把原來的字元串倒置了，然後找最長的公共子串就可以了。例如，S = " caba"，S’ = " abac"，最長公共子串是 “aba”，是以原字元串的最長回文串就是 “aba”。
關于求最長公共子串（不是公共子序列），有很多方法，這裡用動态規劃的方法，可以先閱讀下邊的連結。
https://www.kancloud.cn/digest/pieces-algorithm/163624
整體思想就是，申請一個二維的數組初始化為 0，然後判斷對應的字元是否相等，相等的話
arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 。
當 i = 0 或者 j = 0 的時候單獨分析，字元相等的話 arr [ i ][ j ] 就賦為 1 。
arr [ i ][ j ] 儲存的就是公共子串的長度。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString(); //字元串倒置
int length = s.length();
int[][] arr = new int[length][length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
}
if (arr[i][j] > maxLen) {
maxLen = arr[i][j];
maxEnd = i; //以 i 位置結尾的字元
}
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
} 再看一個例子，S = “abc435cba”，S’ = “abc534cba” ，最長公共子串是 “abc” 和 “cba” ，但很明顯這兩個字元串都不是回文串。
是以我們求出最長公共子串後，并不一定是回文串，我們還需要判斷該字元串倒置前的下标和目前的字元串下标是不是比對。
比如 S = " caba "，S’ = " abac " ，S’ 中 aba 的下标是 0 1 2 ，倒置前是 3 2 1，和 S 中 aba 的下标符合，是以 aba 就是我們需要找的。當然我們不需要每個字元都判斷，我們隻需要判斷末尾字元就可以。
首先 i ，j 始終指向子串的末尾字元。是以 j 指向的紅色的 a 倒置前的下标是 beforeRev = length - 1 - j = 4 - 1 - 2 = 1，對應的是字元串首位的下标，我們還需要加上字元串的長度才是末尾字元的下标，也就是 beforeRev + arr[ i ] [ j ] - 1 = 1 + 3 - 1 = 3，因為 arr[ i ] [ j ] 儲存的就是目前子串的長度，也就是圖中的數字 3 。此時再和它與 i 比較，如果相等，則說明它是我們要找的回文串。
之前的 S = “abc435cba”，S’ = “abc534cba” ，可以看一下圖示，為什麼不符合。
目前 j 指向的 c ，倒置前的下标是 beforeRev = length - 1 - j = 9 - 1 - 2 = 6，對應的末尾下标是 beforeRev + arr[ i ] [ j ] - 1 = 6 + 3 - 1 = 8 ，而此時 i = 2 ，是以目前的子串不是回文串。
代碼的話，在上邊的基礎上，儲存 maxLen 前判斷一下下标匹不比對就可以了。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString();
int length = s.length();
int[][] arr = new int[length][length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
}
/**********修改的地方*******************/
if (arr[i][j] > maxLen) {
int beforeRev = length - 1 - j;
if (beforeRev + arr[i][j] - 1 == i) { //判斷下标是否對應
maxLen = arr[i][j];
maxEnd = i;
}
/*************************************/
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
} 時間複雜度：兩層循環，O（n²）。
空間複雜度：一個二維數組，O（n²）。
空間複雜度其實可以再優化一下。
我們分析一下循環，i = 0 ，j = 0，1，2 … 8 更新一列，然後 i = 1 ，再更新一列，而更新的時候我們其實隻需要上一列的資訊，更新第 3 列的時候，第 1 列的資訊是沒有用的。是以我們隻需要一個一維數組就可以了。但是更新 arr [ i ] 的時候我們需要 arr [ i - 1 ] 的資訊，假設 a [ 3 ] = a [ 2 ] + 1，更新 a [ 4 ] 的時候， 我們需要 a [ 3 ] 的資訊，但是 a [ 3 ] 在之前已經被更新了，是以 j 不能從 0 到 8 ，應該倒過來，a [ 8 ] = a [ 7 ] + 1，a [ 7 ] = a [ 6 ] + 1 , 這樣更新 a [ 8 ] 的時候用 a [ 7 ] ，用完後才去更新 a [ 7 ]，保證了不會出錯。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString();
int length = s.length();
int[] arr = new int[length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
/**************修改的地方***************************/
for (int j = length - 1; j >= 0; j--) {
/**************************************************/
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[j] = 1;
} else {
arr[j] = arr[j - 1] + 1;
}
/**************修改的地方***************************/
//之前二維數組，每次用的是不同的列，是以不用置 0 。
} else {
arr[j] = 0;
}
/**************************************************/
if (arr[j] > maxLen) {
int beforeRev = length - 1 - j;
if (beforeRev + arr[j] - 1 == i) {
maxLen = arr[j];
maxEnd = i;
}
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
} 時間複雜度：O（n²）。
空間複雜度：降為 O（n）。
4. 解法三 暴力破解優化
解法一的暴力解法時間複雜度太高，在 leetCode 上并不能 AC 。我們可以考慮，去掉一些暴力解法中重複的判斷。我們可以基于下邊的發現，進行改進。
首先定義 P（i，j）。
P(i,j)={trues[i,j]是回文串falses[i,j]不是回文串P(i,j)=\begin{cases}true& \text{s[i,j]是回文串} \\false& \text{s[i,j]不是回文串}\end{cases}P(i,j)=⎩⎪⎨⎪⎧truefalses[i,j]是回文串s[i,j]不是回文串
接下來
P(i,j)=(P(i+1,j−1)&&S[i]==S[j])P(i,j)=(P(i+1,j-1)&&S[i]==S[j])P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
是以如果我們想知道 P（i，j）的情況，不需要調用判斷回文串的函數了，隻需要知道 P（i + 1，j - 1）的情況就可以了，這樣時間複雜度就少了 O（n）。是以我們可以用動态規劃的方法，空間換時間，把已經求出的 P（i，j）存儲起來。
如果 S[i+1,j−1]S[i+1,j-1]S[i+1,j−1] 是回文串，那麼隻要 S [ i ] == S [ j ] ，就可以确定 S [ i , j ] 也是回文串了。
求 長度為 1 和長度為 2 的 P ( i , j ) 時不能用上邊的公式，因為我們代入公式後會遇到 P[i][j]P[i][j]P[i][j] 中 i > j 的情況，比如求 P[1][2]P[1][2]P[1][2] 的話，我們需要知道 P[1+1][2−1]=P[2][1]P[1+1][2-1]=P[2][1]P[1+1][2−1]=P[2][1] ，而 P[2][1]P[2][1]P[2][1] 代表着 S[2,1]S[2,1]S[2,1] 是不是回文串，顯然是不對的，是以我們需要單獨判斷。
是以我們先初始化長度是 1 的回文串的 P [ i , j ]，這樣利用上邊提出的公式 P(i,j)=(P(i+1,j−1)&&S[i]==S[j])P(i,j)=(P(i+1,j-1)&&S[i]==S[j])P(i,j)=(P(i+1,j−1)&&S[i]==S[j])，然後兩邊向外各擴充一個字元，長度為 3 的，為 5 的，所有奇數長度的就都求出來了。
同理，初始化長度是 2 的回文串 P [ i , i + 1 ]，利用公式，長度為 4 的，6 的所有偶數長度的就都求出來了。
public String longestPalindrome(String s) {
int length = s.length();
boolean[][] P = new boolean[length][length];
int maxLen = 0;
String maxPal = "";
for (int len = 1; len <= length; len++) //周遊所有的長度
for (int start = 0; start < length; start++) {
int end = start + len - 1;
if (end >= length) //下标已經越界，結束本次循環
break;
P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); //長度為 1 和 2 的單獨判斷下
if (P[start][end] && len > maxLen) {
maxPal = s.substring(start, end + 1);
}
}
return maxPal;
} 時間複雜度：兩層循環，O（n²）。
空間複雜度：用二維數組 P 儲存每個子串的情況，O（n²）。
我們分析下每次循環用到的 P（i，j），看一看能不能向解法二一樣優化一下空間複雜度。
當我們求長度為 6 和 5 的子串的情況時，其實隻用到了 4 ， 3 長度的情況，而長度為 1 和 2 的子串情況其實已經不需要了。但是由于我們并不是用 P 數組的下标進行的循環，暫時沒有想到優化的方法。
之後看到了另一種動态規劃的思路
https://leetcode.com/problems/longest-palindromic-substring/discuss/2921/Share-my-Java-solution-using-dynamic-programming 。
公式還是這個不變
首先定義 P（i，j）。
P(i,j)={trues[i,j]是回文串falses[i,j]不是回文串P(i,j)=\begin{cases}true& \text{s[i,j]是回文串}\\false& \text{s[i,j]不是回文串}\end{cases}P(i,j)=⎩⎪⎨⎪⎧truefalses[i,j]是回文串s[i,j]不是回文串
接下來
P(i,j)=(P(i+1,j−1)&&S[i]==S[j])P(i,j)=(P(i+1,j-1)&&S[i]==S[j])P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
遞推公式中我們可以看到，我們首先知道了 i +1 才會知道 i ，是以我們隻需要倒着周遊就行了。
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表長度減去 1
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
} 時間複雜度和空間複雜和之前都沒有變化，我們來看看可不可以優化空間複雜度。
當求第 i 行的時候我們隻需要第 i + 1 行的資訊，并且 j 的話需要 j - 1 的資訊，是以和之前一樣 j 也需要倒叙。
public String longestPalindrome7(String s) {
int n = s.length();
String res = "";
boolean[] P = new boolean[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
} 時間複雜度：不變，O（n²）。
空間複雜度：降為 O（n ) 。
5. 解法四 擴充中心
我們知道回文串一定是對稱的，是以我們可以每次循環選擇一個中心，進行左右擴充，判斷左右字元是否相等即可。
由于存在奇數的字元串和偶數的字元串，是以我們需要從一個字元開始擴充，或者從兩個字元之間開始擴充，是以總共有 n + n - 1 個中心。
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
} 時間複雜度：O（n²）。
空間複雜度：O（1）。
6. 解法五 Manacher’s Algorithm 馬拉車算法。
馬拉車算法 Manacher‘s Algorithm 是用來查找一個字元串的最長回文子串的線性方法，由一個叫Manacher的人在1975年發明的，這個方法的最大貢獻是在于将時間複雜度提升到了線性。
主要參考了下邊連結進行講解。
https://blog.crimx.com/2017/07/06/manachers-algorithm/
http://ju.outofmemory.cn/entry/130005
https://articles.leetcode.com/longest-palindromic-substring-part-ii/
首先我們解決下奇數和偶數的問題，在每個字元間插入"#"，并且為了使得擴充的過程中，到邊界後自動結束，在兩端分别插入 “^” 和 “$”，兩個不可能在字元串中出現的字元，這樣中心擴充的時候，判斷兩端字元是否相等的時候，如果到了邊界就一定會不相等，進而出了循環。經過處理，字元串的長度永遠都是奇數了。
首先我們用一個數組 P 儲存從中心擴充的最大個數，而它剛好也是去掉 “#” 的原字元串的總長度。例如下圖中下标是 6 的地方。可以看到 P[ 6 ] 等于 5，是以它是從左邊擴充 5 個字元，相應的右邊也是擴充 5 個字元，也就是 “#c#b#c#b#c#”。而去掉 # 恢複到原來的字元串，變成 “cbcbc”，它的長度剛好也就是 5。
7. 求原字元串下标
用 P 的下标 i 減去 P [ i ]，再除以 2 ，就是原字元串的開頭下标了。
例如我們找到 P[ i ] 的最大值為 5 ，也就是回文串的最大長度是 5 ，對應的下标是 6 ，是以原字元串的開頭下标是 （6 - 5 ）/ 2 = 0 。是以我們隻需要傳回原字元串的第 0 到 第 （5 - 1）位就可以了。
8. 求每個 P [ i ]
接下來是算法的關鍵了，它充分利用了回文串的對稱性。
我們用 C 表示回文串的中心，用 R 表示回文串的右邊半徑坐标，是以 R = C + P[ C ] 。C 和 R 所對應的回文串是目前循環中 R 最靠右的回文串。
讓我們考慮求 P [ i ] 的時候，如下圖。
用 i_mirror 表示目前需要求的第 i 個字元關于 C 對應的下标。
我們現在要求 P [ i ]， 如果是用中心擴充法，那就向兩邊擴充比對就行了。但是我們其實可以利用回文串 C 的對稱性。i 關于 C 的對稱點是 i_mirror ，P [ i_mirror ] = 3，是以 P [ i ] 也等于 3 。
但是有三種情況将會造成直接指派為 P [ i_mirror ] 是不正确的，下邊一一讨論。
8.1. 1. 超出了 R
當我們要求 P [ i ] 的時候，P [ mirror ] = 7，而此時 P [ i ] 并不等于 7 ，為什麼呢，因為我們從 i 開始往後數 7 個，等于 22 ，已經超過了最右的 R ，此時不能利用對稱性了，但我們一定可以擴充到 R 的，是以 P [ i ] 至少等于 R - i = 20 - 15 = 5，會不會更大呢，我們隻需要比較 T [ R+1 ] 和 T [ R+1 ]關于 i 的對稱點就行了，就像中心擴充法一樣一個個擴充。
8.2. 2. P [ i_mirror ] 遇到了原字元串的左邊界
此時P [ i_mirror ] = 1，但是 P [ i ] 指派成 1 是不正确的，出現這種情況的原因是 P [ i_mirror ] 在擴充的時候首先是 “#” == “#” ，之後遇到了 "^"和另一個字元比較，也就是到了邊界，才終止循環的。而 P [ i ] 并沒有遇到邊界，是以我們可以繼續通過中心擴充法一步一步向兩邊擴充就行了。
8.3. 3. i 等于了 R
此時我們先把 P [ i ] 指派為 0 ，然後通過中心擴充法一步一步擴充就行了。
9. 考慮 C 和 R 的更新
就這樣一步一步的求出每個 P [ i ]，當求出的 P [ i ] 的右邊界大于目前的 R 時，我們就需要更新 C 和 R 為目前的回文串了。因為我們必須保證 i 在 R 裡面，是以一旦有更右邊的 R 就要更新 R。
此時的 P [ i ] 求出來将會是 3 ，P [ i ] 對應的右邊界将是 10 + 3 = 13，是以大于目前的 R ，我們需要把 C 更新成 i 的值，也就是 10 ，R 更新成 13。繼續下邊的循環。
public String preProcess(String s) {
int n = s.length();
if (n == 0) {
return "^$";
}
String ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.charAt(i);
ret += "#$";
return ret;
}
// 馬拉車算法
public String longestPalindrome(String s) {
String T = preProcess(s);
int n = T.length();
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i;
if (R > i) {
P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
} else {
P[i] = 0;// 等于 R 的情況
}
// 碰到之前講的三種情況時候，需要利用中心擴充法
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
P[i]++;
}
// 判斷是否需要更新 R
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// 找出 P 的最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2; //最開始講的求原字元串下标
return s.substring(start, start + maxLen);
} 時間複雜度：for 循環裡邊套了一層 while 循環，難道不是 O ( n² )？不！其實是 O ( n )。不嚴謹的想一下，因為 while 循環通路 R 右邊的數字用來擴充，也就是那些還未求出的節點，然後不斷擴充，而期間通路的節點下次就不會再進入 while 了，可以利用對稱得到自己的解，是以每個節點通路都是常數次，是以是 O ( n )。
空間複雜度：O（n）。