第4次面試算法講座課件

1、曹鵬2013-11-24第4次 算法 & 面試 講座何為O(N)? N是什么？單調(diào)隊列單調(diào)堆棧二叉樹遍歷（前、中、后）楊氏矩陣查找快排partition及變形荷蘭國旗第一個缺失的正整數(shù)（排列判斷）如果hash是O(1)2-sum最長無重復(fù)字符的子串字符串（KMP） 最長回文子串前綴相關(guān)題外話公司一般沒有自己的題庫，即使有，面試官也有權(quán)自己選擇問題面試成功 = 實力 + 運氣靈活掌握，千萬別背題！普通堆棧例1 判斷括號是否合法輸入只有6種字符的字符串，( ) 判斷字符是否合法？左括號入棧，右左括號看棧頂？Match就出棧，否則就錯誤。例2 數(shù)軸上一群魚，從左到右的順序知道每條魚游動的方向（正負(fù)）

2、，每條魚的速度相同，但大小都不同，如果大小魚相遇，小魚被吃掉，問最后剩幾條魚？掃一遍，遇到正方向入棧，負(fù)方向出棧直到一條被吃掉或者棧為空。單調(diào)隊列例3 一個隊列，每次進入一個數(shù)，不斷查詢求最近k個數(shù)的最大值？本質(zhì)：對于一個新數(shù)x，則比它舊的且不超過它的數(shù)是沒有用的。算法：如果新來一個數(shù)，把過期的扔掉，把比這個數(shù)舊的并且不超過它的數(shù)都扔掉。隊列里的數(shù)是嚴(yán)格單調(diào)遞減的。隊首永遠(yuǎn)是最大值。單調(diào)隊列樣例例如K = 2, 數(shù)字是 4,5,3,2,7,8,1新數(shù)隊列4454，535, 3 4過期23，2 5過期77 3過期，2比7小88 7比8小18，1單調(diào)隊列的應(yīng)用例4 給定一個數(shù)組和兩個整數(shù)s=x?把

3、數(shù)列改一下:ai = ai xsumi的定義不變：對每個sumisumi sumi t, sumi sumi- t + 1,sumi sumi s的最大值是否大于等于0?求等價于sumi-t, sumi t + 1,sumi s的最大值單調(diào)隊列！算上二分的復(fù)雜度O(NlogM) 單調(diào)堆棧例4 直方圖最大面積矩形用堆棧對每一塊找到它能延伸的左右邊界對每一塊堆棧頂矮，這一塊左邊界確定，入堆棧頂高，堆棧頂右邊界確定，出入棧時左邊界確定出棧時右邊界確定堆棧里的是遞增的本質(zhì)：中間的短板沒有用！復(fù)雜度 O(n)單調(diào)堆棧2，1，5，6，2，3 新數(shù)堆棧說明H0 =222入棧,左邊界(-1)H1 = 112出

4、棧，右邊（1），1入棧，左邊界(0) H2 = 55,15入棧 ，左邊界（1）H3 = 66，5，16入棧，左邊邊界（2）H4 = 22,16，5出棧，右邊界（4），2入棧左邊界（1）H5 = 33,2,13入棧，左邊界(4)H6 = 03,2,1,出棧 右邊界（6）單調(diào)堆棧數(shù)據(jù)左右邊界面積H0 =2（-1，1）2H1 = 1（0， 6）5H2 = 5（1，4）10H3 = 6（2，4)6H4 = 2(1,6)8H5 = 3(4,6)3圖的遍歷普通圖的遍歷O(m), O(n2)樹的遍歷 O(n)二叉樹的遍歷 O(n)在遍歷的時候，我們可以得到很多信息樹的高度，節(jié)點最大（?。┲担瑥母皆摴?jié)點的數(shù)

5、字和？二叉樹的遍歷例5 判斷二叉樹是否相同？楊氏矩陣查找例6 在行列都單增的矩陣?yán)锊檎乙粋€數(shù)。查找9， 15-11-7-8-9思考： （非線性） 查找有幾個正數(shù)？T(m * n) = T(0.75 * m * n) + O(1)簡單地掃描例7： 荷蘭國旗問題一個數(shù)組，只有0,1,2，給它排好序？循環(huán)不變式:0.p是0，q.n 1是2,p + 1.i 1是1簡單地掃描例8 （排列判斷）整數(shù)數(shù)組，返回從1開始第一個不在數(shù)組中得整數(shù)？把Ai換到AAi 1的位置即可兩頭掃2-SUM例9 2-SUM，一個數(shù)組，找到其中兩個值，使其和為給定的值X。一般做法： 要排好序，兩頭掃。如果hash是O(1),則2

6、-SUM 可以在O(N)時間內(nèi)解決?？梢韵葤咭槐槎既舆Munordered_map,再對每個數(shù)查找一遍X ai。復(fù)雜度O(N)。掃描的問題例10 給定數(shù)組，選擇連個下標(biāo)i,j滿足ai aj的前提下j i盡可能大。如果一個數(shù)左邊有小于等于它的，它不可能作為i。我們可以從左到右掃一遍，同時記錄左邊的最小值，把可以作為i的保存下來，放入堆棧。注意堆棧的值越靠頂越小。從右向左掃瞄可能的j。彈出i。繼續(xù)掃。復(fù)雜度O(n)。掃描的問題例如 4，3，5，2，1，3，2，3可能的i有4,3,5,2,1,3,2,3然后從右到左掃描 j，對每個j，找到盡可能左的i。堆棧里彈出的是已經(jīng)找到盡可能大的j了，所以不會再后面考慮了。掃描的問題例11 x軸上每個位置有一棵樹直向上的直線，以數(shù)值的直線為邊界，中間的部分當(dāng)做一個容器，問最多能盛多少水？ 兩個軸位置i j注意現(xiàn)在一定有xj 0)表示從i開始的字符串和原串能匹配的最長前綴長度。能否O(n)求出pi?套用Manacher算法，假設(shè)p1.i 1都已經(jīng)算好了，原先框最右邊界是right，該框?qū)?yīng)的左邊界是left。 我們要計算pi,前綴相關(guān)的算法（1） 如果right = i，即i被框住了，i的位置相當(dāng)于原串的開頭的什么位置？ i = i left!我們看看pi由p的定義，注意，在框內(nèi)的部分i和i往后都