給出二維平面上的兩個正方形，找到一條直線能同時將兩個正方形都分為面積相等的兩半工碾。
一條直線只要過正方形的中心百姓，就一定會將它分為面積相等的兩半。(矩形也一樣) 那么垒拢，我們只要作一條過這兩個正方形中心點的直線， 即可同時把這兩個正方形都分為面積相等的兩半求类。
設(shè)計算法，找到質(zhì)因數(shù)只有3宴倍，5或7的第k個數(shù)。
- 初始化結(jié)果res=1和隊列q3,q5,q7
- 分別往q3,q5,q7插入13,15,1*7
- 求出三個隊列的隊頭元素中最小的那個x鸵贬，更新結(jié)果res=x
- 如果x在：
q3中，那么從q3中移除x兆衅，并向q3，q5羡亩，q7插入3x,5x,7x
q5中危融，那么從q5中移除x，并向q5吉殃，q7插入5x,7x(不往q3中插入3x，因為這個數(shù)在q5中已經(jīng)插入過了瓦灶，eg:53插過35)
q7中，那么從q7中移除x贼陶，并向q7插入7*x - 重復步驟3－5巧娱，直到找到第k個滿足條件的數(shù)
線性求k最大
線性求k最大利用的是快排中的partition函數(shù)。每次選取一個基準元素pivot (可以用第1個元素家卖，也可以隨機選)庙楚，然后將其它元素與pivot對比。大于等于pivot 的放到左邊馒闷，小于pivot的放到右邊。調(diào)用一次partition后逛薇， pivot左邊的數(shù)都是大于等于它的疏虫，pivot右邊的數(shù)都是小于它的啤呼。 如果pivot此時正好是第k-1個元素，那么它左邊加上它一共有k個元素官扣， 而且這k個元素都是比右邊的元素要大的羞福，即它們就是最大的k個元素。如果pivot 左邊不足k-1個元素治专，則在它右邊進行同樣的partition操作。如果pivot 左邊是多于k-1個元素的张峰，則在它左邊進行partition操作。
該算法會改變數(shù)組中元素的順序喘批，期望時間復雜度是O(n)。
寫一個程序谤祖，找到由其它單詞組成的最長單詞婿滓。
按單詞的長度從大到小排序粥喜。(先尋找最長的單詞)
不斷地取單詞的前綴s，當s存在于單詞數(shù)組中额湘，遞歸調(diào)用該函數(shù)， 判斷剩余串是否可以由其它單詞組成嗡官。如果可以毯焕，返回true衍腥。
隨機產(chǎn)生一些數(shù)傳遞給一個函數(shù)纳猫，寫程序找出并維護這些數(shù)的中位數(shù)。
中位數(shù)有一個性質(zhì)芜辕，它平分了小于他的元素和大于他的元素，然后我們現(xiàn)在要動態(tài)加入新的元素倔丈。 新加入的元素，我們要怎么辦呢需五？我們希望把元素分成兩個集合A和B，使得滿足以下兩個性質(zhì)：
A中元素均小于等于B中元素
A中的元素和B中元素一樣多或只多一個训裆。
如此，我們可以在log n時間內(nèi)給出中位數(shù)边琉，因為中位數(shù)要么是A的最大值记劝，要么是A的最大值和B的最小值的平均值。同時我們也可以在log n時間加入一個新的元素并維持這兩個性質(zhì)：先把新元素加入A厌丑，然后把A的最大值移動到B使性質(zhì)1滿足，然后判斷A和B的大锌仇（如果Size A小于B則把B中最小元移入A）使性質(zhì)2滿足耕驰。
堆可以完美的完成上述操作爷辱，當然也可以用平衡二叉樹解決朦肘，但是平衡樹編寫復雜，面試中不建議也需要實現(xiàn)此類數(shù)據(jù)結(jié)構(gòu)弟断。我們還是要用到堆這個在面試中容易出現(xiàn)趴生，編寫難度不大又很實用的數(shù)據(jù)結(jié)構(gòu)。我們維護一個大根堆P（根節(jié)點值最大）和一個小根堆Q（根節(jié)點值最谐寤唷），對應集合A和B锉桑，維護上述兩個性質(zhì)即可窍株。
最大子矩陣和
O(nnm)正在思考有沒有更優(yōu)的攻柠。
循環(huán)i,j后裸，b[k]為原矩陣第k列從i到j行的數(shù)字和，b[k]這一維用dp，sum<0時晤硕，sum = b[k]棋弥，or sum = max(sum,sum+b[k]）
