前言

正文6道題目來自leetcode––為求職為生的編程網(wǎng)站，目的是工作閑暇之時(shí)錘煉代碼功底。
沒有捷徑，但手熟爾；
一步領(lǐng)先，步步領(lǐng)先。

正文

5. Longest Palindromic Substring
題目鏈接
題目大意：
輸入一個(gè)回文串，輸出長度最長的回文子串；
如果有多個(gè)答案，輸出任意一個(gè)。

Example
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

** 題目解析：**
模板題，有現(xiàn)成的解法。
求回文串有O(N)的算法，詳見manacher解析。
** 復(fù)雜度解析：**
空間、時(shí)間復(fù)雜度都是O(N)， N是字符串的長度；
** 其他解法：**
暴力，從每個(gè)點(diǎn)開始枚舉，判斷最長的回文子串，O(N^2);
kmp，回文串s和s的轉(zhuǎn)置是一樣的，那么可以把原串s和s'進(jìn)行匹配，判斷區(qū)間是否合法；（有可能存在匹配，但是區(qū)間不重疊的情況）

30. Substring with Concatenation of All Words
題目鏈接
***題目大意： ***
給出一個(gè)字符串s，一個(gè)字符列表words，words內(nèi)的單詞都是同一長度，找到一個(gè)區(qū)間，要求：
1、區(qū)間內(nèi)的字符串，可以切分成若干個(gè)連續(xù)的子串，每個(gè)子串都是words的單詞；
2、每個(gè)單詞只出現(xiàn)一次；
輸出所有可能的區(qū)間的起點(diǎn)。

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].

題目解析：
題目提供了一個(gè)了一個(gè)不可忽視的限制，所有的words是同一長度，這樣就避免了fool和foo的情況；
并且在判斷s的子串是否出現(xiàn)時(shí)，可以直接截取長度為m的字符串。
這樣流程就變成：
1、初始位置s，截取m個(gè)字符str，查詢str是否在words中，如果在則判斷下m個(gè)字符；
2、如果不在words中，則回溯到最初的位置s，從s+1開始判斷。

但是， 這樣的復(fù)雜度會很高，因?yàn)榛厮葜笥忠獜脑瓉淼奈恢玫南乱粋€(gè)開始匹配。
有一種優(yōu)化方案：假設(shè)len為words字符串的統(tǒng)一長度；
從0,1,2...到len-1，分別匹配一次即可。
這樣可以采取一種策略，當(dāng)(l, r)的字符串最后len個(gè)字符匹配失敗后，直接從r+1的位置匹配；因?yàn)?r-len,r)的字符不存在words中；
如果(r-len, r)在之前已經(jīng)在k出現(xiàn)過，則可以把左邊界移到k+1，直到遇到右邊界；
可以在len次枚舉后得到結(jié)果。

** 復(fù)雜度解析： **
時(shí)間復(fù)雜度是O(N*len)，len為words中單詞的長度。
空間復(fù)雜度是O(M*len)，hash的空間復(fù)雜度較高；

** 其他解法：**
有稍微慢一點(diǎn)，但是代碼量很小的做法。
僅需20行。
詳見這里

56. Merge Intervals
題目鏈接
** 題目大意：**
給出n個(gè)數(shù)字區(qū)間，把有相交的區(qū)間合并起來。

example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

題目解析：
區(qū)間合并只需考慮最左和最右的邊界。
先排序，把可能合并到區(qū)間集合在一起。
容易知道如果前面區(qū)間的right >= 當(dāng)前區(qū)間的left 的時(shí)候，是可以合并的。
那么遍歷一遍，判斷邊界是否相交即可。

** 復(fù)雜度解析：**
時(shí)間復(fù)雜度是O(NlogN)，N是區(qū)間個(gè)數(shù)（時(shí)間都在排序上）；
空間復(fù)雜度是O(N)，有可能返回N個(gè)結(jié)果。

** 代碼量：**
比較函數(shù)有簡單寫法。
sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});

76. Minimum Window Substring
題目鏈接
** 題目大意：**
給出兩個(gè)字符串S和T，在S中尋找一個(gè)子串s，要求：
1、s包括T出現(xiàn)過的所有字符；
2、s的字符串長度最?。?/p>

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

如果沒有，返回空串；
題目保證只有一個(gè)答案。

** 題目解析：**
題目要求s出現(xiàn)T中所有的字符，但是沒有順序要求，那么對于一段字符串：
字符串的位置是無意義的。
假設(shè)已經(jīng)選擇一段字符串str，再選新的一個(gè)字符c；
如果字符c沒有出現(xiàn)過，那么c應(yīng)該并入str中；
如果字符c已經(jīng)出現(xiàn)過，那么新出現(xiàn)的c比原來的c更優(yōu)；
在匹配過程中，當(dāng)出現(xiàn)所有T的字符之后，一直保存最小的字符串長度。

這里可以用反證法來證明。

假設(shè)按照這一規(guī)則，選出包括所有T字符的子串s=(l, r)，最右邊的字符是c;
如果在(l, r)的位置k,k∈(l, r)，存在字符c，并且(l, k)出現(xiàn)過所有T的字符；
那么按照之前的過程(l, k)會是最小值。

** 復(fù)雜度解析：**
時(shí)間復(fù)雜度是O(N)，N是字符S的長度；
空間復(fù)雜度是O(M)，M是T的長度；

**實(shí)現(xiàn)過程： **
收獲一枚WA，沒想到題目還有這種數(shù)據(jù)：

Input:
"a"
"aa"
Output:
"a"
Expected:
""

改改即可，記錄下每個(gè)字符的數(shù)量。

123. Best Time to Buy and Sell Stock III
題目鏈接
題目大意：
給出n個(gè)數(shù)字的數(shù)組a，a[i]表示第i天股票的價(jià)格；
現(xiàn)在要求進(jìn)行最多兩次買賣：
1、不考慮購買數(shù)量，利潤就是價(jià)格差，要求買賣后利潤最大；
2、手上不能同時(shí)持有兩次股票；
3、買賣次數(shù)最多為兩次，可以為1次。

舉例：
[1,2,3,4] 利潤最大是2;（只有一個(gè)選擇1買、2賣、3買、4賣）
不能買1、2，在3、4賣。

** 題目解析：**
題目要求交易兩次，但是兩次又不能重疊。
那么可以枚舉k，[1, k]為第一次交易，[k+1, n]為第二次交易，即可解決兩次交易問題。
問題簡化成在[1, k]中交易一次，求出最值。
[1, k] 同樣可以簡化為[1, t]區(qū)間買，[t+1, k]區(qū)間賣。
但是，這樣的時(shí)間復(fù)雜度是O(N^2)，因?yàn)樾枰杜e兩次區(qū)間分隔。
實(shí)際上，這里面有很多重復(fù)的操作，比如說枚舉完k之后，在枚舉k+1的時(shí)候，有[1, k]區(qū)間的運(yùn)算是之前求過的。
那么，考慮預(yù)處理，把這些結(jié)果存下來。

leftMax[i] 表示從左邊開始，前i個(gè)的交易的最優(yōu)解；
rightMax[i] 表示從右邊開始，前i個(gè)的交易的最優(yōu)解；
這樣只需要枚舉k即可。
時(shí)間、空間復(fù)雜度O(n)；

其他解法：
動(dòng)態(tài)規(guī)劃。
因?yàn)闋顟B(tài)數(shù)非常少，直接用4個(gè)狀態(tài)來表示當(dāng)前狀態(tài)。
// 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells

139. Word Break
題目鏈接
** 題目大意：**
給出原串s，字符串?dāng)?shù)組dict，要求：
1、把s分成多個(gè)連續(xù)的子串；
2、每個(gè)子串都在dict里面；
問，是否有解。

s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

題目解析：
把一個(gè)串分成2個(gè)串的可能性有n種可能，n是字符串長度。
那么對于串[l, r] 如果[l, k] 和 [k+1, r]是合法的，那么[l, r]也是合法的。
故而用動(dòng)態(tài)規(guī)劃：
dp[i][j] 表示字符串[i, j]是否為合法的子串；
枚舉k∈[i, j] 來判斷分割字符串的位置；
轉(zhuǎn)移轉(zhuǎn)移是O（N），因?yàn)樾枰袛鄥^(qū)間[i, k]和[k+1, j]是否合法（用字典數(shù)配合）；
最后判斷dp[1, n]是否合法。

復(fù)雜度解析：
時(shí)間復(fù)雜度是O(N^3)， N^2的狀態(tài) * N的字典數(shù)判斷。
空間復(fù)雜度是O(N^{2+M)，N}2是狀態(tài)數(shù)量，M是字典數(shù)；

優(yōu)化方案：
1、dp用1維表示；dp[i] 表示前i個(gè)是否合理，轉(zhuǎn)移的時(shí)候dp[i]=dp[k] && substr(k+1, i)；
2、判斷substr是否存在時(shí)，可以用字典樹。

總結(jié)

給自己定了一個(gè)小目標(biāo)：按照ACrate排序，把第一頁所有的題目刷完。
目前已完成20題，第一頁共有50道題，任務(wù)艱巨。
按照每日一題的時(shí)間來算，大概還要一個(gè)月的時(shí)間才能做完。
剛好，是年后。

一步領(lǐng)先，步步領(lǐng)先？
都知道操作系統(tǒng)、編譯原理、網(wǎng)絡(luò)原理、數(shù)據(jù)結(jié)構(gòu)重要，但是現(xiàn)在已經(jīng)沒有毅力再去重新學(xué)一遍。
忙著面對生活與工作，偶爾的休閑時(shí)間則貢獻(xiàn)給娛樂。
這就是普通的生活。