前言
正文6道題目來(lái)自leetcode––為求職為生的編程網(wǎng)站暗甥，目的是工作閑暇之時(shí)錘煉代碼功底筹麸。
如何從這篇文章受益炕泳？
先看題目大意，對(duì)照Example的樣例理解題目意思苞七；
嘗試解答，得到自己的答案挪丢，并分析時(shí)間和空間復(fù)雜度蹂风；
思考完畢，看題目解析乾蓬，對(duì)比分析自己解法的異同和優(yōu)劣惠啄。
題目大都是LeetCode的hard難度。
正文
41.First Missing Positive
題目鏈接
題目大意：
給出一個(gè)數(shù)組任内，找到數(shù)組中沒(méi)有的最小正整數(shù)撵渡。
要求：O(N)的時(shí)間和O(1)的空間復(fù)雜度；
Example
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
** 題目解析：**
先不考慮題目要求的時(shí)間死嗦、空間復(fù)雜度趋距；
暴力的做法有兩個(gè)：
1、時(shí)間最快越除，空間不限：數(shù)組a[N]节腐，然后出現(xiàn)數(shù)字k就a[k]=1標(biāo)志出現(xiàn)；
2摘盆、時(shí)間翼雀、空間都不限：排序，遍歷一遍數(shù)組骡澈；
回到題目的要求锅纺，時(shí)間復(fù)雜度要求是O(N)，可以肯定是會(huì)用到方法1肋殴；
現(xiàn)在要求O(1)的空間復(fù)雜度囤锉，那么就必須利用上給出的數(shù)組坦弟。
遍歷數(shù)組，如果數(shù)字k小于n且非負(fù)官地，那么a[k-1]=k-1;
然后遍歷一遍酿傍，a[i] != i的就行是解。
** 復(fù)雜度解析：**
O(N)的時(shí)間和O(1)的空間復(fù)雜度驱入；
** 其他解法：**
基數(shù)排序赤炒。
從低位開(kāi)始，
當(dāng)前第i位亏较，統(tǒng)計(jì)0出現(xiàn)x次莺褒，1出現(xiàn)y次，(x+y == n)
再次掃描數(shù)組雪情，可以直接確定每個(gè)數(shù)字該排在哪里遵岩。
if bit = 0 then
idx = total_y + (total_x-left_x)
....
基數(shù)排序解法
45. Jump Game II
題目鏈接
**題目大意： **
給出一個(gè)數(shù)組，數(shù)組上的值表示能前進(jìn)的距離巡通；
現(xiàn)在從pos=0的位置向右出發(fā)尘执，問(wèn)最少需要走幾步才能到達(dá)終點(diǎn)。
Example
輸入 A = [2,3,1,1,4]
返回 2
因?yàn)榭梢詮膒os=0走到pos=1宴凉，然后直接到達(dá)pos=4誊锭；
題目解析：
第一反應(yīng)就是bfs，但是bfs需要每次判斷距離[i+1, i+k]內(nèi)的點(diǎn)是否訪問(wèn)弥锄，導(dǎo)致時(shí)間復(fù)雜度是O(N^2);
這個(gè)題也可以用動(dòng)態(tài)規(guī)劃：
dp[i]表示到達(dá)i的最短步數(shù)丧靡；
那么狀態(tài)方程可以寫成dp[i+k]=min(dp[i+k], dp[i] + 1); k∈[1, nums(i)]
這樣對(duì)于每個(gè)i都需要去更新后面nums[i]狀態(tài)，故而復(fù)雜度也是O(N^2);
對(duì)狀態(tài)轉(zhuǎn)移方程稍作修改：
dp[i] = min(dp[i], dp[k] + 1); k+num[k] >= i 且 k < i
這樣可以建一個(gè)dp[i]的優(yōu)先隊(duì)列籽暇，先按照步數(shù)排序窘行，再按能到達(dá)的距離排序；
每次從隊(duì)列的頂端拿出步數(shù)最小的dp值图仓，判斷pos的有效區(qū)間是否覆蓋當(dāng)前位置i罐盔；
如果不覆蓋，那么對(duì)i+1必然也不覆蓋救崔，可以丟棄惶看；
如果覆蓋，則直接dp[i]=dp[k]+1六孵，并把(dp[i],i+nums[i])放入優(yōu)先隊(duì)列纬黎；
復(fù)雜度是O(NlogN)。
提交后劫窒，非常遺憾的收獲TLE...
仔細(xì)觀察dp[i]的性質(zhì)本今，可以得出一個(gè)結(jié)論：
步數(shù)越大，能到達(dá)的距離就越遠(yuǎn)；
那么先建一個(gè)隊(duì)列冠息，保證步數(shù)最小的在前面挪凑，后面是步數(shù)大但是覆蓋距離較遠(yuǎn)的備選；
這樣可以O(shè)(1)取出最優(yōu)解逛艰；
并且可以設(shè)定一個(gè)maxRight躏碳，表示隊(duì)列當(dāng)前最遠(yuǎn)的覆蓋距離，如果沒(méi)有大于這個(gè)數(shù)字散怖，可以不用放入隊(duì)列菇绵；
這樣可以在O(N)的時(shí)間/空間復(fù)雜度解決問(wèn)題。
** 復(fù)雜度解析： **
O(N)的時(shí)間/空間復(fù)雜度解決問(wèn)題镇眷。
84. Largest Rectangle in Histogram
題目鏈接
** 題目大意：**
給出一個(gè)數(shù)組咬最，數(shù)組a[i]表示第i棟樓的高度；
求出最大矩形的面積欠动。
example,
Given heights = [2,1,5,6,2,3],
return 10丹诀。
題目解析：
維護(hù)一個(gè)高度不減少的棧，每次可以通過(guò)棧翁垂，快速得出面積。
** 復(fù)雜度解析：**
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是O(N)
** 代碼量：**
int largestRectangleArea(vector<int>& heights) {
int ret = 0;
heights.push_back(0);
stack<int> s;
for (int col = 0; col < heights.size(); ++col) {
while (!s.empty() && heights[col] < heights[s.top()]) {
int top = s.top();
s.pop();
int area = heights[top] * (s.empty() ? col : (col - s.top() - 1));
ret = max(ret, area);
}
s.push(col);
}
return ret;
}
85. Maximal Rectangle
題目鏈接
** 題目大意：**
給出一個(gè)01矩陣硝桩，求全為1的最大的矩形的面積沿猜；
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
** 題目解析：**
假設(shè)最后的矩形是(i, j)到(x, y)碗脊，01矩陣為n*m矩陣啼肩；
從1到n枚舉y，那么要求變成矩形貼著底邊衙伶，然后面積盡可能大祈坠。
把與底部連著的1統(tǒng)計(jì)起來(lái)，例如當(dāng)row=3的時(shí)候矢劲，分別為[3,1,3,2,2]赦拘；
此時(shí)，題目與84. Largest Rectangle in Histogram完全一致芬沉；
維護(hù)一個(gè)高度不減少的棧躺同，每次可以通過(guò)棧，快速得出面積丸逸。
** 復(fù)雜度解析：**
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是O(N)
97. Interleaving String
題目鏈接
題目大意：
給出三個(gè)字符串s1,s2,s3蹋艺；
判斷字符串s3能否由字符串s1和s2組成，要求s1的字符串內(nèi)字符的相對(duì)順序不變黄刚，s2同理捎谨。（假如s1=abc，那么在s3中，就不能變成bac涛救，相對(duì)順序必須是abc）
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
** 題目解析：**
動(dòng)態(tài)規(guī)劃畏邢。
dp[i][j] 表示s1的前i個(gè)字符，s2的前j個(gè)字符州叠，組成的字符串是否為s3的前i+j個(gè)字符棵红。
dp[0][0]=true，表示初始狀態(tài)咧栗。
假設(shè)dp[i][j]=true逆甜，那么表示s1的前i個(gè)字符，s2的前j個(gè)字符致板，與s3的前i+j個(gè)字符是匹配的交煞。
那么只要s1[i+1]==s3[i+j+1]，那么dp[i+1][j]=true;
同理斟或，有dp[i][j]=true && s2[j+1] == s3[i+j+1] => dp[i][j+1]=true
最后看dp[n][m]是否為true即可素征。
** 復(fù)雜度解析：**
時(shí)間和空間復(fù)雜度是O(NM) N是s1長(zhǎng)度，M是s2長(zhǎng)度萝挤；
*** 135. Candy ***
題目鏈接
** 題目大意：**
n個(gè)人排成一行御毅，每個(gè)人有一個(gè)rating的數(shù)值。
現(xiàn)在給所有人分配糖果怜珍，要求：
1端蛆、每個(gè)人至少有一個(gè)；
2酥泛、rating比身邊人高的分配到更多的糖果今豆。
問(wèn)最少需要多少糖果。
題目解析：
假設(shè)所有人rating一致柔袁，那么需要n個(gè)糖果呆躲；
如果有一人rating更高，那么需要n+1捶索；
如果有2人rating更高插掂，則看兩個(gè)人是否相鄰，需要n+2或n+3個(gè)糖果腥例；
以此燥筷，可以得出一種分配方案：
從最小的rating值開(kāi)始分配，每次觀看旁邊的人是否有糖果：
如果身邊人有糖果院崇，則分配max(左邊, 右邊) + 1肆氓；
如果身邊人沒(méi)有糖果，則分配1底瓣；
時(shí)間復(fù)雜度為O(NLogN)谢揪，排序耗時(shí)蕉陋。
收獲一枚TLE；
那么對(duì)算法進(jìn)行優(yōu)化拨扶。
根據(jù)分配糖果的條件2凳鬓，我們知道在一個(gè)單調(diào)遞增中：（單調(diào)遞減可以逆著看，就是單調(diào)遞增）
分配的結(jié)果是1患民、2缩举、3、4匹颤、5這樣的序列仅孩；
那么，一個(gè)數(shù)組可以分成多個(gè)單調(diào)遞增的序列印蓖；
然后反著遍歷辽慕，找到單調(diào)遞減的序列；
剩下的部分可以全部填1赦肃。
復(fù)雜度解析：
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是O(N)
總結(jié)
給自己定的小目標(biāo)50題溅蛉，因?yàn)榈谝豁?yè)某些題目質(zhì)量較低，加了一些比較容易的目前進(jìn)度33/50他宛。
