重要參考鏈接[https://juejin.im/post/58ca051f61ff4b0060165122]
堆與棧(http://blog.csdn.net/hairetz/article/details/4141043/)
棧區(qū)（stack）由編譯器自動分配釋放，存放方法（函數(shù)）的參數(shù)值佩捞，局部變量的值等整胃。
堆區(qū)（heap）一般由程序員分配與釋放李破，若程序員不釋放绿满，則會內(nèi)存溢出遮糖。
棧：只要棧的剩余空間大于所申請空間，系統(tǒng)將為程序提供內(nèi)存孽亲，否則將報異常提示棧溢出慧妄。
堆：首先應該知道操作系統(tǒng)有一個記錄空閑內(nèi)存地址的鏈表顷牌，當系統(tǒng)收到程序的申請時，會遍歷該鏈表塞淹，尋找第一個空間大于所申請空間的堆結(jié)點窟蓝，然后將該結(jié)點從空閑結(jié)點鏈表中刪除，并將該結(jié)點的空間分配給程序窖铡，另外疗锐，對于大多數(shù)系統(tǒng)坊谁，會在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣滑臊，代碼中的delete語句才能正確的釋放本內(nèi)存空間口芍。
另外，由于找到的堆結(jié)點的大小不一定正好等于申請的大小雇卷，系統(tǒng)會自動的將多余的那部分重新放入空閑鏈表中鬓椭。
棧：在Windows下,棧是向低地址擴展的數(shù)據(jù)結(jié)構，是一塊連續(xù)的內(nèi)存的區(qū)域关划。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預先規(guī)定好的小染，在WINDOWS下，棧的大小是2M（也有的說是1M贮折，總之是一個編譯時就確定的常數(shù)）裤翩，如果申請的空間超過棧的剩余空間時，將提示overflow调榄。因此踊赠，能從棧獲得的空間較小。
堆：堆是向高地址擴展的數(shù)據(jù)結(jié)構每庆，是不連續(xù)的內(nèi)存區(qū)域筐带。這是由于系統(tǒng)是用鏈表來存儲的空閑內(nèi)存地址的，自然是不連續(xù)的缤灵，而鏈表的遍歷方向是由低地址向高地址伦籍。堆的大小受限于計算機系統(tǒng)中有效的虛擬內(nèi)存。由此可見腮出，堆獲得的空間比較靈活帖鸦，也比較大。
hashmap的基礎數(shù)據(jù)結(jié)構
HashMap基于hashing原理利诺，我們通過put()和get()方法儲存和獲取對象富蓄。當我們將鍵值對傳遞給put()方法時剩燥，它調(diào)用鍵對象的hashCode()方法來計算hashcode慢逾，讓后找到bucket位置來儲存值對象。當獲取對象時灭红，通過鍵對象的equals()方法找到正確的鍵值對侣滩，然后返回值對象。HashMap使用LinkedList來解決碰撞問題变擒，當發(fā)生碰撞了君珠，對象將會儲存在LinkedList的下一個節(jié)點中。 HashMap在每個LinkedList節(jié)點中儲存鍵值對對象娇斑。
循環(huán)隊列
循環(huán)隊列的優(yōu)點：
可以有效的利用資源策添。用數(shù)組實現(xiàn)隊列時材部，如果不移動，隨著數(shù)據(jù)的不斷讀寫唯竹，會出現(xiàn)假滿隊列的情況乐导。即尾數(shù)組已滿但頭數(shù)組還是空的；循環(huán)隊列也是一種數(shù)組浸颓，只是它在邏輯上把數(shù)組的頭和尾相連物臂，形成循環(huán)隊列，當數(shù)組尾滿的時候产上，要判斷數(shù)組頭是否為空棵磷，不為空繼續(xù)存放數(shù)據(jù)。
循環(huán)隊列的缺點：
循環(huán)隊列中晋涣，由于入隊時尾指針向前追趕頭指針仪媒；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等谢鹊。因此规丽，無法通過條件front==rear來判別隊列是"空"是"滿"。
解決這個問題有兩個辦法：一是增加一個參數(shù)撇贺，用來記錄數(shù)組中當前元素的個數(shù)赌莺；第二個辦法是，少用一個存儲空間松嘶，也就是數(shù)組的最后一個存數(shù)空間不用艘狭，當（rear+1）%maxsiz=front時，隊列滿
棧結(jié)構與隊列的區(qū)別翠订？
棧（stack）：限定只能在表的一端進行插入和刪除操作的線性表巢音。
隊列（queue）：限定只能在表的一端插入和在另一端進行刪除操作的線性表。
1）隊列先進先出尽超，棧先進后出官撼。
2）對插入和刪除操作的“限定”不同。
3）遍歷數(shù)據(jù)速度不同似谁。隊列遍歷數(shù)據(jù)的速度要快得多傲绣。
二叉樹的深度優(yōu)先遍歷(遞歸與非遞歸（非遞歸后序最難））
寫出一次快排后的具體變化情況
什么是紅黑樹。
紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹巩踏，顏色或紅色或黑色秃诵。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:
性質(zhì)1. 節(jié)點是紅色或黑色塞琼。
性質(zhì)2. 根節(jié)點是黑色菠净。
性質(zhì)3 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
性質(zhì)4 每個紅色節(jié)點的兩個子節(jié)點都是黑色毅往。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
性質(zhì)5. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點牵咙。
這些約束強制了紅黑樹的關鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的攀唯。因為操作比如插入霜大、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的革答，而不同于普通的二叉查找樹战坤。
紅黑樹的插入和刪除
寫一個快排。
Quick Sort是目前已知最快的排序法残拐，平均復雜度為O(NlogN)途茫，可是最壞情況下將達O(N^2)。
Quick Sort算法可以敘述如下溪食。假設S代表將被處理的序列：
1囊卜、如果S的元素個數(shù)為0或1，結(jié)束错沃。
2栅组、取S中的任何一個元素，當做樞軸(pivot) v枢析。
3玉掸、將S分割為L、R兩段醒叁，使L內(nèi)的每一個元素都小于或等于v司浪，R內(nèi)的每一個元素都大于或等于v。
4把沼、對L啊易、R遞歸執(zhí)行Quick Sort。
一個單鏈表怎么判斷有沒有環(huán)饮睬？環(huán)的起點怎么找租谈？ 如何找出環(huán)的連接點在哪里？帶環(huán)鏈表的長度是多少捆愁？
1割去、對于問題1，使用追趕的方法牙瓢，設定兩個指針slow劫拗、fast间校，從頭指針開始矾克，每次分別前進1步、2步憔足。如存在環(huán)胁附，則兩者相遇酒繁；如不存在環(huán)，fast遇到NULL退出控妻。
2州袒、對于問題2，記錄下問題1的碰撞點p弓候，slow郎哭、fast從該點開始，再次碰撞所走過的操作數(shù)就是環(huán)的長度s菇存。
3夸研、問題3：有定理：碰撞點p到連接點的距離=頭指針到連接點的距離，因此依鸥，分別從碰撞點亥至、頭指針開始走，相遇的那個點就是連接點贱迟。
該定理的證明可參考：http://fayaa.com/tiku/view/7/
4姐扮、問題3中已經(jīng)求出連接點距離頭指針的長度，加上問題2中求出的環(huán)的長度衣吠，二者之和就是帶環(huán)單鏈表的長度
哈希表解決沖突的方法
開放定址法（當關鍵字key的哈希地址p=H（key）出現(xiàn)沖突時茶敏，以p為基礎，產(chǎn)生另一個哈希地址p1缚俏，如果p1仍然沖突睡榆，再以p為基礎，產(chǎn)生另一個哈希地址p2袍榆，…胀屿，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中包雀，線性探測再散列宿崭，二次探測再散列，偽隨機探測再散列）
再哈希法（這種方法是同時構造多個不同的哈希函數(shù)）
鏈地址法（這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表）
建立一個公共溢出區(qū)（將哈希表分為基本表和溢出表兩部分才写，凡是和基本表發(fā)生沖突的元素葡兑，一律填入溢出表）
散列表查找的復雜度
O（1）
動態(tài)規(guī)劃，最長公共子串等 最長遞增子序列（nlogn的算法）
[http://blog.csdn.net/joylnwang/article/details/6766317]
排序：快排赞草、歸并讹堤、堆，時間復雜度是一樣的厨疙，有什么區(qū)別洲守？為什么平均情況下快排最快？
給定一棵樹，除左右節(jié)點外梗醇，還有一個random域知允，不一定指向哪，可能是空節(jié)點叙谨，可能是樹中的其他節(jié)點温鸽，做樹拷貝。
大整數(shù)加手负、減涤垫、乘、除竟终、求模運算實現(xiàn)
二叉查找
二叉搜索樹
Top(k)
1.將輸入內(nèi)容（假設用數(shù)組存放）進行完全排序雹姊，從中選出排在前K的元素即為所求。有了這個思路衡楞，我們可以選擇相應的排序算法進行處理吱雏，目前來看快速排序，堆排序和歸并排序都能達到O(nlogn)的時間復雜度瘾境。
2.對輸入內(nèi)容進行部分排序歧杏，即只對前K大的元素進行排序（這K個元素即為所求）。此時我們可以選擇冒泡排序或選擇排序進行處理迷守，即每次冒泡（選擇）都能找到所求的一個元素犬绒。這類策略的時間復雜度是O(Kn)。
3.對輸入內(nèi)容不進行排序兑凿，顯而易見凯力，這種策略將會有更好的性能開銷。我們此時可以選擇兩種策略進行處理：
a)利用小根堆維護一個大小為K的數(shù)組礼华，目前該小根堆中的元素是排名前K的數(shù)咐鹤，其中根是最小的數(shù)。此后圣絮，每次從原數(shù)組中取一個元素與根進行比較祈惶，如大于根的元素，則將根元素替換并進行堆調(diào)整（下沉）扮匠，即保證小根堆中的元素仍然是排名前K的數(shù)捧请，且根元素仍然最小棒搜；否則不予處理疹蛉，取下一個數(shù)組元素繼續(xù)該過程。該算法的時間復雜度是O(nlogK)力麸，一般來說企業(yè)中都采用該策略處理top-K問題可款，因為該算法不需要一次將原數(shù)組中的內(nèi)容全部加載到內(nèi)存中育韩，而這正是海量數(shù)據(jù)處理必然會面臨的一個關卡。
b)利用快速排序的分劃函數(shù)找到分劃位置K筑舅，則其前面的內(nèi)容即為所求座慰。該算法是一種非常有效的處理方式陨舱，時間復雜度是O(n)翠拣。對于能一次加載到內(nèi)存中的數(shù)組，該策略非常優(yōu)秀游盲。
單鏈表翻轉(zhuǎn)（兩個指針如何實現(xiàn)）误墓、查找、刪除益缎、插入以及雙向鏈表谜慌、有序鏈表合并
判斷一個整數(shù)是否是2的整數(shù)次冪.
(n&(n-1))
數(shù)組中只有一個數(shù)出現(xiàn)了兩次，求這個數(shù)莺奔，并使得空間效率最優(yōu)（用位圖bitmap欣范，比O（n）的線性空間更優(yōu)）
位運算
利用異或的特性，xyx=yxx=y
二分查找（注意邊界條件）
二分查找算法的填空（PS：注意陷阱：數(shù)會溢出的問題）定中間值的時候?qū)戝e了 mind = low+high/2 令哟，后面回來一查恼琼，說這樣子會溢出 low+high 會越界溢出，查閱相關資料 mind = low+（high-low）>>1屏富，這樣 才可以晴竞，果然，哪里有這么簡單的題目…注意陷阱……
常見排序算法的實現(xiàn)以及穩(wěn)定性（快排跟歸并考的很多）
字符串翻轉(zhuǎn)（O(n)）狠半、匹配（KMP算法）
指定一個數(shù)組噩死，求2個數(shù)的和等于指定的和（某一個數(shù)），如果是3,4,5神年，n個等于個的和（某一個數(shù)）呢已维？（可以看作背包問題）
跳臺階問題
一堆數(shù)據(jù)怎么找中位數(shù)（分兩種，內(nèi)寸是不是能一次裝下所用數(shù)據(jù)已日，能的話用快排衣摩，不能用分桶）
[http://blog.csdn.net/jiyanfeng1/article/details/8088237]
找出一個字符串中只出現(xiàn)一次且是第一個的字符
建立一個hash表，遍歷一遍字符串捂敌，記錄每個字符出現(xiàn)的次數(shù)
在不使用額外空間的情況下艾扮，交換兩個數(shù)？
位操作（異或）或者加減
呼呼呼山
18 Sep 2017 9:04 PM
