前言
正文6道題目來自leetcode––為求職為生的編程網(wǎng)站森渐，目的是工作閑暇之時錘煉代碼功底劳曹。
沒有捷徑妓灌，但手熟爾；
一步領(lǐng)先晨汹，步步領(lǐng)先。
正文
5. Longest Palindromic Substring
題目鏈接
題目大意：
輸入一個回文串贷盲，輸出長度最長的回文子串淘这；
如果有多個答案，輸出任意一個巩剖。
Example
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
** 題目解析：**
模板題铝穷，有現(xiàn)成的解法。
求回文串有O(N)的算法佳魔，詳見manacher解析曙聂。
** 復(fù)雜度解析：**
空間、時間復(fù)雜度都是O(N)鞠鲜， N是字符串的長度宁脊；
** 其他解法：**
暴力，從每個點開始枚舉贤姆，判斷最長的回文子串榆苞，O(N^2);
kmp，回文串s和s的轉(zhuǎn)置是一樣的霞捡，那么可以把原串s和s'進行匹配语稠，判斷區(qū)間是否合法；（有可能存在匹配弄砍，但是區(qū)間不重疊的情況）
30. Substring with Concatenation of All Words
題目鏈接
***題目大意： ***
給出一個字符串s仙畦，一個字符列表words，words內(nèi)的單詞都是同一長度音婶，找到一個區(qū)間慨畸，要求：
1、區(qū)間內(nèi)的字符串衣式，可以切分成若干個連續(xù)的子串寸士，每個子串都是words的單詞檐什；
2、每個單詞只出現(xiàn)一次弱卡；
輸出所有可能的區(qū)間的起點乃正。
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
題目解析：
題目提供了一個了一個不可忽視的限制，所有的words是同一長度婶博，這樣就避免了fool和foo的情況瓮具；
并且在判斷s的子串是否出現(xiàn)時，可以直接截取長度為m的字符串凡人。
這樣流程就變成：
1名党、初始位置s，截取m個字符str挠轴，查詢str是否在words中传睹，如果在則判斷下m個字符；
2岸晦、如果不在words中欧啤，則回溯到最初的位置s，從s+1開始判斷启上。
但是邢隧， 這樣的復(fù)雜度會很高，因為回溯之后又要從原來的位置的下一個開始匹配碧绞。
有一種優(yōu)化方案：假設(shè)len為words字符串的統(tǒng)一長度府框；
從0,1,2...到len-1，分別匹配一次即可讥邻。
這樣可以采取一種策略迫靖，當(l, r)的字符串最后len個字符匹配失敗后，直接從r+1的位置匹配兴使；因為(r-len,r)的字符不存在words中系宜；
如果(r-len, r)在之前已經(jīng)在k出現(xiàn)過，則可以把左邊界移到k+1发魄，直到遇到右邊界盹牧；
可以在len次枚舉后得到結(jié)果。
** 復(fù)雜度解析： **
時間復(fù)雜度是O(N*len)励幼，len為words中單詞的長度汰寓。
空間復(fù)雜度是O(M*len)，hash的空間復(fù)雜度較高苹粟；
** 其他解法：**
有稍微慢一點有滑，但是代碼量很小的做法。
僅需20行嵌削。
詳見這里
56. Merge Intervals
題目鏈接
** 題目大意：**
給出n個數(shù)字區(qū)間毛好，把有相交的區(qū)間合并起來望艺。
example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
題目解析：
區(qū)間合并只需考慮最左和最右的邊界。
先排序肌访，把可能合并到區(qū)間集合在一起找默。
容易知道如果前面區(qū)間的right >= 當前區(qū)間的left 的時候，是可以合并的吼驶。
那么遍歷一遍惩激，判斷邊界是否相交即可。
** 復(fù)雜度解析：**
時間復(fù)雜度是O(NlogN)旨剥，N是區(qū)間個數(shù)（時間都在排序上）咧欣；
空間復(fù)雜度是O(N)浅缸，有可能返回N個結(jié)果轨帜。
** 代碼量：**
比較函數(shù)有簡單寫法。
sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
76. Minimum Window Substring
題目鏈接
** 題目大意：**
給出兩個字符串S和T衩椒，在S中尋找一個子串s蚌父，要求：
1、s包括T出現(xiàn)過的所有字符毛萌；
2苟弛、s的字符串長度最小阁将；
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
如果沒有膏秫，返回空串；
題目保證只有一個答案做盅。
** 題目解析：**
題目要求s出現(xiàn)T中所有的字符缤削，但是沒有順序要求，那么對于一段字符串：
字符串的位置是無意義的吹榴。
假設(shè)已經(jīng)選擇一段字符串str亭敢，再選新的一個字符c；
如果字符c沒有出現(xiàn)過图筹，那么c應(yīng)該并入str中帅刀；
如果字符c已經(jīng)出現(xiàn)過，那么新出現(xiàn)的c比原來的c更優(yōu)远剩；
在匹配過程中扣溺，當出現(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ù)雜度解析：**
時間復(fù)雜度是O(N)蛔钙，N是字符S的長度；
空間復(fù)雜度是O(M)荠医，M是T的長度吁脱；
**實現(xiàn)過程： **
收獲一枚WA，沒想到題目還有這種數(shù)據(jù)：
Input:
"a"
"aa"
Output:
"a"
Expected:
""
改改即可彬向，記錄下每個字符的數(shù)量兼贡。
123. Best Time to Buy and Sell Stock III
題目鏈接
題目大意：
給出n個數(shù)字的數(shù)組a，a[i]表示第i天股票的價格娃胆；
現(xiàn)在要求進行最多兩次買賣：
1遍希、不考慮購買數(shù)量，利潤就是價格差里烦，要求買賣后利潤最大凿蒜；
2、手上不能同時持有兩次股票胁黑；
3废封、買賣次數(shù)最多為兩次，可以為1次丧蘸。
舉例：
[1,2,3,4] 利潤最大是2;（只有一個選擇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ū)間賣。
但是，這樣的時間復(fù)雜度是O(N^2)于样，因為需要枚舉兩次區(qū)間分隔疏叨。
實際上，這里面有很多重復(fù)的操作穿剖，比如說枚舉完k之后蚤蔓，在枚舉k+1的時候，有[1, k]區(qū)間的運算是之前求過的糊余。
那么秀又，考慮預(yù)處理，把這些結(jié)果存下來贬芥。
leftMax[i] 表示從左邊開始吐辙，前i個的交易的最優(yōu)解；
rightMax[i] 表示從右邊開始蘸劈，前i個的交易的最優(yōu)解昏苏；
這樣只需要枚舉k即可。
時間昵时、空間復(fù)雜度O(n)捷雕；
其他解法：
動態(tài)規(guī)劃椒丧。
因為狀態(tài)數(shù)非常少壹甥，直接用4個狀態(tài)來表示當前狀態(tài)。
// 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
139. Word Break
題目鏈接
** 題目大意：**
給出原串s壶熏，字符串數(shù)組dict句柠，要求：
1、把s分成多個連續(xù)的子串棒假；
2溯职、每個子串都在dict里面；
問帽哑，是否有解谜酒。
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
題目解析：
把一個串分成2個串的可能性有n種可能，n是字符串長度妻枕。
那么對于串[l, r] 如果[l, k] 和 [k+1, r]是合法的僻族，那么[l, r]也是合法的。
故而用動態(tài)規(guī)劃：
dp[i][j] 表示字符串[i, j]是否為合法的子串屡谐；
枚舉k∈[i, j] 來判斷分割字符串的位置述么；
轉(zhuǎn)移轉(zhuǎn)移是O（N），因為需要判斷區(qū)間[i, k]和[k+1, j]是否合法（用字典數(shù)配合）愕掏；
最后判斷dp[1, n]是否合法度秘。
復(fù)雜度解析：
時間復(fù)雜度是O(N^3)， N^2的狀態(tài) * N的字典數(shù)判斷饵撑。
空間復(fù)雜度是O(N2+M)剑梳，N2是狀態(tài)數(shù)量唆貌，M是字典數(shù)；
優(yōu)化方案：
1垢乙、dp用1維表示挠锥；dp[i] 表示前i個是否合理，轉(zhuǎn)移的時候dp[i]=dp[k] && substr(k+1, i)侨赡；
2蓖租、判斷substr是否存在時，可以用字典樹羊壹。
總結(jié)
給自己定了一個小目標：按照ACrate排序蓖宦，把第一頁所有的題目刷完。
目前已完成20題油猫，第一頁共有50道題稠茂，任務(wù)艱巨。
按照每日一題的時間來算情妖，大概還要一個月的時間才能做完睬关。
剛好，是年后毡证。
一步領(lǐng)先电爹，步步領(lǐng)先？
都知道操作系統(tǒng)料睛、編譯原理丐箩、網(wǎng)絡(luò)原理、數(shù)據(jù)結(jié)構(gòu)重要恤煞，但是現(xiàn)在已經(jīng)沒有毅力再去重新學(xué)一遍屎勘。
忙著面對生活與工作，偶爾的休閑時間則貢獻給娛樂居扒。
這就是普通的生活概漱。
