西電面試算法講座演示文稿

西電面試算法講座演示文稿當(dāng)前第1頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)優(yōu)選西電面試算法講座當(dāng)前第2頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)以前的不足對(duì)著PPT一本正經(jīng)念到底堆砌知識(shí)、沒有要害100頁(yè)P(yáng)PTPPT上字多、不夠一目了然體力不支、互動(dòng)太少當(dāng)前第3頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)第一部分、面試當(dāng)前第4頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)筆試面試考什么當(dāng)前第5頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)筆試偏基礎(chǔ)語(yǔ)言基礎(chǔ)inthope;int*hope;double(*p)[3];void(*func)();操作系統(tǒng)線程與進(jìn)程的區(qū)別產(chǎn)生死鎖的條件如何規(guī)避死鎖C++內(nèi)存分配堆、棧、自由存儲(chǔ)區(qū)、全局/靜態(tài)存儲(chǔ)區(qū)，常量存儲(chǔ)區(qū)網(wǎng)絡(luò)協(xié)議TCP建立連接的三次握手?jǐn)?shù)據(jù)庫(kù)概率論與數(shù)理統(tǒng)計(jì)推薦《數(shù)理統(tǒng)計(jì)學(xué)簡(jiǎn)史》當(dāng)前第6頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)面試偏算法數(shù)據(jù)結(jié)構(gòu)上的增刪改查查找、遍歷、排序算法分治、遞歸、回溯貪心、動(dòng)態(tài)規(guī)劃海量數(shù)據(jù)處理當(dāng)前第7頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)基于各個(gè)數(shù)據(jù)結(jié)構(gòu)上的增刪改查字符串字符串庫(kù)函數(shù)的編寫，例如atoi等字符串查找、翻轉(zhuǎn)、匹配數(shù)組查找（如二分查找、楊氏矩陣查找）鏈表翻轉(zhuǎn)、遍歷、查找、刪除、合并Hash表查找樹遍歷（前序、中序、后序）set、map高級(jí)樹的查找（紅黑樹、B樹、R樹）圖遍歷查找（DFS、BFS）最短路徑算法當(dāng)前第8頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)知道了考什么，怎么破當(dāng)前第9頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)筆試面試常用算法窮舉（遞歸回溯）——“萬(wàn)能的”求n個(gè)數(shù)的全排列&8皇后（N皇后問題）分治分而治之，然后歸并遞歸回溯DFS空間換時(shí)間hashtable巧用數(shù)據(jù)結(jié)構(gòu)堆能排序，考慮排序前后兩個(gè)指針往中間掃若已經(jīng)排好序，想想有無(wú)必要二分不能排序貪心最小生成樹Prim,Krusal最短路dijkstra動(dòng)態(tài)規(guī)劃如01背包問題，每一步都在決策細(xì)節(jié)處理注意邊界條件當(dāng)前第10頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)各類算法的時(shí)間復(fù)雜度當(dāng)前第11頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)O(1)到O(nlogn)O(1)基本運(yùn)算，＋，－，＊，／，%，尋址Hash表的期望復(fù)雜度O(logn)二分查找O(n1/2)枚舉約數(shù)O(n)線性查找建立堆O(nlogn)歸并排序快速排序的期望復(fù)雜度基于比較排序的算法下界當(dāng)前第12頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)O(n2)到O(nn)O(n2)集合里枚舉所有二元組、樸素最近點(diǎn)對(duì)O(n3)集合里枚舉三元組、Floyd最短路、普通矩陣乘法O(2n)枚舉全部的子集O（2nn)TSP的動(dòng)態(tài)規(guī)劃算法O(n!)枚舉全排列O(nn)枚舉[1..n]的n維數(shù)組的全部元素……總結(jié)O(1)<O(logn)<O(n1/2)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O（2nn)<O(n!)<O(nn)當(dāng)前第13頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)各種排序算法的時(shí)間復(fù)雜度當(dāng)前第14頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)O(N)的時(shí)間復(fù)雜度能解決什么問題？當(dāng)前第15頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)O(N)時(shí)間內(nèi)能解決的問題字符串字符串循環(huán)位移最長(zhǎng)回文子串?dāng)?shù)組尋找最小的K個(gè)數(shù)2-sum最大連續(xù)子數(shù)組和快排的partition奇偶排序荷蘭國(guó)旗問題完美洗牌問題最大面積直方圖最大連續(xù)乘積子數(shù)組查找排序楊氏矩陣查找出現(xiàn)次數(shù)超過一半的數(shù)字建立堆計(jì)數(shù)排序二叉查找樹的前中后序遍歷ManacherKMP當(dāng)前第16頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)字符串翻轉(zhuǎn)把字符串a(chǎn)bcdef左旋轉(zhuǎn)3位得到字符串defabc。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。暴力移位三步翻轉(zhuǎn)（字符串a(chǎn)bcdef->defabc）X：abc，Y：def；X->X^T，得：abc->cba；Y->Y^T，得：def->fedX^TY^T，得到：cbafed->defabc，即(X^TY^T)^T=YX當(dāng)前第17頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)尋找最小的k個(gè)數(shù)輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字請(qǐng)輸出其中最小的4個(gè)數(shù)字：1，2，3和4當(dāng)前第18頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)尋找和為定值的兩個(gè)數(shù)輸入數(shù)組1、2、4、7、11、15和數(shù)字15由于4+11=15，因此輸出4和11解答：百試不厭：暴力窮舉如果無(wú)序，先排序，排完序后，ij前后兩個(gè)指針往中間掃當(dāng)前第19頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)編程藝術(shù)github當(dāng)前第20頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)第二部分、算法當(dāng)前第21頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)如何學(xué)習(xí)算法？當(dāng)前第22頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)算法學(xué)習(xí)方法論基礎(chǔ)很重要學(xué)習(xí)什么，心中有大綱算法解決什么問題，解決策略是什么廣搜一層一層往外遍歷，尋找最短路徑策略：隊(duì)列最小生成樹最小代價(jià)連接所有點(diǎn)策略：貪心（Prim：貪心+權(quán)重隊(duì)列）Dijkstra尋找單源最短路徑策略：貪心+非負(fù)權(quán)重隊(duì)列Floyd多結(jié)點(diǎn)對(duì)的最短路徑策略：動(dòng)態(tài)規(guī)劃方法論循序漸進(jìn)對(duì)比聯(lián)系從簡(jiǎn)單入手，追本溯源當(dāng)前第23頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)如何學(xué)習(xí)算法之一要?jiǎng)t一：循序漸進(jìn)KMP當(dāng)前第24頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)有一個(gè)算法，本科期間無(wú)數(shù)人被虐過，是哪個(gè)算法？當(dāng)前第25頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)字符串的查找匹配有一個(gè)文本串S和一個(gè)模式串P請(qǐng)查找P在S中的位置當(dāng)前第26頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)暴力！一步步往后匹配當(dāng)前第27頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)繼續(xù)暴力匹配失敗，回溯當(dāng)前第28頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)改進(jìn)暴力！利用模式串中具有相同的前綴后綴不做沒用的重復(fù)匹配當(dāng)前第29頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)找模式串中最大的相同前綴后綴考察前綴后綴得到：最大前綴后綴公共元素長(zhǎng)度字符ABCDABD最大前綴后綴公共元素長(zhǎng)度0000120模式串的各個(gè)子串前綴后綴最大公共元素長(zhǎng)度A空空0ABAB0ABCA,ABC,BC0ABCDA,AB,ABCD,CD,BCD0ABCDAA,AB,ABC,ABCDA,DA,CDA,BCDA1ABCDABA,AB,ABC,ABCD,ABCDAB,AB,DAB,CDAB,BCDAB2ABCDABDA,AB,ABC,ABCD,ABCDAABCDABD,BD,ABD,DABD,CDABDBCDABD0當(dāng)前第30頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)失配時(shí)，模式串向右移動(dòng)的位數(shù)為已匹配字符數(shù)-失配字符的上一位字符所對(duì)應(yīng)的最大長(zhǎng)度值字符ABCDABD最大前綴后綴公共元素長(zhǎng)度0000120當(dāng)前第31頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)基于《前后綴的最大公共元素長(zhǎng)度》匹配1/2D跟空格失配時(shí)向右移動(dòng)的位數(shù)=已匹配的字符數(shù)-上一位字符B對(duì)應(yīng)的最大公共元素長(zhǎng)度6-2=4再度失配，向右移動(dòng)：2-0=2位字符ABCDABD最大前綴后綴公共元素長(zhǎng)度0000120當(dāng)前第32頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)基于《前后綴最大公共長(zhǎng)度》匹配2/2A跟空格失配，向右移動(dòng)一位D跟C失配時(shí)向右移動(dòng)的位數(shù)為已匹配的字符數(shù)-上一位字符B對(duì)應(yīng)的最大長(zhǎng)度即：6-2=4匹配成功。字符ABCDABD前綴后綴最大公共元素長(zhǎng)度0000120當(dāng)前第33頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)“前后綴”概念引申出next數(shù)組前綴后綴的最大公共元素長(zhǎng)度失配時(shí)移動(dòng)位數(shù)：已匹配字符數(shù)-失配字符的上一位字符所對(duì)應(yīng)的最大長(zhǎng)度值next數(shù)組把上面的“最大長(zhǎng)度值”整體向右移動(dòng)一位，然后初始值賦為-1失配時(shí)移動(dòng)位數(shù)：失配字符所在位置-失配字符對(duì)應(yīng)的next值j-next[j]注意：無(wú)論是哪種匹配方法，得出的向右移動(dòng)位數(shù)一樣模式串ABCDABDnext-1000012模式串ABCDABD前后綴最大公共元素長(zhǎng)度0000120當(dāng)前第34頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)基于《next數(shù)組》匹配1/2Next數(shù)組失配時(shí)移動(dòng)位數(shù)：j-next[j]j從0開始計(jì)數(shù)：向右移動(dòng)6-2=4位再次失配向右移動(dòng)：j-next[j]=2-0=2位字符ABCDABDNext值-1000012當(dāng)前第35頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)基于《next數(shù)組》匹配2/2接上移動(dòng)兩位之后A跟空格不匹配，再次后移一位D處失配，向右移動(dòng)j-next[j]=6-2=4位字符ABCDABDNext值-1000012當(dāng)前第36頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)KMP算法假設(shè)現(xiàn)在文本串S匹配到i位置，模式串P匹配到j(luò)位置如果j=-1，或者當(dāng)前字符匹配成功（即S[i]==P[j]），都令i++，j++，繼續(xù)匹配下一個(gè)字符；如果j!=-1，且當(dāng)前字符匹配失敗（即S[i]!=P[j]），則令i不變，j=next[j]。此舉意味著失配時(shí)模式串P相對(duì)于文本串S向右移動(dòng)了j-next[j]位。當(dāng)前第37頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)intKmpSearch(char*s,char*p){inti=0,j=0;intsLen=strlen(s);intpLen=strlen(p);while(i<sLen&&j<pLen){

//①如果j=-1，或者當(dāng)前字符匹配成功（即S[i]==P[j]），都令i++，j++

if(j==-1||s[i]==p[j]){i++;j++;}else{

//②如果j!=-1，且當(dāng)前字符匹配失?。碨[i]!=P[j]），則令i不變，j=next[j]

j=next[j];}}if(j==pLen)returni-j;elsereturn-1;}當(dāng)前第38頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)next數(shù)組的遞推計(jì)算對(duì)于值k，已有p0p1,...,pk-1=pj-kpj-k+1,...,pj-1，相當(dāng)于next[j]=k。下面的問題是：已知next[0,...,j]，如何求出next[j+1]呢？pk=pjpk!=pj當(dāng)前第39頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)當(dāng)前第40頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)voidGetNext(char*p,intnext[]){intpLen=strlen(p);next[0]=-1;intk=-1;intj=0;while(j<pLen-1){

//p[k]表示前綴，p[j]表示后綴

if(k==-1||p[j]==p[k]){++k;++j;next[j]=k;}else{

//拿前綴去跟后綴匹配，如果pk跟pj失配，繼續(xù)遞歸前綴索引p[next[k]]k=next[k];}}}當(dāng)前第41頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)當(dāng)前第42頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)如何學(xué)習(xí)算法之二要?jiǎng)t二：把相關(guān)算法串聯(lián)起來(lái)，相互比對(duì)貪心、動(dòng)態(tài)規(guī)劃當(dāng)前第43頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)貪心與動(dòng)規(guī)貪心：“最優(yōu)子結(jié)構(gòu)+局部最優(yōu)”動(dòng)態(tài)規(guī)劃：“最優(yōu)獨(dú)立重疊子結(jié)構(gòu)+全局最優(yōu)”。枚舉所有狀態(tài)，然后剪枝，尋找最優(yōu)狀態(tài)同時(shí)將每一次求解子問題的結(jié)果保存在一張“表格”中以后再遇到重疊的子問題，從表格中保存的狀態(tài)中查找（俗稱記憶化搜索）當(dāng)前第44頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)動(dòng)態(tài)規(guī)劃當(dāng)前第45頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)兩個(gè)簡(jiǎn)單的例子最短路徑：A->B經(jīng)過x1，x2，x3故枚舉所有可能從A到B要經(jīng)過的路徑選擇一條最優(yōu)如何求最優(yōu)比較如何比較？寫DP方程，求min比如二維數(shù)組最小路徑和一個(gè)二維矩陣M*N矩陣matrix中，找出一條路徑，只能向右或向下，求路徑經(jīng)過元素之和最小當(dāng)前位置(i,j)上一個(gè)位置只可能是(i-1，j)或(i,j-1)path[i][j]=min(path[i][j-1],path[i-1][j])+matrix[i][j]當(dāng)前第46頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)尋找和為定值的多個(gè)數(shù)輸入兩個(gè)整數(shù)n和m，從數(shù)列1，2，3.......n中隨意取幾個(gè)數(shù),使其和等于m,要求將其中所有的可能組合列出來(lái)。 list1.push_front(n);//典型的01背包問題 find_factor(sum-n,n-1);//放n，n-1個(gè)數(shù)填滿sum-nlist1.pop_front();find_factor(sum,n-1);//不放n，n-1個(gè)數(shù)填滿sum動(dòng)態(tài)規(guī)劃適用條件最優(yōu)子結(jié)構(gòu)獨(dú)立重疊子問題當(dāng)前第47頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)如何學(xué)習(xí)算法之三要?jiǎng)t三：從簡(jiǎn)單入手，追本溯源二叉樹、紅黑樹、2-3-4樹、B樹當(dāng)前第48頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)追本溯源紅黑樹為何要有RB-Tree完全平衡完全二叉樹高度平衡AVL樹先理解二叉樹的插入、刪除后理解紅黑樹的插入修復(fù)、刪除修復(fù)B樹先學(xué)習(xí)2-3-4樹，理解結(jié)點(diǎn)飽和分裂，結(jié)點(diǎn)稀缺合并為何？因?yàn)?-3-4樹在計(jì)算機(jī)科學(xué)中是階為4的B樹意味著什么？意味著2-3-4樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目是：1-3個(gè)（ceil(m/2)-1）<=n<=m-1m為階數(shù)，即孩子樹，等于4當(dāng)前第49頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)二叉樹到完全二叉樹樹的深度越小，搜索時(shí)間logn（n即為樹的深度）當(dāng)前第50頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)AVL樹高度平衡樹AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一當(dāng)前第51頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)紅黑樹的5個(gè)性質(zhì)每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。根結(jié)點(diǎn)是黑的。每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn)）是黑的。如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。對(duì)于任一結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。

當(dāng)前第52頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)二叉樹的插入插入一個(gè)節(jié)點(diǎn)當(dāng)前第53頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)紅黑樹的插入插入一個(gè)元素后，需要修復(fù)，修復(fù)有兩種手段重新著色旋轉(zhuǎn)操作：左旋與右旋當(dāng)前第54頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)紅黑樹的插入修復(fù)代碼3種插入修復(fù)情況當(dāng)前第55頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹當(dāng)前第56頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹的查找當(dāng)前第57頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹的插入1/3當(dāng)前第58頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹的插入2/3當(dāng)前第59頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹的插入3/3關(guān)鍵字?jǐn)?shù)要超過4時(shí)就要開始分裂4階的B樹的關(guān)鍵字?jǐn)?shù)滿足：大于等于1，小于等于3當(dāng)前第60頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹一次完整的插入示例1/2不斷插入多個(gè)元素的過程當(dāng)前第61頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)2-3-4樹一次完整的插入示例1/2接上，繼續(xù)插入元素N、B、X當(dāng)前第62頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)看過了紅黑樹的插入看過了2-3-4樹分裂接下來(lái)，看另外一種新樹它與紅黑樹最大的區(qū)別在于，它的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)當(dāng)前第63頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹出現(xiàn)緣由二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進(jìn)而導(dǎo)致查詢效率低下

當(dāng)前第64頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)一棵B樹的示例查找文件29一直往下，3次磁盤IO操作和3次內(nèi)存查找當(dāng)前第65頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹的插入示例1/5一棵5階（即樹中任一結(jié)點(diǎn)至多含有4個(gè)關(guān)鍵字，5棵子樹）B樹根結(jié)點(diǎn)至少得有2個(gè)孩子5階，2-4個(gè)key，3-5個(gè)childrenB樹除根結(jié)點(diǎn)之外的結(jié)點(diǎn)（包括葉子結(jié)點(diǎn)）的關(guān)鍵字的個(gè)數(shù)n必須滿足：（ceil(m/2)-1）<=n<=m-12<=關(guān)鍵字?jǐn)?shù)<=4m為孩子數(shù)，即子樹的數(shù)目，等于5當(dāng)前第66頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹的插入示例2/5插入以下字符字母到一棵空的B樹中非根結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)小了（小于2個(gè)）就合并大了（超過4個(gè)）就分裂）：CNGAHEKQMFWLTZDPRXYS當(dāng)前第67頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹的插入示例3/5CNGAHEKQMFWLTZDPRXYS③當(dāng)咱們插入E,K,Q時(shí)，不需要任何分裂操作：④插入M需要一次分裂，M恰好是中間關(guān)鍵字元素，以致向上移到父節(jié)點(diǎn)中：當(dāng)前第68頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹的插入示例4/5CNGAHEKQMFWLTZDPRXYS⑤插入F,W,L,T不需要任何分裂操作：⑥插入Z時(shí)，中間元素T上移到父節(jié)點(diǎn)中：當(dāng)前第69頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B樹的插入示例5/5CNGAHEKQMFWLTZDPRXYS⑦插入D時(shí)，D上移到父節(jié)點(diǎn)中，然后字母P,R,X,Y陸續(xù)插入：⑧插入S時(shí)，中間元素Q上移到父節(jié)點(diǎn)中，Q上移導(dǎo)致父結(jié)點(diǎn)“DGMT”也滿了，將父節(jié)點(diǎn)中的中間元素M上移到新形成的根結(jié)點(diǎn)中，從而致使樹的高度增加一層。當(dāng)前第70頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B+樹一棵m階的B+樹和m階的B樹的異同點(diǎn)在于：有n棵子樹的結(jié)點(diǎn)中含有n-1個(gè)關(guān)鍵字所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(而B樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。(而B樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)當(dāng)前第71頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)B*樹B*-tree是B+-tree的變體在B+樹的基礎(chǔ)上，所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針)；B*樹中非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）當(dāng)前第72頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)總結(jié)有了二叉樹，為何要有AVL平衡樹？有了AVL樹，為何要有紅黑樹？有了紅黑樹，為何要有B樹？當(dāng)前第73頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)海量數(shù)據(jù)處理當(dāng)前第74頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)十個(gè)密匙哈希分治simhash算法外排序MapReduce多層劃分BitmapBloomFilterTrie樹數(shù)據(jù)庫(kù)倒排索引當(dāng)前第75頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)76萬(wàn)丈高樓平地起Reb-Blacktreeset/map（map同時(shí)擁有key和value，set的key就是value）multiset/multimap（允許重復(fù)鍵值）hashtablehashmap/hashset/hash_multiset/hash_multimap（允許重復(fù)鍵值）備注：C++11標(biāo)準(zhǔn)命名了基于hash函數(shù)實(shí)現(xiàn)的unordered_set/unordered_map/unordered_multiset/unordered_multimap相當(dāng)于hash_set、hash_ma，和hash_multiset、hash_multimap。當(dāng)前第76頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)77分而治之/hash映射+hash統(tǒng)計(jì)+堆/快速/歸并排序海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP分而治之/hash映射，比如模1000，把整個(gè)大文件映射為1000個(gè)小文件hash_map(ip，value)來(lái)進(jìn)行頻率統(tǒng)計(jì)（hash_map對(duì)那1000個(gè)文件中的所有IP進(jìn)行頻率統(tǒng)計(jì)，然后依次找出1000個(gè)文件中頻率最大的那個(gè)IP）再在這1000個(gè)最大的IP中，找出那個(gè)頻率最大的IP當(dāng)前第77頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)類似問題變形hash函數(shù)映射+hashmap統(tǒng)計(jì)+堆排有100W個(gè)關(guān)鍵字，長(zhǎng)度小于等于50字節(jié)。用高效的算法找出top10的熱詞，并對(duì)內(nèi)存的占用不超過1MB。假設(shè)已有10w個(gè)敏感詞，現(xiàn)給你50個(gè)單詞，查詢這50個(gè)單詞中是否有敏感詞。單機(jī)5G內(nèi)存，磁盤200T的數(shù)據(jù)，分別為字符串，然后給定一個(gè)字符串，判斷這200T數(shù)據(jù)里面有沒有這個(gè)字符串，怎么做？如果查詢次數(shù)會(huì)非常的多,怎么預(yù)處理？當(dāng)前第78頁(yè)\共有95頁(yè)\編于星期日\(chéng)16點(diǎn)simHash的具體算法分詞給定一段語(yǔ)句：“CSDN博客結(jié)構(gòu)之法算法之道的作者July”，分詞后為：“CSDN/博客/結(jié)構(gòu)/之/法/算法/之/道/的/作者/July”，然后為每個(gè)特征向量賦予權(quán)值：CSDN(4)博客(5)結(jié)構(gòu)(3)之(1)法(2)算法(3)之(1)道(2)的(1)作者(5)July(5)，其中括號(hào)里的數(shù)字代表這個(gè)單詞在整條語(yǔ)句中的重要程度，數(shù)字越大代表越重要。hash○通過hash函數(shù)計(jì)算各個(gè)特征向量的hash值，hash值為二進(jìn)制數(shù)01組成的n-bit簽名。比如“CSDN”的hash值Hash(CSDN)為100101，“博客”的hash值Hash(博客)為“101011”。就這樣，字符串就變成了一系列數(shù)字。加權(quán)W=Hash*weight。W(CSDN)=100101*4=4-4-44-44，W(博客)=101011*5=5-55-555。合并將上述各個(gè)特征的加權(quán)結(jié)果累加，變成一個(gè)序列串。如：“4+5,-4+-5,-4+5,4+-5,-4+5,4+5”，得到“9,-9,1,-1,1”。降維對(duì)于n位簽名的累加結(jié)果，如果大于0則置1