這兩題都涉及到一個(gè)小細(xì)節(jié)蹂风，就是數(shù)組個(gè)數(shù)的奇偶和下標(biāo)的關(guān)系卢厂。一個(gè)數(shù)組的個(gè)數(shù)是n，下標(biāo)就是0到n-1惠啄；如果n是奇數(shù)慎恒，(n-1)/2就是中間元素的下標(biāo)，如果n是偶數(shù)撵渡，(n-1)/2和n/2就是位于中間的兩個(gè)元素融柬；而且，n是奇數(shù)時(shí)趋距，n/2等于(n-1)/2粒氧，這個(gè)細(xì)節(jié)在處理二分等需要定位數(shù)字中間位置的問題時(shí)可以簡化思考。

反過來想节腐，任意一個(gè)數(shù)組外盯，通過在各元素中間插入分隔符(含首位)，得到的新數(shù)組個(gè)數(shù)一定為奇數(shù)(2n+1)：
[1,2,3,4,5] --- [#,1,#,2,#,3,#,4,#,5,#]
[1,2,3,4] --- [#,1,#,2,#,3,#,4,#]
且新數(shù)組中下標(biāo)i翼雀，對(duì)應(yīng)原數(shù)組下標(biāo)i/2饱苟，下面兩個(gè)問題都可以利用這一點(diǎn)統(tǒng)一算法的邏輯。

4.兩個(gè)排序數(shù)組的中位數(shù)

給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2 狼渊。
請(qǐng)找出這兩個(gè)有序數(shù)組的中位數(shù)箱熬。要求算法的時(shí)間復(fù)雜度為 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位數(shù)是 (2 + 3)/2 = 2.5

這個(gè)時(shí)間復(fù)雜度的要求也變相的進(jìn)行了提示狈邑，O(log(n))是類似二分法的時(shí)間復(fù)雜度城须。不過這種思考問題的方式并不可取，容易限制思路米苹，沒有這個(gè)要求我們也應(yīng)該要想到理論上最優(yōu)的方法糕伐。 怎么想到呢？這里就要充分利用已排序這一前提條件驱入，二分查找的原理都知道赤炒，就是從一個(gè)已排序的數(shù)組中快速找到某個(gè)元素氯析。本題只不過變成兩個(gè)數(shù)組，查找的是這兩個(gè)數(shù)組中第(m+n)/2小的元素莺褒。

假設(shè)我們隊(duì)nums1進(jìn)行二分掩缓，根據(jù)二分的位置可以在nums2中找到相應(yīng)的一個(gè)位置，使得兩個(gè)數(shù)組的前半部分相加剛好是一半：
a1,a2,,,ai / ai+1,...,am
b1,b2,...,bj / bj+1,...,bn
對(duì)于個(gè)數(shù)為奇數(shù)的數(shù)組遵岩，我們假設(shè)這個(gè)“/”在中位數(shù)中間你辣，即：[1，(2 / 2)尘执，3]
如果剛好滿足ai<=bj+1 且 bj<=ai+1舍哄，那么中位數(shù)一定就是(max(ai,bj)+min(ai+1,bj+1))/2，反之就繼續(xù)進(jìn)行二分誊锭。

再考慮到前面提到的小技巧表悬，可以將這兩個(gè)數(shù)組分別變成個(gè)數(shù)為2m+1和2n+1的數(shù)組，免去分類討論的情形丧靡。我們得到的是類似如下的數(shù)組：
原數(shù)組為奇數(shù)個(gè) ： [#,1,#,2,#,3,#,4,#,5,#]
原數(shù)組為偶數(shù)個(gè) ： [#,1,#,2,#,3,#,4,#]
我們用l和r分別表示分割左右的兩個(gè)元素蟆沫，假設(shè)某一時(shí)刻二分的分割下標(biāo)是c，則不論個(gè)數(shù)是奇數(shù)還是偶數(shù)温治，l和r在原數(shù)組中的下標(biāo)一定是(c-1)/2和c/2饭庞。

算法寫出來就是：
（參考自https://legacy.gitbook.com/book/hk029/leetbook/details）

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m == 0) return findMedianSortedArray(nums2);
        if (n == 0) return findMedianSortedArray(nums1);
        if (m > n) return findMedianSortedArrays(nums2,nums1);
        int c1,c2,l=0,h=2*m;
        int l1=0,r1=0,l2=0,r2=0;
        while (l <= h) {
            c1 = (l+h)/2;
            // c1確定后，c2取m+n-c1熬荆，保證兩個(gè)數(shù)組左邊個(gè)數(shù)相加等于右邊
            c2 = m+n-c1;
            // num1二分的左邊舟山，邊界時(shí)取最小值不影響 Math.max(l1,l2)的結(jié)果
            l1= (c1 == 0) ? Integer.MIN_VALUE : nums1[(c1-1)/2];
            // num1二分的右邊，邊界時(shí)取最大值不影響 Math.min(r1,r2)的結(jié)果
            r1= (c1 == 2*m) ? Integer.MAX_VALUE : nums1[c1/2];
            // nums2對(duì)應(yīng)的分割左右邊卤恳，同上
            l2= (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2-1)/2];
            r2= (c2 == 2*n) ? Integer.MAX_VALUE : nums2[c2/2];

            if (l1 > r2) {
                h = c1-1;
            }
            else if (l2 > r1) {
                l = c1+1;
            }
            else break;
        }
        return (Math.max(l1,l2) + Math.min(r1,r2))/2.f;
    }

    double findMedianSortedArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return -1;
        else return (nums[(n-1)/2]+nums[n/2])/2.f;
    }
}

5.最長回文子串

給定一個(gè)字符串 s累盗，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為1000突琳。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba"也是一個(gè)有效答案幅骄。
示例 2：
輸入: "cbbd"
輸出: "bb"

假設(shè)我們遍歷數(shù)組，并以每個(gè)點(diǎn)為中心查找最長回文子串本今，這樣下來時(shí)間復(fù)雜度為O(n^2)。在這個(gè)過程中主巍，我們并沒有利用字符串匹配的特殊性冠息，做了大量不必要的重復(fù)匹配。想想一下當(dāng)我們匹配以i為中心的回文串時(shí)孕索，其實(shí)已經(jīng)知道了以i-1和之前的點(diǎn)為中心的最長回文串逛艰，如果之前最長的回文子串包含i，則根本不需要再計(jì)算i搞旭。這里直接貼一個(gè)Manacher算法的思路散怖，下一篇會(huì)整理一下關(guān)于字符串匹配的相關(guān)內(nèi)容菇绵。

和上一題類似的地方是，長度為奇數(shù)的回文串是aba镇眷，abcba這種形式咬最；偶數(shù)則是abba，abccba這種形式欠动。我們同樣可以使用插入分隔符的方法將這兩種形式統(tǒng)一起來：
"#a#b#a#"
"#a#b#b#a#"
這樣都變成了奇數(shù)形式永乌。Manacher算法適合計(jì)算長度為奇數(shù)的回文串，正好可以利用這個(gè)方法具伍。

關(guān)于Manacher算法的內(nèi)容可以參考 Manacher算法總結(jié)
代碼：

class Solution {
    public String longestPalindrome(String s) {
        int bound=0,id=0,max=0;
        StringBuilder p = new StringBuilder();
        p.append('$');
        p.append('#');
        for (int i = 0; i < s.length(); i ++) {
            p.append(s.charAt(i));
            p.append('#');
        }
        p.append('\0');
        int[] P = new int[p.length()-1];
        Arrays.fill(P,1);
        for(int i=1;i < p.length()-1; i++) {
            if(i < bound) {
                P[i] = Math.min(bound-i,P[2*id-i]);
            }
            while(p.charAt(i-P[i]) == p.charAt(i+P[i])) {
                P[i] = P[i]+1;
            }
            if(i+P[i] > bound) {
                bound = i+P[i];
                id = i;
            }
            max = P[i] > P[max]?i:max;
        }
        return s.substring((max-P[max])/2,(max+P[max])/2-1);
    }
}