對(duì)數(shù)器=（隨機(jī)樣本生成器+正確解題方法）

return 正確結(jié)果；

然后調(diào)用自己覺得好的辦法與對(duì)數(shù)器得出的結(jié)果進(jìn)行對(duì)比

插入

排序，外層循環(huán)控制來到位置，內(nèi)層循環(huán)決定是否進(jìn)行交換，如果當(dāng)前位置比左邊小直接continue，初始有序狀態(tài)會(huì)影響算法的時(shí)間復(fù)雜度。

除功能必須要求的原因之外，另外開辟的空間

記錄當(dāng)前位置是否大于等于，符合就記住，并進(jìn)入下一次二分，如果下一次不成功，就結(jié)束，發(fā)送最近一個(gè)數(shù)

鏈表反轉(zhuǎn)（普遍位置）head為當(dāng)前節(jié)點(diǎn)，pre為上一節(jié)點(diǎn)，記錄下一個(gè)節(jié)點(diǎn)為next=head.next;反轉(zhuǎn)鏈表head.next=pre;反轉(zhuǎn)完成來到新位置pre=head;head=next;重復(fù)操作

雙向鏈表，實(shí)現(xiàn)頭/尾部插入刪除操作，是棧和隊(duì)列的基礎(chǔ)

3.棧：棧頂進(jìn)棧頂出（規(guī)定那邊是棧頂就行）

4.隊(duì)列：頭刪尾插

棧

隊(duì)列

數(shù)組隊(duì)列

最小棧實(shí)現(xiàn)1

實(shí)現(xiàn)2：比最小棧棧頂小于等于的時(shí)候壓入，只有和data棧頂一樣大的時(shí)候才彈出返回，否則只是返回最小棧peak

棧實(shí)現(xiàn)隊(duì)列

哈希表在非基礎(chǔ)類型中不按值傳遞

歸并排序?qū)崿F(xiàn)細(xì)節(jié)

遞歸版

非遞歸版

快排序?qū)崿F(xiàn)細(xì)節(jié)

荷蘭國旗問題

快排

快排3.0

注意：堆和搜索樹的區(qū)別是，搜索樹是自頂向下找到自己的位置的，而堆是像隊(duì)列一樣每次進(jìn)入時(shí)先排再隊(duì)尾，然后向上heapInsert找到自己的位置，是先插后找。

堆的push利用HeapInsert

2.堆的pop利用Heapify（先--heapsize，因?yàn)橄聵?biāo)是0開始的）

堆排序：先建成堆；每次拿heapsize-1下標(biāo)處的數(shù)據(jù)與0下標(biāo)的數(shù)進(jìn)行交換；再heapsize--；然后heapify.....重復(fù)

堆排序

建堆：一種是向上看，這種是向下沉

堆中修改值resign

當(dāng)一個(gè)數(shù)組每個(gè)數(shù)據(jù)離它正確排列位置不超過k時(shí)的問題

comp(o1,o2):返回-1則o1在前，否則o2在前

前綴樹

結(jié)點(diǎn)（內(nèi)含next節(jié)點(diǎn)數(shù)組）

insert

search

所有加入字符串中有幾個(gè)以pre為前綴的

delete

實(shí)現(xiàn)2

基數(shù)排序（高位數(shù)字比低位數(shù)字有決定性，且后來者會(huì)顛覆前者）radixsort

newCount[i]=Count[i-1]+count[i];

help[--newCount[array[j]位值]]=array[j];

對(duì)于基礎(chǔ)類型的數(shù)據(jù)，穩(wěn)定性沒有意義，因?yàn)榛A(chǔ)類型是按值傳遞的，對(duì)于人來說兩個(gè)相同的數(shù)字即便互換了順序也沒有實(shí)際影響。

對(duì)于非基礎(chǔ)類型來說，比如一組數(shù)據(jù)開始按照時(shí)間順序來排列，后來應(yīng)業(yè)務(wù)需求的影響又按照大小來排序，如果具有穩(wěn)定性的話，那么雖然整體是按照大小來排序，但原來時(shí)間的順序也沒有被破壞，這一點(diǎn)對(duì)于很多產(chǎn)品都很有意義。一下是各種排序特性總結(jié):

如果奇數(shù)放在左邊偶數(shù)放在右邊——0/1標(biāo)準(zhǔn)的partition，如果這可以做到的話，那為什么partitionSort不做成有穩(wěn)定性的呢？

略

先壓入右后壓入左是為了保證左孩子在棧頂進(jìn)行打印，并且壓入了右孩子便于以后返回來遍歷右孩子先序：

后序：先壓左再壓右，此為頭右左即為后序的逆序，把彈出打印改為彈出到另外一個(gè)棧中，最后打印這個(gè)棧。

一個(gè)棧實(shí)現(xiàn)的（先壓入頭節(jié)點(diǎn)）：h是進(jìn)行標(biāo)記打印過的位置的，如果左右都沒有打印過就先壓入左（并更新位置到左），如果左打印過了而有沒有，就壓入右，如果左右都打印過啦就彈出打印棧頂

注：第一個(gè)if必須包含對(duì)右孩子是否打印過的判斷，否則上一次打印了右孩子，而左孩子沒有了標(biāo)記指針就會(huì)誤以為左孩子沒有打印過（右孩子都被標(biāo)記過，那么左孩子必然也被標(biāo)記過）

c進(jìn)行peak相當(dāng)于更新操作

中序非遞歸實(shí)現(xiàn)：盡量壓入左邊界，沒有左邊界可以壓了就彈出打印，并且來到右樹位置，棧中數(shù)據(jù)相當(dāng)于一個(gè)線索，盡量走到最左邊再進(jìn)行處理

******************************************************************************************************************************************************************************

其它實(shí)現(xiàn)先序中序后序遍歷見P30Morris

******************************************************************************************************************************************************************************

二叉樹寬度優(yōu)先遍歷（隊(duì)列）

統(tǒng)計(jì)二叉樹最大寬度：沒有到達(dá)下一層就++；否則就結(jié)算，重新統(tǒng)計(jì)下一層，而最后一層無法逾越，所以最后結(jié)束循環(huán)后還要結(jié)算一次。

levelmap節(jié)點(diǎn)在那一層的hashmap；curlevel當(dāng)前正在統(tǒng)計(jì)層；curnodelevel當(dāng)前節(jié)點(diǎn)層數(shù)；

curlevelnodes寬度（每次++）；max更新最大寬度

由于隊(duì)列實(shí)現(xiàn)的寬度優(yōu)先遍歷的特性，最右一個(gè)本層節(jié)點(diǎn)必然在隊(duì)列后面的位置，所以第一次遍歷到節(jié)點(diǎn)是下一層的時(shí)候，必然說明一一本層節(jié)點(diǎn)已經(jīng)全部遍歷完了?。?！

不用map實(shí)現(xiàn)：發(fā)現(xiàn)每一層結(jié)束位置即可

curend：當(dāng)前層最右節(jié)點(diǎn)；nextend：下一層最右節(jié)點(diǎn)......

nextend一直不斷更新向右邊動(dòng)，記錄下一層最右節(jié)點(diǎn)，以便curend更新

如果當(dāng)前節(jié)點(diǎn)cur是當(dāng)前層最右節(jié)點(diǎn)就結(jié)算，如果不是就++

當(dāng)cur來到了當(dāng)前層最右節(jié)點(diǎn)，則nextend勢必也會(huì)剛好找到當(dāng)前層最右位置，

注：而且還會(huì)保證最后一層右邊界不會(huì)越界（判斷不為空才會(huì)更新）

左右孩子不為空才進(jìn)行的nextend更新也保證了不會(huì)出現(xiàn)隔一層統(tǒng)計(jì)的情況

二叉樹的序列化和反序列化

序列化

反序列化

按層序列化

樹的打?。ㄟf歸實(shí)現(xiàn)）：右頭左的順序是因?yàn)?，右?cè)節(jié)點(diǎn)位于最高層，而且要先深度遍歷打印

查找中序遍歷結(jié)果的后繼節(jié)點(diǎn)

紙條折痕問題

二叉樹遞歸套路

平衡二叉樹

兩節(jié)點(diǎn)最大距離

搜索二叉樹（任意一棵以當(dāng)前節(jié)點(diǎn)為頭結(jié)點(diǎn)的樹，它的左子樹都比自己小，右子樹都比自己大），下面進(jìn)行判斷（返回最大搜索二叉樹的頭節(jié)點(diǎn)，即遞歸在不滿足搜索二叉樹處停止，并一步步向上返回此節(jié)點(diǎn)）：

個(gè)人觀點(diǎn)：如果左樹和右樹都是搜索二叉樹并且符合當(dāng)前要求，size=左size+右size+1，更新max，min....

如果有一個(gè)不滿足要求則取最大的搜索子樹向上返回

派對(duì)快樂值問題：

個(gè)人觀點(diǎn)當(dāng)前頭節(jié)點(diǎn)來：頭節(jié)點(diǎn)快樂值+所有直接下級(jí)的直接下級(jí)快樂值之和與當(dāng)前頭節(jié)點(diǎn)不來：所有直接下級(jí)的快樂值之和的對(duì)比（和本題不太一樣，請(qǐng)指正)

個(gè)人觀點(diǎn)：對(duì)于初學(xué)者盡量將遞歸函數(shù)單純的理解為一個(gè)黑盒，一個(gè)可以完成需求的黑盒，應(yīng)該注重的是對(duì)于解決問題的宏觀策略一一base case+基本策略

決定來時(shí)：當(dāng)前節(jié)點(diǎn)快樂值+直接下級(jí)不來的最大快樂值

決定不來：0+（直接下級(jí)選擇來或者不來的最大快樂值的最大值）累加

以與當(dāng)前節(jié)點(diǎn)有關(guān)無關(guān)劃分情況

第二期

打表

我們只能站在先手的立場上去嘗試解決問題，這是從邏輯上來說的，不能同時(shí)站在兩個(gè)立場。

個(gè)人觀點(diǎn)：n-base已經(jīng)代表當(dāng)前后手的境地了，而當(dāng)前后手的后手就是現(xiàn)在的先手。

暴力解、打表

矩陣處理技巧：不要把想法限制在局部坐標(biāo)的變換或者變化規(guī)律上，而是有一個(gè)宏觀調(diào)度

個(gè)人觀點(diǎn)：應(yīng)該以最直觀的方式來實(shí)現(xiàn)一一觀察它最樸實(shí)的移動(dòng)方法

打印之字形矩陣A、B同步走，A不能再往右了就向下走，B不能再往下走，就向右，然后確定上下打印方向

轉(zhuǎn)圈打印矩陣

原地旋轉(zhuǎn)矩陣

會(huì)議問題

放燈問題：

暴力遞歸：如果當(dāng)前位置是x跳過，遞歸下一步；如果是“。”就進(jìn)行放燈何不放燈的抉擇，分別再遞歸下一步，最后取min，base case為檢測是否都照亮

for循環(huán)驗(yàn)證是否都照亮

lighes.remove是現(xiàn)場恢復(fù)的操作

貪心試法個(gè)人觀點(diǎn)：來到當(dāng)前節(jié)點(diǎn)如果是x就跳過

一、 i-1位置是是×?xí)r（從當(dāng)前i位置觀察）

1）。。。放于i+1位置，遞歸進(jìn)行i+3位置的嘗試

2）。。x放于i或者i+1無所謂結(jié)果一樣，遞歸i+3

3）。x放于i位置，遞歸i+2

/*二、i-1位置是。

1.i-1位置放燈了

1）。。。在i+1位置放燈，遞歸i+3

2）。。x在i或者i+1位置放燈都一樣，遞歸i+3

3）。x直接遞歸i+2

2.i-1位置沒放燈，檢測i-1是否照亮，若未照亮，不論如何在i位置點(diǎn)燈，遞歸i+2；若照亮了，就把i-1當(dāng)x和一、處理方式一樣*/

老師講解不需要二、情況,因?yàn)閕位置不應(yīng)該被之前位置決定，但是依然可以用一、的方法，因?yàn)橹拔恢貌挥绊懍F(xiàn)在位置等同于把i-1位置當(dāng)作x

并查集解決連通性集合問題

Unionset初始化

findfather兼具尋找代表點(diǎn)和扁平化并查集的優(yōu)化操作

學(xué)生歸類問題，以三個(gè)字段作為是否歸屬一個(gè)集合并且合并的判斷依據(jù)，以hashmap：key=string

value=user

圖算法：圖是點(diǎn)集和邊集的集合

鄰接矩陣法

點(diǎn)結(jié)構(gòu)描述：value代表點(diǎn)的值；in、out分別代表入度和出度；nexts代表由自己出發(fā)的直接鄰居；edges代表由自己出發(fā)的邊包含權(quán)值、出發(fā)點(diǎn)、終點(diǎn)

邊信息

點(diǎn)集+邊集

將其他不同形式圖的描述轉(zhuǎn)化成這種標(biāo)準(zhǔn)形式

如果圖的點(diǎn)集沒有出現(xiàn)過from、to這個(gè)點(diǎn)就進(jìn)行初始化（等下進(jìn)行寫入操作）

拿出from和to對(duì)應(yīng)的點(diǎn)來fromNode和toNode

構(gòu)建出這條新的邊，接下來對(duì)兩個(gè)點(diǎn)進(jìn)行寫入操作，最后邊入集合

寬度優(yōu)先遍歷：隊(duì)列實(shí)現(xiàn)，hashset防止重復(fù)加入形成環(huán)

預(yù)先進(jìn)入一個(gè)節(jié)點(diǎn)，進(jìn)入循環(huán)，先彈出后打印，然后for循環(huán)枚舉沒有set過的就進(jìn)隊(duì)......

深度優(yōu)先遍歷：棧實(shí)現(xiàn)，預(yù)先壓入棧一個(gè)，后打印，進(jìn)入while就pop棧頂元素，進(jìn)入for循環(huán)并觀察它是否有未進(jìn)入set的子節(jié)點(diǎn)，如果有，則再次入棧，并把沒有進(jìn)入過set過的登記壓棧，然后馬上break，不深究當(dāng)前節(jié)點(diǎn)所有的孩子，留到以后再去遍歷......

在圖中找到入度為0的點(diǎn)，入隊(duì)，消除他的影響，重復(fù)......

K算法：先把所有邊從小到大排序，找到最小邊看兩個(gè)點(diǎn)是不是一個(gè)集合，不是一個(gè)集合就要這條邊，利用并查集歸為一個(gè)集合，否則跳過尋找次之.......

找最小邊權(quán)值的方法嘗試用小根堆實(shí)現(xiàn)，

進(jìn)行無向圖其實(shí)也可以，因?yàn)橹皇欠催^來對(duì)另一側(cè)不會(huì)出現(xiàn)重復(fù)情況而已，這一點(diǎn)是在并查集的isSameSet決定的，可以進(jìn)行優(yōu)化

用整體權(quán)重最小的邊的集合，不改變連通性。

K算法：并查集+小根堆

P算法：任意指定出發(fā)點(diǎn)，解鎖有關(guān)此點(diǎn)所有的邊，選擇最小邊，查看此邊另一端是否解鎖過，如果解鎖過就消除此邊，否則就進(jìn)行解鎖，并把和這個(gè)新節(jié)點(diǎn)所有有關(guān)的邊進(jìn)行解鎖，下一次再在解鎖邊集合中找最小邊......

解鎖的邊和點(diǎn)放在set中，還可以實(shí)現(xiàn)忽視某些不符合規(guī)定的邊

最外層for循環(huán)防止森林出現(xiàn)

K算法和P算法區(qū)別：K算法尋找最小權(quán)值邊是從全局里面查找的（小根堆），而P算法是每解鎖一次才查找一次最小權(quán)值邊一一局部查找。

distanceMap

迪杰特斯拉算法（最短路徑問題）

選擇當(dāng)前最短路徑進(jìn)行封存，并作為出發(fā)點(diǎn)，由此出發(fā)查找他能直接到達(dá)的所有位置，如果比遠(yuǎn)距離?。褐刂靡猿霭l(fā)點(diǎn)到達(dá)目的地的所有距離。計(jì)算完成后，重復(fù)......注意，已經(jīng)到達(dá)的最短路徑無需更改

/*旅行商問題個(gè)人觀點(diǎn)：

base?case：重回出發(fā)點(diǎn)，檢測是否所有點(diǎn)都走過

無路可走?：return false；

基本策略：暴力的每個(gè)地方都進(jìn)行嘗試（枚舉當(dāng)前節(jié)點(diǎn)nextEdge）*/

個(gè)人認(rèn)為迪杰特斯拉算法可以進(jìn)行優(yōu)化：申請(qǐng)一個(gè)數(shù)組，長度為點(diǎn)個(gè)數(shù)，以下標(biāo)代表節(jié)點(diǎn)a、b、c....而數(shù)組內(nèi)部代表a->a,a->b,a->c的距離，初始化內(nèi)部值無法到達(dá)的置為max，將找到的最短路徑封存入hashmap，并在數(shù)組中置為0，每次查找數(shù)組中非0的最小值......

可以利用小根堆進(jìn)行加速，解決彈出最短邊以及改堆值重建小根堆和添加新值的問題，這不是普通堆。忽略重回節(jié)點(diǎn)的邊。

暴力遞歸：base case+基本策略

...............................................................................

個(gè)人觀點(diǎn)：對(duì)于逆序一個(gè)棧，即便我們一開始沒什么思路，但是仍然可以從直觀上進(jìn)行一定的分析，作者本身進(jìn)行了提示一一遞歸，直觀思路是：

每次提取出最底層的數(shù)據(jù)，然后把他壓入一個(gè)新的棧中，如果配合遞歸那就是，每次提取出棧底元素，然后交由遞歸再提取出新棧的底層元素，這樣就實(shí)現(xiàn)了1>2>3(3為棧底)這個(gè)原始棧提取元素棧底的順序是這樣的：第一層 3 ；第二層 2 ；第三層 1 至此遞歸到達(dá)最底層（?？樟耍缓笙旅嫣鲞f歸，進(jìn)行重新壓入新棧的的操作，即本方法是這樣的

base case：到達(dá)原始棧棧底 return

基本策略：先將本層中原始棧棧底取出，然后利用遞歸進(jìn)入下一層重復(fù)這一操作直至結(jié)束

結(jié)束后把取出的每一層棧底元素壓回新棧........（僅個(gè)人意見，不對(duì)指教，非科班出身請(qǐng)見諒）

函數(shù)優(yōu)先執(zhí)行的是遞歸調(diào)用上面的部分，所以需要優(yōu)先完成什么操作要在遞歸調(diào)用之前進(jìn)行......

本題中取棧底元素的操作也用了遞歸實(shí)現(xiàn)（存在現(xiàn)場恢復(fù)）

整體實(shí)現(xiàn)

這個(gè)問題揭示了遞歸棧對(duì)于數(shù)據(jù)的保存作用，值得研究。

遞歸必須保證子問題只是比原問題規(guī)模小而已

對(duì)于暴力遞歸求解問題，不論是針對(duì)先手后手型問題，還是一般的逐層求解性問題，一定不能考慮計(jì)算機(jī)是怎樣實(shí)現(xiàn)的，容易被“催眠”。我們只需要站在當(dāng)前立場上，按照最為直接、樸素、直觀的態(tài)度處理問題即可?。。。?！

打印字符串全部子序列問題：當(dāng)前字符進(jìn)行要與不要的抉擇，然后遞歸對(duì)下一個(gè)字符進(jìn)行同樣抉擇，最終實(shí)現(xiàn)每一個(gè)字符要與不要的抉擇

進(jìn)階：不重復(fù)打印，liyongset比較浪費(fèi)空間

打印字符串的全排列

每一層函數(shù)進(jìn)行枚舉，然后下一層交給遞歸（含現(xiàn)場恢復(fù)）

不重復(fù)的全排列：可以用set，但是也可以利用分支限界一一在枚舉階段摒除相同的兩個(gè)字母和當(dāng)前i位置交換，在源頭上過濾

從左往右的嘗試模型：

如果已經(jīng)超重就無效，如果方案有效但是沒貨就返回0；下面對(duì)于要貨或者不要貨物進(jìn)行抉擇，然后遞歸進(jìn)入下一層，最終對(duì)兩種抉擇進(jìn)行比較取舍。

范圍上的嘗試模型：

每個(gè)人絕頂聰明的意思是：

當(dāng)前先手得到最優(yōu)的結(jié)局，而后手承受先手帶來的最差的結(jié)局

以往的決策都是對(duì)當(dāng)前一個(gè)元素進(jìn)行取舍，這次對(duì)最左和最右兩個(gè)元素的范圍進(jìn)行選擇和取舍

從小往大范圍的嘗試分析

海盜分硬幣問題：方案只有贊成票超過一半才能通過，否則殺死

剩余E:必然同意

剩余·DE:D必然被否決，E得全部金幣

剩余CDE:C告訴D如果自己死它的結(jié)局，迫使D同意自己C：100 D： 0 E：0

剩余BCDE:B告訴后人自己死他們的遭遇B： 98 C ：0 D：1 E：1

剩余ABCDE:同理A ：97 B： 0 C ：1 D：2 E：0

每個(gè)人都和緊挨著自己的人是最大的對(duì)手，在此基礎(chǔ)上針對(duì)自己的對(duì)手，并且給對(duì)手之后的人更大一點(diǎn)的報(bào)酬即可（只要人數(shù)超過一半）

歐拉信封問題：一個(gè)村子里每個(gè)人必須寄出一封信收到一封信，問總共有多少種寄信方式？

1個(gè)人有0種方法，2個(gè)人有1種方法，3個(gè)人有2種........

n個(gè)人中，當(dāng)a寄給b一封信，則b可以選擇回寄給b或者不回寄給b一一

1）回寄則問題縮小成為n-2規(guī)模

2）不回寄，則a還差收到一封信，b差寄出一封信，二者可以視作一個(gè)人一一寄出一封信收到一封信，問題規(guī)?？s小為n-1

int f（int n）{

base case：人數(shù)為1 return 0；

2 return 1；

3 return 2；

基本策略：return 4*（ f（n-1）+f（n-2））；

}

base case：來到length就return 1；

如果未來到length但是沒有地方可以擺return 0；

基本策略：在當(dāng)前行每一列進(jìn)行嘗試，然后標(biāo)記，遞歸進(jìn)入下一行......

判斷：數(shù)組記錄擺放列，每次遍歷數(shù)組非負(fù)項(xiàng)，只要數(shù)據(jù)不同并且......

.

在本層遞歸中，對(duì)于某一列的一位標(biāo)記1，左移得到左限制，右移得到右限制，三者或運(yùn)算為總限制，下一級(jí)遞歸挑選未標(biāo)記過的位置重復(fù)此步驟

00001000

00010000--->00011100;下一層00011100選第3-->

00000100

00100000

個(gè)0的位置標(biāo)記1 01000000-->01110000并與之前

00010000

標(biāo)記想與01111100

base case：當(dāng)來到最后一步，檢測是否到達(dá)，是返回1，否則返回0

res=0；

基本策略：如果來到最左res+=process（向右走）；

如果來到最右res+=process（向左走）；

除此之外res+=process（向左）+process（向右）；

return res；

動(dòng)態(tài)規(guī)劃初級(jí)版一一記憶化搜索

只有含有重復(fù)子問題的遞歸才有改成動(dòng)態(tài)規(guī)劃的必要

最重要的就是分析清楚有幾個(gè)可變參數(shù)，這關(guān)系我們要做一個(gè)幾維表

背包問題改動(dòng)態(tài)規(guī)劃：

字符串問題改動(dòng)態(tài)規(guī)劃：一個(gè)可變參數(shù)

抽紙牌問題改動(dòng)態(tài)規(guī)劃：L和R作為兩個(gè)可變參數(shù)組成二維表，L不可能大于R，否則就越界啦?。?！

記憶化搜索和動(dòng)態(tài)規(guī)劃的區(qū)別：如果決策過程中沒有枚舉行為（有限動(dòng)作），記憶化搜索沒必要改為動(dòng)態(tài)規(guī)劃，否則有必要改為經(jīng)典動(dòng)態(tài)規(guī)劃。

將n種不同面值的紙幣湊成一個(gè)特定值：兩種思路，第一種將當(dāng)前貨幣枚舉m張，下一層遞歸不再使用這張貨幣再去嘗試；第二種當(dāng)前將n種貨幣試一遍（只試一張），下一級(jí)遞歸亦如此。。。。。

for循環(huán)中已經(jīng)包含了base case的一部分即：rest<0時(shí)，return 0；

改成記憶化搜索：所謂后效性問題是指可變參數(shù)未找全導(dǎo)致問題未全部解決。

改成經(jīng)典動(dòng)態(tài)規(guī)劃：

由于內(nèi)部含有枚舉行為，還可以進(jìn)一步優(yōu)化：

略

未來知識(shí)

多樣本位置全對(duì)應(yīng)的嘗試模型：

遞歸嘗試 int f（str L，str R，i，j）：str1在i位置，且str2在j位置公共子序列下一步遞歸一一

主調(diào)用f（str L，str R，0，0）；

base case：如果兩個(gè)字符串越界，

return 0；

if（L[i]==R[j]）

return 1+f(L，R，i-1，j-1)；

else

return max（f（L，R，i+1，j），f（L，R，i，j+1））；

此問題包含三種可能性：既不以str1又不以str2結(jié)尾（縮小問題規(guī)模），以str1或者str2結(jié)尾（分別縮小規(guī)模進(jìn)行嘗試取max），既已str1又以str2結(jié)尾（說明當(dāng)前必然相等1+二者縮小規(guī)模的比較）。

之所以會(huì)感到困惑一一如果當(dāng)前i和j一個(gè)字符相同，那么他真的為公共子序列做貢獻(xiàn)了嗎，當(dāng)然是，因?yàn)槲覀兪菑淖笸乙稽c(diǎn)一點(diǎn)考慮的，產(chǎn)生這樣的困惑是因?yàn)槲覀兒鲆暳水?dāng)前的決策正是建立在之前的基礎(chǔ)上，它不是空中樓閣，左邊的公共子序列長度我們已經(jīng)檢查過啦。這種困惑也曾經(jīng)在其他遞歸求解中出現(xiàn)過，注意?。。。。。?/p>

若i和j位置相同三種情況進(jìn)行比較

尋找業(yè)務(wù)限制的嘗試模型

在之前一些嘗試模型基礎(chǔ)之上，添加關(guān)于本題的具體限制，本質(zhì)上就是精細(xì)化的前幾種嘗試模型。

常規(guī)思路就是當(dāng)前決定洗杯子，還是揮發(fā)杯子，然后對(duì)這兩種行為做具體執(zhí)行，進(jìn)入下一層繼續(xù)抉擇。本題中洗咖啡機(jī)洗咖啡的時(shí)間是有業(yè)務(wù)限制的要么咖啡沒時(shí)間洗，要么洗咖啡機(jī)沒有空閑時(shí)間

。

決定揮發(fā)杯子，那就直接跳到下一層進(jìn)行下一個(gè)杯子的抉擇，但要給出洗咖啡機(jī)能用的時(shí)間。

決定洗杯子，先看一下咖啡杯什么時(shí)候能洗，然后去洗，進(jìn)行下一層咖啡杯的抉擇，但要給出洗咖啡機(jī)能用的時(shí)間。

不管當(dāng)前決定洗或者不洗，都得讓i后面的杯子也都洗完，最后才能比較時(shí)間，不能只管當(dāng)前這一杯。

1）wash計(jì)算決定洗則下一次咖啡機(jī)有空的時(shí)間，next1是后續(xù)決策過程所用最短時(shí)間，二者取max即為index及其往后都洗完所用的時(shí)間

/*p1記錄決定洗杯子index并完成index++所到的時(shí)間點(diǎn)；p2記錄揮發(fā)當(dāng)前index杯子并完成index++所到的時(shí)間點(diǎn)，二者取min*/

2）dry是揮發(fā)當(dāng)前杯子，next2是將后續(xù).........

最后二者取min

改為動(dòng)態(tài)規(guī)劃：

*********************************************************

*********************************************************

*********************************************************

全問題

*********************************************************

******************************************************************************************************************

三維動(dòng)態(tài)規(guī)劃：建立出空間感

象棋問題：象棋棋子馬規(guī)定在棋盤內(nèi)部必須走完n步，且到達(dá)特定目的地，問一共有多少種走法？

分析：馬在棋盤中在不越界的情況下可以走八個(gè)不同的方向，所以在當(dāng)前層枚舉各個(gè)方向的可能性，然后下一層重復(fù)此抉擇，base case為最后一步是否到達(dá)目的地。（如果越界return 0；）

可變參數(shù)：棋子坐標(biāo)、剩余步數(shù)

給定兩個(gè)參數(shù)n、m表示n行m列，給定鮑勃一個(gè)初始坐標(biāo)（a，b），他向上下左右等概率隨機(jī)的，在給定參數(shù)k。一旦越界就會(huì)死掉。求存活概率。

一共有4的k次方種走法，暴力遞歸像上下左右四個(gè)方向嘗試并進(jìn)行統(tǒng)計(jì)一一最后一步到達(dá)位置不越界即為1，若有越界行為即為0.......

找錢問題

一種錢只在當(dāng)前層嘗試，下一級(jí)遞歸不再使用

斜率優(yōu)化：當(dāng)填表的時(shí)候有枚舉行為，就看鄰近的位置能不能替代，只和觀察有關(guān)，與原題意無關(guān)。

經(jīng)典哈希函數(shù)：

1）輸入域無窮，輸出域相對(duì)有限

2）相同的輸入?yún)?shù)返回相同的輸出值（可以用來檢測文件傳輸是否正確）

3）由于輸入域無窮，輸出域有限，所以有可能會(huì)發(fā)生哈希碰撞，只是幾率非常小

4）假如每一個(gè)輸入in都會(huì)在大域上映射一個(gè)點(diǎn)，則每一個(gè)小圓圈圈中的點(diǎn)幾乎一樣，即均勻性、離散性（即便輸入有規(guī)律，哈希函數(shù)也會(huì)讓它盡可能離散均勻）

in1通過哈希函數(shù)得到out1再經(jīng)過模運(yùn)算得到m1

如果能保證在哈希域上均勻分布，也就能保證可以在m域上均勻分布

假設(shè)有一個(gè)大文件都是無符號(hào)整數(shù)0一一2的32次方-1（42億++），40億個(gè)，如果只給1G內(nèi)存，返回出現(xiàn)最多的數(shù)？

哈希表key為數(shù)，value為頻率，這樣內(nèi)存根本不夠用，一條記錄至少需要8字節(jié)，最差情況這40億個(gè)數(shù)不一樣，一共需要320億B內(nèi)存即320G，考慮其他方法

對(duì)于每一個(gè)數(shù)調(diào)用哈希函數(shù)得到一個(gè)值，然后取模100，分配在100個(gè)桶中，由于不同的數(shù)根據(jù)哈希函數(shù)會(huì)盡可能地離散均勻，然后取模之后也是離散均勻，那么我們只需要觀察哪一個(gè)桶最多，之后再針對(duì)這個(gè)桶的數(shù)進(jìn)行哈希篩查（一個(gè)數(shù)做以上步驟屬于這個(gè)桶的才歸入統(tǒng)計(jì)中），所用內(nèi)存320G/100。

注：說白了就是先大致分析一下什么性質(zhì)的數(shù)最有可能頻率最高，然后對(duì)這種性質(zhì)的數(shù)做仔細(xì)篩查

num[數(shù)據(jù)取哈希函數(shù)%100]++；

哈希函數(shù)的實(shí)現(xiàn)：

技術(shù)一：當(dāng)某一鏈表長度到達(dá)6時(shí)，由于哈希函數(shù)的性質(zhì)，也可以認(rèn)為其它鏈也到達(dá)6，后續(xù)杯需要擴(kuò)容為2倍

n個(gè)數(shù)需要擴(kuò)容O(logn)次，而每一次擴(kuò)容的代價(jià)是全要重新計(jì)算哈希值、重新掛在格子上O(n)，所以總的代價(jià)是O(n*logn),單次代價(jià)是O(logn)，而又因?yàn)槊總€(gè)鏈的長度可以自己定義很長，故可以視為O(1)。用哈希表還有刪除操作，更會(huì)減少擴(kuò)容次數(shù)。

技術(shù)二：JAVA等虛擬機(jī)語言特有的離線擴(kuò)容技術(shù)

注意，哈希表是使用上O(1)的時(shí)間，理論上O(logn)

具體語言對(duì)于鏈表可能替換成為有序樹、開放地址法……

主要是刪除操作不能硬刪，否則會(huì)有很多“洞”，令最后一條記錄去填補(bǔ)這個(gè)洞

布隆過濾器

解決黑名單問題、網(wǎng)絡(luò)爬蟲問題，允許一定的失誤率，但是布隆過濾器只可能錯(cuò)殺。

基礎(chǔ)知識(shí)

位圖：假設(shè)有一個(gè)int數(shù)組含100個(gè)元素空間，一個(gè)元素4字節(jié)一一32比特，對(duì)于黑名單上每一個(gè)文件取哈希函數(shù)后并對(duì)于每一位進(jìn)行標(biāo)記，就可以大大節(jié)省空間。而這種位圖需要基礎(chǔ)類型拼一一i

int [] arr=new int [10]相當(dāng)于320比特

numindex定位在哪個(gè)數(shù)上面去找這個(gè)位，bitindex是具體位，可以在這一位進(jìn)行標(biāo)記和查詢狀態(tài)......

布隆過濾器就是一個(gè)大位圖

一個(gè)url1文件分別調(diào)用k個(gè)哈希函數(shù)，然后取模，將那一位置1，多個(gè)哈希函數(shù)相當(dāng)于對(duì)url1提取不同的特征信息，以便進(jìn)行識(shí)別檢驗(yàn)。同理url2......

查詢的時(shí)候，url文件分別調(diào)用k個(gè)哈希函數(shù)并取模m檢驗(yàn)是否都進(jìn)行了標(biāo)記，如果沒有都進(jìn)行標(biāo)記，說明沒有在黑名單。

那么使用多少個(gè)哈希函數(shù)吶，m應(yīng)該是多少

如果m很小，經(jīng)歷過100億個(gè)url文件后，格子可能全部描黑了，都是黑名單。m決定失誤率，而k太大會(huì)導(dǎo)致一條url文件描黑很多格子。

一致性哈希原理

邏輯端不需要維持?jǐn)?shù)據(jù)，數(shù)據(jù)端需要維持大量數(shù)據(jù)。邏輯端只是使用，數(shù)據(jù)端是進(jìn)行維護(hù)。盡量選擇種類比較多的，詞頻分配比較均勻或者說每個(gè)種類都有一定的數(shù)量。

當(dāng)業(yè)務(wù)擴(kuò)展時(shí)，數(shù)據(jù)大規(guī)模增加，導(dǎo)致機(jī)器數(shù)也會(huì)增加，數(shù)據(jù)量的重新分配就成了一個(gè)問題。

一致性哈希不需要模運(yùn)算，m1、m2、m3根據(jù)哈希函數(shù)得到三個(gè)值，在環(huán)上各自的到一個(gè)位置，每輸入一條信息打到環(huán)上一個(gè)位置，順時(shí)針最近的就是他的歸屬機(jī)器。邏輯端的所有有序數(shù)組載有這三個(gè)機(jī)器數(shù)，根據(jù)二分法可以找到一條數(shù)據(jù)的歸屬機(jī)器。

現(xiàn)在增加一個(gè)機(jī)器：

這樣做存在兩個(gè)問題，初始時(shí)數(shù)量很少的機(jī)器怎么把環(huán)均分，即便可以均分那么增刪一個(gè)機(jī)器又怎么保證均分呢？

解決方法是虛擬節(jié)點(diǎn)技術(shù)：假設(shè)三臺(tái)機(jī)器各有1000個(gè)字符串，m1每一個(gè)字符串都算一個(gè)哈希值去搶環(huán)，m2......任意一段abc節(jié)點(diǎn)數(shù)差不多，此外還可以管理負(fù)載，可以讓負(fù)載能力強(qiáng)的多承擔(dān)節(jié)點(diǎn)。

base case：如果越界或者被標(biāo)記過或者不是島（！=1），直接return

基本策略：以上條件不中就是1，進(jìn)行標(biāo)記為2，然后上下左右依次嘗試

計(jì)算島的個(gè)數(shù)然后進(jìn)行感染過程：

感染過程：

下面進(jìn)行并行計(jì)算：利用并查集解決這種集合問題將整張表一分為二，分別看左右兩個(gè)表各自有幾個(gè)島，依次歸集為abcd，最終在交界處將兩個(gè)不屬于同一個(gè)集合的數(shù)據(jù)union，最后看有幾個(gè)集合。

KMP算法：

當(dāng)一段字符串有公共串時(shí)，必然二者有前后位置，所謂KMP算法就是當(dāng)一個(gè)字符串比對(duì)到一個(gè)位置不匹配時(shí)，看這個(gè)字符前面的字符串擁有的最長公共子序列，將公共前綴的位置移動(dòng)到公共后綴的位置，然后繼續(xù)進(jìn)行比較。

所謂的next數(shù)組即公共前綴的下標(biāo)的再下一個(gè)位置。

經(jīng)典解法：所加特殊字符沒有特殊要求，它只是一種標(biāo)記而已

求每個(gè)位置最長回文子串的長度放于數(shù)組

R：之前所擴(kuò)所有位置所到達(dá)的最右回文右邊界

C：取得更遠(yuǎn)邊界時(shí)中心點(diǎn)位置，二者是伴生狀態(tài)

1）當(dāng)前沒在最右回文右邊界R內(nèi)，暴力擴(kuò)展并進(jìn)行R和c的更新

2）當(dāng)前來到最右回文右邊界內(nèi)部，此時(shí)i必然在C的右側(cè)，i關(guān)于C做一個(gè)對(duì)稱點(diǎn)S，由S向兩側(cè)盡力擴(kuò)展

1.如果S的最左回文右邊界沒有超出C的左邊界，則繼續(xù)i+1.

2.S的最左回文右邊界超過了C的左邊界，那么根據(jù)對(duì)稱關(guān)系，我們只能保證i在邊界內(nèi)部的部分是回文，再向右位置不是回文，可以證明

X==Y,Y==Z如果Z==P的話那么以C為中心的回文必然會(huì)擴(kuò)大，與原題設(shè)矛盾，故Z！=P。

3.S向兩邊擴(kuò)壓線L，則i的回文可能更向右，需要i繼續(xù)嘗試

注：S為之前已經(jīng)求過回文子串長度的位置，這是一種由于回文子串對(duì)稱性帶來的加速。C對(duì)于這種加速做了前提保證一一我本身就是回文子串，可以利用我的對(duì)稱性。

總結(jié)：說白了這種求最長回文子串長度數(shù)組的算法，利用了回文子串具有對(duì)稱性來進(jìn)行加速的一一盡量在回文字串范圍內(nèi)部求解。

for循環(huán)內(nèi)第一句求的是以當(dāng)前節(jié)點(diǎn)為中心至少擁有的回文子串長度，之后視情況還會(huì)再while循環(huán)內(nèi)部更新

滑動(dòng)窗口：雙端隊(duì)列實(shí)現(xiàn)，內(nèi)部存放下標(biāo)既可以得到位置又可以得到數(shù)據(jù)。

R向右動(dòng)：要保證內(nèi)部數(shù)據(jù)從大到小，一旦遇到數(shù)據(jù)大于等于就一個(gè)一個(gè)彈出，直至符合嚴(yán)格遞減才可以放入

L向右動(dòng)：L向右動(dòng)看一下哪個(gè)位置信息過期，如果他是雙端隊(duì)列頭部位置就彈出，不是就不用管

雙端隊(duì)列存放的是可能性，局部最大值的可能性排列

猜測：可以先讓全部數(shù)據(jù)進(jìn)隊(duì)列，即R++，然后一個(gè)一個(gè)出隊(duì)列，即L++，每一次L++都會(huì)過期一個(gè)數(shù)據(jù)，沒過期一個(gè)數(shù)據(jù)就看一下他的下標(biāo)是否和隊(duì)頭下標(biāo)相同，如果相同就彈出隊(duì)頭下標(biāo)，否則當(dāng)前局部最大值就是淘汰元素自己本身。

這是因?yàn)槿绻^期元素下標(biāo)如果和隊(duì)頭下標(biāo)差距很多，說明隊(duì)頭元素淘汰過很多元素，而又因?yàn)檫@個(gè)隊(duì)是嚴(yán)格遞減的淘汰的元素也必然是嚴(yán)格遞減的，所以說明一件事情一一從當(dāng)前淘汰元素到隊(duì)頭元素下標(biāo)的前一個(gè)位置所有的值一定是嚴(yán)格遞減的。

例如本題中按所猜想試驗(yàn)一下：

隊(duì)中元素：如果先一股腦只進(jìn)隊(duì)emmmmm只有7，說明何時(shí)進(jìn)隊(duì)何時(shí)出隊(duì)存在調(diào)度問題

改正：先讓自由窗口變?yōu)榇笮?的然后每次再加一個(gè)數(shù)讓一個(gè)數(shù)過期，即先R++再L++......

尋找每一個(gè)數(shù)左邊和右邊離他最近且比他大的數(shù)據(jù)的下標(biāo)。

單調(diào)棧：設(shè)計(jì)一個(gè)棧按自底向上單調(diào)遞減的依次壓入棧中，如果遇到數(shù)據(jù)S破環(huán)規(guī)律就彈出棧頂元素，新棧頂和這個(gè)破環(huán)規(guī)則的數(shù)S構(gòu)成了左右邊界，記錄下來。再看S是否破環(huán)這個(gè)新棧規(guī)律，重復(fù).......

以上若有重復(fù)元素就掛在元素鏈的后面

party of happy value

Morris遍歷：前提是可以改變底層節(jié)點(diǎn)空閑指針，又稱線索二叉樹。

流程：

1.當(dāng)前節(jié)點(diǎn)cur：如果它有左樹，就尋找它左樹上最右節(jié)點(diǎn)，

1）如果最右節(jié)點(diǎn)的右指針為null就讓它指向cur，然后cur來到它的左孩子

2）否則如果不是null（那就是指向了當(dāng)前節(jié)點(diǎn)本身），說明當(dāng)前cur節(jié)點(diǎn)是第二次遍歷，那就重新回到cur，并且把最右節(jié)點(diǎn)右指針置null，然后來到cur的右孩子

2.如果cur沒有左樹，就來到它的右孩子，重復(fù)以上1.操作優(yōu)先執(zhí)行左孩子

3.如果左右都為null就結(jié)束

如果一個(gè)節(jié)點(diǎn)沒有左樹說明它不會(huì)被二次遍歷。

如果一個(gè)節(jié)點(diǎn)有左樹，一定能回到它自己兩次。

代碼

先序：如果一個(gè)節(jié)點(diǎn)只能到達(dá)它一次直接打印，如果可以到達(dá)兩次，就第一次打印。

如果沒有左樹，說明當(dāng)前節(jié)點(diǎn)只能到達(dá)一次，先打印再向右；如果有左樹就在大if里面的小if里先打印再向左，因?yàn)檫@里代表了第一次遍歷

中序：只能到達(dá)一次的節(jié)點(diǎn)，直接打印，可以到達(dá)兩次的節(jié)點(diǎn)第二次打印。

如果沒有左樹直接打印，因?yàn)橹荒鼙闅v一次，如果有左樹就在大if里面的else里面打印，因?yàn)檫@是第二次遍歷。

而在這里的代碼中中了else以后先修改了最右節(jié)點(diǎn)，然后逐步跳出大if，然后進(jìn)行了打印，從功能上來說符合了邏輯。正常來說可以在這個(gè)else中打印后直接continue，這樣寫代碼相當(dāng)于簡化了

后序：把打印時(shí)機(jī)放在能打印兩次的節(jié)點(diǎn)上，在第二次到達(dá)某一結(jié)點(diǎn)時(shí)逆序打印自己左樹的右邊界。

盡量不要用棧，會(huì)增加空間復(fù)雜度，我們可以將左樹右邊界進(jìn)行逆序然后打印，最后再逆序回來。

判斷一個(gè)樹是否是搜索二叉樹：中序遍歷時(shí)一直是升序即可

思想方法和布隆過濾器一樣，先看這些數(shù)大部分分布在什么范圍，然后再看哪些部分很少涉獵，一步步細(xì)分。

將這些數(shù)放在512個(gè)桶中，看哪個(gè)桶的數(shù)最少再仔細(xì)研究，其中每個(gè)桶包含一定范圍的數(shù)，將這個(gè)定位的范圍再分成512份......

進(jìn)一步假設(shè)只能申請(qǐng)有限幾個(gè)變量，進(jìn)行詞頻統(tǒng)計(jì)，一步步二分。

可以用哈希函數(shù)分流

看1G內(nèi)存最多有多少條記錄一一key：桶序號(hào) value：詞頻數(shù)，看看能分成多少個(gè)小文件，一個(gè)小文件有多少記錄，然后細(xì)分

位圖的方法：用位圖的兩位表示出現(xiàn)次數(shù)，00（0次），01（1次），10（2次），11（多次）。

尋找中位數(shù)依然是范圍統(tǒng)計(jì)的思想，先進(jìn)行詞頻統(tǒng)計(jì)，然后看位于中間的數(shù)在哪一個(gè)桶中，對(duì)這個(gè)捅進(jìn)行仔細(xì)篩查查找正好處于20億位的數(shù)。

先看這5G內(nèi)存大致可以存放多少詞條，由此來確定建立一個(gè)小根堆（按照key值進(jìn)行排序）有多大（2的27次方），有符號(hào)數(shù)為2的32次方，一份2的27次方有2的5次方份（即統(tǒng)計(jì)2的5次方份）。

先統(tǒng)計(jì)最小范圍的數(shù)據(jù)，不在此范圍的數(shù)據(jù)進(jìn)行忽略，統(tǒng)計(jì)完此范圍之后，從小根堆依次彈入到新文件，然后進(jìn)行下一個(gè)范圍的數(shù)據(jù)統(tǒng)計(jì)......

說白了一個(gè)范圍一個(gè)范圍的進(jìn)行統(tǒng)計(jì)，但是盡量堆大一點(diǎn)，這樣每次就可以多統(tǒng)計(jì)一些。

第二種方法：做一個(gè)只能放下三個(gè)記錄的大根堆，不夠三條記錄就加進(jìn)去，加入過就詞頻++，每有一個(gè)數(shù)比堆頂大就跳過，小就彈出堆頂將其入堆，統(tǒng)計(jì)完一遍之后彈入小根堆，并且記住這里面最大的那個(gè)數(shù)以便下一次進(jìn)行劃分范圍。

注：大根堆可以進(jìn)行前n個(gè)最小數(shù)據(jù)的統(tǒng)計(jì)

位運(yùn)算

n右移31位得到符號(hào)位，然后&1

sign可以得到符號(hào)，scA、scB必然一個(gè)是0，一個(gè)是1，缺點(diǎn)是可能會(huì)產(chǎn)生溢出。

改進(jìn)

2的冪：二進(jìn)制只有一個(gè)1，所以x減去x與上自己的取反加一等于0或者自身減去1之后令所有的1打散一一x&（x-1）==0

4的冪：只有一個(gè)1并且1后面有偶數(shù)個(gè)

x&（010101.。。。。）！=0是

加減運(yùn)算

或（無進(jìn)位相加 ）

利用&然后再向左移動(dòng)一位為進(jìn)位

然后二者再或.....

及重復(fù)兩次：先求無進(jìn)位相加再求進(jìn)位，再來一次不斷重復(fù)計(jì)算無進(jìn)位相加和求進(jìn)位運(yùn)算，直至沒有進(jìn)位為止。

減法即加b的相反數(shù).....

乘法

乘數(shù)如果是0直接復(fù)制被乘數(shù)是1就復(fù)制，并且每次伴隨著左移運(yùn)算。

被乘數(shù)每次向左移動(dòng)一位實(shí)現(xiàn)每次錯(cuò)開一位的操作，b每次向右移一位直至成為0，運(yùn)算結(jié)束

除法

假設(shè)被除數(shù)a：0110111 除數(shù)b：00011

嘗試a-（b左移17位）不能就跳過，依次嘗試16、15、14......直到能減得出結(jié)果a‘，再讓

a’嘗試減去b向左移動(dòng)3位、2位......得到a‘’，由于不能再減了就忽略

一步步讓a嘗試減去b左移位數(shù)得到的新值進(jìn)行更新，直至最后可以視為0

讓x右移相當(dāng)于讓y左移然后進(jìn)行比較，但是y左移面臨溢出的危險(xiǎn)，不如讓x右移

以下版本是考慮正負(fù)號(hào)的

略，此處為動(dòng)態(tài)規(guī)劃，前文已講?。。。。?/p>

略，此處為動(dòng)態(tài)規(guī)劃的補(bǔ)充部分，已經(jīng)歸到了動(dòng)態(tài)規(guī)劃最后一節(jié)。

有序表：O（logn），可以由紅黑樹、AVL樹、SB樹以及跳表（skiplist）實(shí)現(xiàn)，他們之間只有常數(shù)時(shí)間的區(qū)別。但是利用樹實(shí)現(xiàn)的結(jié)構(gòu)一一BST，必然會(huì)用到平衡樹、樹旋轉(zhuǎn)的概念。

搜索樹，對(duì)于每一個(gè)當(dāng)前頭節(jié)點(diǎn)，左樹都比自己小，右樹都比自己大。

增加：按規(guī)律加入即可。

查找：一個(gè)數(shù)據(jù)和6最為接近，6如果發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)比6小就去它的右樹找，如果比自己大就去左樹找。

刪除：

1）有左右孩子 找到自己左樹的最右節(jié)點(diǎn)或者自己右樹的最左節(jié)點(diǎn)，將它的所有孩子交給自己的父親，然后去替代刪除節(jié)點(diǎn)的位置。最后返回刪除的數(shù)據(jù)。（即左樹上面最大的或者右樹上面最小的）

2）沒有左右孩子，直接刪除返回

3）刪除節(jié)點(diǎn)只有左孩子或者右孩子，直接讓孩子替代然后返回即可。

但是這樣建立的樹沒有平衡性，建立平衡搜索二叉樹還需要進(jìn)一步操作BST。而這里的平衡性要求不是太嚴(yán)格，只需保證任何一個(gè)結(jié)點(diǎn)的左右兩樹相差不大一一高度相差不太大或者個(gè)數(shù)差不多

下面我們利用左旋和右旋這兩個(gè)基本操作進(jìn)行平衡性的實(shí)現(xiàn)。

AVL、SB、紅黑樹之間的共同特點(diǎn)是都利用了左右旋這兩個(gè)基本操作進(jìn)行平衡性的實(shí)現(xiàn)，區(qū)別是它們判定何時(shí)需要進(jìn)行平衡操作的條件以及怎么用這兩個(gè)操作不一樣。

AVL樹：維持高度信息

下面作為主要實(shí)例進(jìn)行講解

SB樹：節(jié)點(diǎn)數(shù)量信息

LL//RR型：左孩子的左孩子個(gè)數(shù)大于右孩子個(gè)數(shù)，先對(duì)T做一個(gè)右旋L上去，m（T）表示以哪個(gè)節(jié)點(diǎn)為頭進(jìn)行調(diào)整，原則是右旋之后發(fā)現(xiàn)哪個(gè)節(jié)點(diǎn)的孩子發(fā)生變化了，調(diào)函數(shù)對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行操作，這里是T變了，所以再來一個(gè)m（T），L節(jié)點(diǎn)也變化了，來一個(gè)m（T）

m（T）{

1）右旋；

2）m（T）

3）m（L）

}//左旋就第一步變化

LR//RL型：左孩子的右孩子大小大于右樹，想辦法讓B變成頭部。先對(duì)L左旋，然后對(duì)T右旋，然后誰的孩子變化了重復(fù)m誰

紅黑樹：1）每一個(gè)節(jié)點(diǎn)非黑即紅 2）頭節(jié)點(diǎn)和葉結(jié)點(diǎn)（最底層的空節(jié)點(diǎn)）必須為黑 3）任何兩個(gè)紅結(jié)點(diǎn)不能相鄰 4）從任何一個(gè)當(dāng)前cur結(jié)點(diǎn)出發(fā)，每一條到達(dá)結(jié)束路徑的黑節(jié)點(diǎn)數(shù)量一樣一一保證了最長和最短路徑長度不超過二倍關(guān)系。

檢查違規(guī)情況中，新增標(biāo)準(zhǔn)的操作5個(gè)，刪除標(biāo)準(zhǔn)8個(gè)。

********************************************************************************************************************

如果左旋只操作頭節(jié)點(diǎn)和他的右孩子；如果右旋只操作頭節(jié)點(diǎn)和他的左孩子。

********************************************************************************************************************

AVL樹

一個(gè)重要的問題是這些樹是如何意識(shí)到自己是否是不平衡的吶？

對(duì)于AVL樹，它每加入一個(gè)節(jié)點(diǎn)，都會(huì)往上檢查它的平衡性，假如加入一個(gè)節(jié)點(diǎn)x ，當(dāng)x來到了自己合適的位置時(shí)，它會(huì)先檢查x處是否有平衡性，然后沿著父節(jié)點(diǎn)一步步檢查平衡性，沒有就利用左右旋轉(zhuǎn)進(jìn)行平衡。

刪除一個(gè)節(jié)點(diǎn)時(shí)，比如說刪除節(jié)點(diǎn)5，先進(jìn)行完

刪除操作，利用6進(jìn)行替代，并將6的孩子托付給自己的父親...，然后從自己的父親7開始向上進(jìn)行檢查平衡性一一相當(dāng)于7的結(jié)構(gòu)被修改過了所以要進(jìn)行檢查，而6原來的孩子本身就有平衡性不需要進(jìn)行檢查。

那檢查出什么樣子就算不平衡吶，分為4種情況：

（節(jié)點(diǎn)用?代替，子樹用??代替）

左樹的左邊過長一一右旋操作，右樹的右邊過長一一左旋，

左樹的右邊過長一一讓最底層考慮的節(jié)點(diǎn)x轉(zhuǎn)成頭部即可（先對(duì)y左旋讓x上去，然后讓z右旋再讓x上去）。

右樹的左邊過長一一讓最底層考慮的節(jié)點(diǎn)c轉(zhuǎn)成頭部即可（先對(duì)b進(jìn)行右旋讓c上去，再對(duì)z進(jìn)行左旋讓c上去）

這些調(diào)整都是常數(shù)型的，下面看具體實(shí)現(xiàn)：旋轉(zhuǎn)操作自帶高度更新，如果沒有進(jìn)行旋轉(zhuǎn)，也會(huì)進(jìn)行一次更新一一updateHeight。做完當(dāng)前節(jié)點(diǎn)之后，向上繼續(xù)進(jìn)行修改。

跳表

可以認(rèn)為是一個(gè)多鏈表skiplist

{

1.假設(shè)有一個(gè)默認(rèn)節(jié)點(diǎn)，默認(rèn)它的key是全局最小的，開始只有一條向外指的指針。

增加節(jié)點(diǎn)操作：

while{

2.現(xiàn)在用戶開始加數(shù)據(jù)，封裝數(shù)據(jù)之后，開始搖骰子，用以決定這個(gè)新節(jié)點(diǎn)有幾條指針，如果指針數(shù)量比當(dāng)前默認(rèn)節(jié)點(diǎn)數(shù)量多的話，默認(rèn)節(jié)點(diǎn)也要增加指針。還要將新節(jié)點(diǎn)的所有指針置為null。

3.下一步進(jìn)行添加操作這里我們假設(shè)跳表已經(jīng)有了一定的數(shù)據(jù)量，詳述具體添加操作。

從默認(rèn)節(jié)點(diǎn)最高層開始，如果最高層指向null一一說明這個(gè)新節(jié)點(diǎn)更新了層數(shù)，就讓最高層指向新節(jié)點(diǎn)，然后繼續(xù)下一層，以下遵守下列原則：

/*當(dāng)前新節(jié)點(diǎn)記作cur。*/

****************************************************************************************************************************************************************************** 以 默認(rèn)節(jié)點(diǎn)為對(duì)象從最高層指針開始，假設(shè)進(jìn)行檢驗(yàn)的節(jié)點(diǎn)記為S,初始化S=默認(rèn)節(jié)點(diǎn)。

1）S指向的下一個(gè)數(shù)據(jù)比cur大

①比cur層數(shù)高就反彈回來，S節(jié)點(diǎn)直接進(jìn)行下一層的檢驗(yàn)。

②和cur層數(shù)一樣，S節(jié)點(diǎn)本層就指向cur，而cur最高層指針就承接S節(jié)點(diǎn)指針的數(shù)據(jù)，開始進(jìn)行S節(jié)點(diǎn)的下一層嘗試。

//③默認(rèn)節(jié)點(diǎn)不可能比cur層數(shù)低

2）S節(jié)點(diǎn)指向的下一個(gè)數(shù)據(jù)比cur小就跳轉(zhuǎn)到下一個(gè)數(shù)據(jù)，重復(fù)1）2）......

******************************************************************************************************************************************************************************

}

}

//從最高層開始是進(jìn)行檢查的一個(gè)加速

例子

刪除節(jié)點(diǎn)操作：

先進(jìn)行查找后進(jìn)行刪除，大體還是利用了增加操作的很多思想，這里不再進(jìn)行贅述。