基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的融合是成為龐大系統(tǒng)的基石。比如Redis中的跳躍表，數(shù)據(jù)庫(kù)索引B+樹(shù)等，只有對(duì)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)足夠的熟悉才能更容易去理解稍微復(fù)雜的結(jié)構(gòu)，就仿佛我們闖關(guān)打怪一樣，一步一步解鎖直到結(jié)局。今天想和大家一起分享的是常見(jiàn)數(shù)據(jù)結(jié)構(gòu)以及面試中的高頻手撕算法題，一定要去手動(dòng)寫(xiě)這些代碼，可說(shuō)百分之七八十都是這些題，一定要好好掌握。

高頻手撕算法合集

1、數(shù)據(jù)結(jié)構(gòu)

鏈表屬于數(shù)據(jù)結(jié)構(gòu)中的線(xiàn)性結(jié)構(gòu)的一種，我們先看看什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是：結(jié)構(gòu)的定義+結(jié)構(gòu)的操作

想必大伙兒應(yīng)該玩兒過(guò)拼圖，拼圖之前我們先看看說(shuō)明書(shū)，看看包含幾個(gè)部分，然后對(duì)這些部分進(jìn)行拼裝，隨后拼好候進(jìn)行組合直到完成。

那么數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)定義是這個(gè)數(shù)據(jù)結(jié)構(gòu)長(zhǎng)什么樣子，有些什么性質(zhì)？結(jié)構(gòu)的操作意思是這個(gè)結(jié)構(gòu)可以支持什么操作，但是不管你怎么的操作，不能破壞了它的結(jié)構(gòu)

2、鏈表定義

一個(gè)鏈表是由1個(gè)或者多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含兩個(gè)信息，一個(gè)是數(shù)據(jù)信息，用來(lái)存儲(chǔ)數(shù)據(jù)，一個(gè)是地址信息，用來(lái)存儲(chǔ)下個(gè)節(jié)點(diǎn)的地址。

鏈表節(jié)點(diǎn)
鏈表結(jié)構(gòu)由一個(gè)個(gè)節(jié)點(diǎn)組成，我們不需要對(duì)結(jié)構(gòu)做任何改變，只需要按照需求修改鏈表結(jié)構(gòu)中的數(shù)據(jù)域即可。從上圖我們知道此事數(shù)據(jù)域類(lèi)型為整型763，指針域?yàn)?x56432，這個(gè)地址正好是第二個(gè)節(jié)點(diǎn)的地址，所以這兩個(gè)節(jié)點(diǎn)在邏輯上是有個(gè)指向關(guān)系，也是通過(guò)這種方式將兩個(gè)節(jié)點(diǎn)進(jìn)行了關(guān)聯(lián)。

第二個(gè)節(jié)點(diǎn)中的指針域?yàn)?x0，這是一個(gè)特殊的地址，叫做空地址，指向空地址意味著它是這個(gè)鏈表結(jié)構(gòu)的最后一個(gè)節(jié)點(diǎn)。

那在代碼中是什么樣子呢

structNode{ intdata; structNode*next; };

這個(gè)結(jié)構(gòu)很清晰，數(shù)據(jù)域根據(jù)我們的需求而定，想存整型就改成整型，想存字符串就寫(xiě)字符串。而指針域用來(lái)維護(hù)整個(gè)鏈表結(jié)構(gòu)，一般來(lái)說(shuō)直接用即可，如果需要內(nèi)存中的鏈表結(jié)構(gòu)，一定要修改節(jié)點(diǎn)內(nèi)部next指針域中存儲(chǔ)的地址值

3、鏈表操作

說(shuō)到鏈表結(jié)構(gòu)，我們習(xí)慣性的和數(shù)組聯(lián)系在一起。只是數(shù)組結(jié)構(gòu)在內(nèi)存中是連續(xù)的，而鏈表結(jié)構(gòu)因?yàn)橹羔樣虻拇嬖?，每個(gè)節(jié)點(diǎn)在內(nèi)存中存儲(chǔ)的位置未必連續(xù)。下面我們按照數(shù)組的方式給鏈表也編個(gè)號(hào)。

單鏈表

下面我們定義一個(gè)向鏈表插入節(jié)點(diǎn)的函數(shù)

structNode*insert(structNode*head,intind,structNode*a);

第一個(gè)參數(shù)為待操作的鏈表的頭結(jié)點(diǎn)地址，也就是第一個(gè)節(jié)點(diǎn)的地址

第二個(gè)參數(shù)為插入位置

第三個(gè)參數(shù)為指針變量，指向要插入的新節(jié)點(diǎn)

簡(jiǎn)單的說(shuō)就是向 head 指向的鏈表的 ind 位置插入一個(gè)由 a 指向的節(jié)點(diǎn)，返回值為插入新節(jié)點(diǎn)后的表頭地址。為什么要返回它呢？因?yàn)槲覀儾迦氲墓?jié)點(diǎn)很可能在頭部，此時(shí)就會(huì)改變鏈表的結(jié)構(gòu)且改變頭結(jié)點(diǎn)地址，所以需要返回。

那么我們插入一個(gè)元素，顯然會(huì)改變鏈表的節(jié)點(diǎn)，操作方法為修改鏈表節(jié)點(diǎn)的 next 指針域即可，那么為了插入成功，我們需要修改哪些節(jié)點(diǎn)呢？

首先是讓 ind - 1 位置的節(jié)點(diǎn)指向 a 節(jié)點(diǎn)，然后是 a 節(jié)點(diǎn)指向原 ind 位置的節(jié)點(diǎn)，也就是說(shuō)，涉及到兩個(gè)節(jié)點(diǎn)的 next 指針域的值的修改，一個(gè)是 ind - 1 位置的節(jié)點(diǎn)，一個(gè)是 a 節(jié)點(diǎn)自身。我們就可以先找到 ind - 1 位置的節(jié)點(diǎn)，然后再進(jìn)行相關(guān)操作即可。

structNode*insert(structNode*head,intind,structNode*a){ structNoderet,*p=&ret; ret.next=head; //從虛擬頭節(jié)點(diǎn)開(kāi)始向后走ind步 while(ind--)p=p->next; //完成節(jié)點(diǎn)的插入操作 a->next=p->next; p->next=a; //返回真正的鏈表頭節(jié)點(diǎn)地址 returnret.next; }

這里非常關(guān)心且非常重要的是虛擬節(jié)點(diǎn)。我們?yōu)槭裁匆胩摂M節(jié)點(diǎn)？是為了讓我們的插入操作統(tǒng)一化？什么是統(tǒng)一化？舉個(gè)例子，假設(shè)我們現(xiàn)在是在第5個(gè)位置插入元素，我們自然需要從頭遍歷到第四個(gè)節(jié)點(diǎn)，確定了第四個(gè)節(jié)點(diǎn)后，修改相關(guān)的next指針域，也就是如果我們想插入到 nid 位，就需要從頭節(jié)點(diǎn)向后移動(dòng) ind-1 步，那么如果插入的位置為0呢？我們總不能走-1步吧，所以這個(gè)時(shí)候我們只好對(duì)ind=0的情況進(jìn)行單獨(dú)的判斷了，這樣明顯是不完美了，所以我們?yōu)榱私y(tǒng)一ind在等于0和不等于0時(shí)的情況，引入虛擬節(jié)點(diǎn)。

ok，我們看看是不是方便了。增加了虛擬節(jié)點(diǎn)，如果插入第5個(gè)位置，我們只需要向后移動(dòng)5位，如果插入到0號(hào)位置，向后移動(dòng)0步即可，即p指針指向虛擬節(jié)點(diǎn)不懂，直接將新的節(jié)點(diǎn)插入到虛擬頭結(jié)點(diǎn)后面完事兒。

虛擬節(jié)點(diǎn)

好勒，這里出現(xiàn)了第一個(gè)重要的技巧。在我們插入鏈表節(jié)點(diǎn)的時(shí)候，加上虛擬節(jié)點(diǎn)是個(gè)實(shí)用技巧。

那么我們看看插入和刪除的操作動(dòng)態(tài)以及實(shí)現(xiàn)方式

3、案例

案例1

我們看個(gè)題吧，定義一個(gè)快樂(lè)數(shù)，什么是快樂(lè)數(shù)，所謂快樂(lè)數(shù)即通過(guò)有限次變換后等于1 的數(shù)字。怎么變換呢，給出一個(gè)非1的數(shù)字，然后出去位數(shù)，求各個(gè)位數(shù)的平方和，得到數(shù)字A，假設(shè)A不死1，那就繼續(xù)對(duì)元素A的每一位進(jìn)行平方和，得到數(shù)字B。。。。知道最后能夠=1

例如，一開(kāi)始的數(shù)字是 19，經(jīng)過(guò)變換規(guī)則 ，得到數(shù)字 82；因?yàn)椴皇?1 ，所以接著做變換，就是 ，再做一次變換 ，最后一次做變換，得到了 1 以后，停止

這個(gè)題的難點(diǎn)不是判斷數(shù)是不是快樂(lè)數(shù)，而是如何判斷一個(gè)數(shù)不是快樂(lè)數(shù)，如果不是快樂(lè)數(shù)，說(shuō)明沒(méi)有辦法通過(guò)有限的次數(shù)到達(dá)數(shù)字1，那么到底是 經(jīng)過(guò)多少次呢？1k次，10w次？很難確定上限。在說(shuō)這個(gè)問(wèn)題之前我們先看幾個(gè)高頻鏈表練習(xí)題

例題1 用數(shù)組判斷鏈表中是否有環(huán)

在上面我們介紹了最后一個(gè)節(jié)點(diǎn)指向空，可是你有沒(méi)有想過(guò)如果鏈表的最后一個(gè)節(jié)點(diǎn)不是空地址而是指向鏈表中的一個(gè)節(jié)點(diǎn)，這不就是環(huán)了？

鏈表環(huán)

如上圖所示，節(jié)點(diǎn)8指向了3，這樣形成了3,4,5,6,7,8的環(huán)狀結(jié)構(gòu)，此時(shí)使用指針遍歷鏈表將永無(wú)止境。那通過(guò)什么辦法判斷是否有環(huán)呢？

使用數(shù)組標(biāo)記的方法。記錄出現(xiàn)過(guò)的節(jié)點(diǎn)信息，每次遍歷新節(jié)點(diǎn)就去數(shù)組查看記錄，這樣的時(shí)間復(fù)雜度不給力。經(jīng)過(guò)第一個(gè)節(jié)點(diǎn)，需要在數(shù)組查找0次，第2個(gè)節(jié)點(diǎn)，數(shù)組查找1次，第i個(gè)節(jié)點(diǎn)，在數(shù)組查找i-1次，直到遍歷第n+1個(gè)節(jié)點(diǎn)，查找的總次數(shù)為(n + 1) * n / 2，這樣時(shí)間復(fù)雜度為O(n^2)。太慢了，給我優(yōu)化

快慢指針?lè)?/p>

AB兩位同學(xué)跑步，A同學(xué)速度快，B同學(xué)速度慢，他們并不知道跑道是環(huán)形的，如果是環(huán)形，跑得快的，在足夠的時(shí)間終究會(huì)從速度慢的B同學(xué)經(jīng)過(guò)，形成相遇的情況。如果不是環(huán)形，速度快的先到重點(diǎn)，不會(huì)相遇---快慢指針?lè)ā?/p>

快慢指針

在這里，我們將鏈表當(dāng)做跑道，跑道上兩個(gè)指針，指針A每次走兩步，指針B每次走兩步，如果快的指針先跑到終點(diǎn)注定沒(méi)有環(huán)，如果兩指針相遇則有環(huán)。

inthasCycle(structNode*head){ if(head==NULL)return0; //p是慢指針，q是快指針 structNode*p=head,*q=head; //每次循環(huán)，p走1步，q走2步 do{ p=p->next; q=q->next; if(q==NULL)return0; q=q->next; }while(p!=q&&q); returnp==q; }

3、二分查找初探

說(shuō)到二分查找，這里就有個(gè)笑話(huà)了。

小孫同學(xué)去圖書(shū)館借書(shū)，一次性了借了40本書(shū)，出圖書(shū)館的時(shí)候報(bào)警了，不知道哪一本書(shū)沒(méi)有消磁，然后把書(shū)放在地上，準(zhǔn)備一本本嘗試。

女生的操作被旁邊的阿姨看見(jiàn)了，阿姨說(shuō)你這樣操作多慢啊，我來(lái)教你。于是將樹(shù)分為兩摞，拿出第一luo過(guò)一下安檢，安檢機(jī)器想了，于是阿姨將這摞書(shū)分成兩部分，拿出一部分繼續(xù)嘗試，就這樣，阿姨每次減少一半，沒(méi)幾次就找到了沒(méi)有消磁的書(shū)。阿姨嘚瑟的來(lái)一句：小姑涼，這就是書(shū)中的二分查找算法，你這還得好好學(xué)習(xí)哇，第二天，圖書(shū)館發(fā)現(xiàn)丟了39本書(shū)。哈哈哈哈

4、二分查找基礎(chǔ)

最簡(jiǎn)單的二分算法即在一個(gè)有序數(shù)組中，查找一個(gè)數(shù)字X是否存在。注意有序性。那么如何在數(shù)組中查找一個(gè)數(shù)

從頭到尾一個(gè)一個(gè)查找，找到即有數(shù)字x

二分算法即通過(guò)確定一個(gè)區(qū)間，然后查找區(qū)間的一半和x比較，如果比x大則在x前半段查找。如果比x小則在后半段查找，只需要log2n的比較即可確定結(jié)果。

二分初探

圖中呢，我們以查找 17 這個(gè)數(shù)字為例，L 和 R 所圈定的，就是當(dāng)前的查找區(qū)間，一開(kāi)始 L= 0，R = 6，mid 所指向的就是數(shù)組的中間位置，根據(jù) L 和 R 計(jì)算得到 mid 的值是 3。查看數(shù)組第 3 位的值是 12，比待查找值 17 要小，說(shuō)明如果 17 在這個(gè)有序數(shù)組中，那它一定在 mid 所指向位置的后面，而 mid 本身所指向的數(shù)字已經(jīng)確定不是 17 了，所以下一次我們可以將查找區(qū)間，定位到 mid + 1 到 R，也就是將 L 調(diào)整到 mid + 1 （即數(shù)組第 4
位）的位置。

1 第一種小白寫(xiě)法

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?(left+right)/2; ????????if?(nums[mid]?==?target)?return?mid; ????????else?if?(nums[mid]?

面試官發(fā)話(huà)了

方法二優(yōu)化版

如果right和left比較的時(shí)候，兩者之和可能溢出。那么改進(jìn)的方法是mid=left+(right-left)/2.還可以繼續(xù)優(yōu)化，我們將除以2這種操作轉(zhuǎn)換為位運(yùn)算mid=left+((right-left)>>1).

哪有這么簡(jiǎn)單的事兒，大多數(shù)的筆試面試中可能會(huì)出現(xiàn)下面的幾種情況。

四 、二分的各種變種

這里主要是看看原始數(shù)組有重復(fù)數(shù)的情況。

二分

1 查找第一個(gè)值等于給定值的情況(查找元素7)
思路

首先7與中間值a[4]比較，發(fā)現(xiàn)小于7，于是在5到9中繼續(xù)查找，中間a[7]=7,但是這個(gè)數(shù)7不是第一次出現(xiàn)的。那么我們檢查這個(gè)值的前面是不是等于7，如果等于7，說(shuō)明目前這個(gè)值不是第一次出現(xiàn)的7，此時(shí)更新rihgt=mid-1。ok我們看看代碼

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?left+((right-left)>>1); if(nums[mid]>value) { right=mid-1; }elseif(nums[mid]

2 查找最后一個(gè)值等于給定值的情況

假設(shè)nums[mid]這個(gè)值已經(jīng)是最后一個(gè)元素了，那么它肯定是要找到最后一個(gè)值。如果nums[mid]的下一個(gè)不等于value，那說(shuō)明nums[mid]就是我們需要找到最后一個(gè)等于給定值的值。

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?left+((right-left)>>1); if(nums[mid]>value) { right=mid-1; }elseif(nums[mid]

3 查找第一個(gè)大于等于給定值的情況

如果nums[mid]小于要查找的值，那么我們需要查找在[mid+1,right]之間，所以此時(shí)更新為left=mid+1

如果nums[mid]大于給定值value,這個(gè)時(shí)候需要查看nums[mid]是不是我們需要找的第一個(gè)值大于等于給定值元素，如果nums[mid]前面沒(méi)有元素或者前面一個(gè)元素小于查找的值，那么nums[mid]就是我們需要查找的值。相反

如果nums[mid-1]也是大于等于查找的值，那么說(shuō)明查找的元素在[left,mid-1]之間，所以我們需要將right更新為mid-1

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?left+((right-left)>>1); if(nums[mid]>value) { right=mid-1; }elseif(nums[mid]

4 查找第一個(gè)大于等于給定值的情況

如果nums[mid]小于要查找的值，那么我們需要查找在[mid+1,right]之間，所以此時(shí)更新為left=mid+1

如果nums[mid]大于給定值value,這個(gè)時(shí)候需要查看nums[mid]是不是我們需要找的第一個(gè)值大于等于給定值元素，如果nums[mid]前面沒(méi)有元素或者前面一個(gè)元素小于查找的值，那么nums[mid]就是我們需要查找的值。相反

如果nums[mid-1]也是大于等于查找的值，那么說(shuō)明查找的元素在[left,mid-1]之間，所以我們需要將right更新為mid-1

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?left+((right-left)>>1); if(nums[mid]>=value) { if(mid==0||nums[mid-1]

5 查找最后一個(gè)小于等于給定值的情況

如果nums[mid]小于查找的值，那么需要查找的值肯定在[mid+1,right]之間，所以我們需要更新left=mid+1

如果nums[mid]大于等于給定的value，檢查nums[mid]是不是我們的第一個(gè)值大于等于給定值的元素

intBinarySerach(vector&nums,intn,inttarget){ intleft=0,right=n-1; while(left<=?right)?{ ????????int?mid?=?left+((right-left)>>1); if(nums[mid]>value) { right=mid-1; }else { if(mid==n-1||(nums[mid+1]>value)) { returnmid; }else { left=mid+1; } } return-1; }

4、隊(duì)列

例子：滑動(dòng)窗口最大值

隊(duì)列回憶：

火車(chē)站買(mǎi)票應(yīng)該都經(jīng)歷過(guò)，窗口小姐姐每次服務(wù)排在最前面的那個(gè)人，買(mǎi)完票則從頭部離開(kāi)，后面人往前一步接替離開(kāi)的人繼續(xù)購(gòu)票，這就是典型的隊(duì)列結(jié)構(gòu)。

計(jì)算機(jī)中的隊(duì)列和其類(lèi)似，先到先得，先入先出，每個(gè)元素從尾部入隊(duì)，從頭部處理完出隊(duì)

隊(duì)列定義

單調(diào)隊(duì)列

假設(shè)將學(xué)生從高年級(jí)到低年級(jí)排列，隨著時(shí)間的推移，高年級(jí)同學(xué)從隊(duì)列頭部畢業(yè)，低年級(jí)從尾部進(jìn)入。大部分學(xué)校都有校隊(duì)，假設(shè)小林高三，我高二，小七高一，小林畢業(yè)接班的是我，我畢業(yè)，很可能就是小七接班，而當(dāng)我進(jìn)隊(duì)的那一刻，小七即使進(jìn)的早但是戰(zhàn)斗力沒(méi)我高，所以小七是永遠(yuǎn)沒(méi)計(jì)劃被選中啦。所以，縱觀全隊(duì)，不僅有著隊(duì)列的性質(zhì)，也有著單調(diào)的性質(zhì)，所以就是單調(diào)隊(duì)列。

為什么需要單調(diào)隊(duì)列

比較明顯的作用是，用來(lái)維護(hù)隊(duì)列處理順序中的區(qū)間最大值。

高頻面試題----滑動(dòng)窗口最大值

滑動(dòng)窗口沒(méi)向后滑動(dòng)一位，就有一個(gè)元素從隊(duì)首出隊(duì)，同時(shí)也會(huì)有個(gè)元素從隊(duì)尾入隊(duì)。這個(gè)題需要求區(qū)間的最大值：意味著需要維護(hù)在隊(duì)列處理順序中的區(qū)間最大值，直接上代碼附上注釋

#defineMAX_N1000 intq[MAX_N+5],head,tail; voidinterval_max_number(int*a,intn,intm){ head=tail=0; for(inti=0;i=m){ printf("interval(%d,%d)",i-m+1,i); printf("=%d ",a[q[head]]); } } return; }

5、棧與單調(diào)棧

棧結(jié)構(gòu)對(duì)應(yīng)于隊(duì)列，可以將棧想象為一個(gè)只有單出口的羽毛球筒，羽毛球只能從單一的入口放入和取出。假設(shè)我們將1，2,3三個(gè)球放進(jìn)球桶，如果取出來(lái)此時(shí)就是3,2,1。性質(zhì)就很明顯了，先進(jìn)后出的結(jié)構(gòu)

棧結(jié)構(gòu)本身維護(hù)的是一種完全包含的關(guān)系。這種包含關(guān)系在函數(shù)之間的運(yùn)行體現(xiàn)的玲離盡致，也就是一種包含關(guān)系，如果主函數(shù)調(diào)用函數(shù)B，那么函數(shù)B一定會(huì)在主函數(shù)結(jié)束之前結(jié)束。

單調(diào)棧

此時(shí)應(yīng)該了解了棧和隊(duì)列，那么我問(wèn)你，你覺(jué)得棧和隊(duì)列最大的區(qū)別是啥？

你可能毫不猶豫的可以回答棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。ok，那我再問(wèn)你，堵住了出口的單調(diào)隊(duì)列和棧有什么區(qū)別？這是不是就沒(méi)什么區(qū)別了，單調(diào)隊(duì)列為了維護(hù)其單調(diào)性，在入隊(duì)的時(shí)候會(huì)將違反單調(diào)性的元素彈出去，這就相當(dāng)于棧的同一段進(jìn)出，是的，堵住出口的單調(diào)隊(duì)列就是我們現(xiàn)在要說(shuō)的單調(diào)棧，目前以單調(diào)遞減棧為例

單調(diào)棧

當(dāng)序列中的12號(hào)元素入棧以后，此時(shí)單調(diào)棧有4個(gè)元素，從棧底到棧頂分別為23,18,15,9，按照原始序列為2 5 9 12。此時(shí)我們關(guān)注12號(hào)元素和9號(hào)元素的關(guān)系。如果12號(hào)元素入棧，為了保證棧的單調(diào)遞減性，最終放在9號(hào)上面，此時(shí)我們雖然不是第十個(gè)元素和十一號(hào)元素值多少，但是這兩個(gè)元素的值一定是比9號(hào)元素小，這就是單調(diào)棧的性質(zhì)。所以，單調(diào)隊(duì)列是用來(lái)維護(hù)區(qū)最值的高效結(jié)構(gòu)，單調(diào)棧呢是維護(hù)最近大于或小于的高效結(jié)構(gòu)。下面看個(gè)例子

題目：判斷括號(hào)序列是否合法

示例 合法

({})
{()}

示例 非合法

([)]
(((){}

publicbooleanisValid(Strings){ Stackstack=newStack<>(); Mapmap=newHashMap<>(); char[]chars=s.toCharArray(); map.put(')','('); map.put('}','{'); map.put(']','['); for(inti=0;i

6、遞推套路

在分享遞推之前，先和大家分享與之緊密的數(shù)學(xué)原理：容斥原理

在計(jì)數(shù)問(wèn)題中，為了保證計(jì)數(shù)的準(zhǔn)確程度，通常會(huì)保證兩個(gè)問(wèn)題，第一個(gè)問(wèn)題是沒(méi)有重復(fù)，第二個(gè)問(wèn)題是沒(méi)有遺漏。這兩個(gè)問(wèn)題相對(duì)來(lái)說(shuō)，第二點(diǎn)比較容易做到。比如對(duì)某地區(qū)進(jìn)行爆炸式轟炸，為了保證炸的覆蓋面，足夠多的炸彈即可，但是如果保障一塊土地只能炸一次就比較難搞了。那么容斥原理就是解決這個(gè)問(wèn)題

容斥原理是什么？

先不考慮重疊的情況，先將所有對(duì)象數(shù)目計(jì)算出來(lái)，然后將重復(fù)計(jì)算的排斥出去，是的，計(jì)算的結(jié)果不僅不遺漏也不重復(fù)。簡(jiǎn)單的說(shuō)就是在計(jì)算的過(guò)程中，如果加多了就減去多的部分，如果減多了就加回來(lái)一部分，直到不多不少。

我們看一個(gè)兔子繁殖問(wèn)題

假設(shè)有一片草原上，莫名其妙來(lái)了一只外星兔子，這種外星兔子呢，第一個(gè)月的時(shí)候是幼體，第二個(gè)月成長(zhǎng)為成體，從第三個(gè)月開(kāi)始，成體兔子每個(gè)月都會(huì)產(chǎn)生出一只克隆體的幼體兔子，而且這種兔子不會(huì)衰老，一旦成體以后，就會(huì)一直生下去。按照這種情況，請(qǐng)你計(jì)算出第 n 個(gè)月，草原上有多
少只兔子？

此時(shí)給出前面6個(gè)月的情況

六個(gè)月兔子情況

從上圖我們可以發(fā)現(xiàn)，從第一個(gè)月到第六個(gè)月，草原上的兔子數(shù)量分別為1,1,2,3,5,8

第六個(gè)月共有8只兔子，其中包含5只成兔，3只幼兔，為什么是5只成兔，因?yàn)榈诹鶄€(gè)月的兔子數(shù)量等于第五個(gè)月的兔子總數(shù)，六個(gè)月的3只幼兔是等于第四個(gè)月的兔子數(shù)量

后三個(gè)月情況

結(jié)論就比較清晰了：從第三個(gè)月開(kāi)始，第n個(gè)月的兔子數(shù)量等于該月的成兔數(shù)量與幼兔數(shù)量之和，也就是等于第n-1個(gè)月的兔子數(shù)量與第n-2兔子數(shù)量之和。這種根據(jù)前面的數(shù)量來(lái)推后面的數(shù)量的情況叫做遞推，那么遞推算法套路通常是怎么樣呢

確定遞推的狀態(tài)，多畫(huà)圖前面幾步

推導(dǎo)遞推公式

程序的編寫(xiě)

我們根據(jù)三步走的方式來(lái)闡釋解決兔子的這個(gè)問(wèn)題

f(n)表示n個(gè)月兔子的數(shù)量

遞推公式(第一個(gè)月合第二個(gè)月兔子的數(shù)量為1，到了第三個(gè)月即等于前面兩個(gè)月之和)

遞推公式

案例2 湊錢(qián)幣問(wèn)題

用 1 元、2 元、5 元、10 元、20 元、50 元和 100
元湊成 1000 元錢(qián)，總共有多少種方案

確定遞推狀態(tài)，需要分析自變量與因變量，自變量?jī)蓚€(gè)分別為幣種種類(lèi)和拼湊的錢(qián)幣數(shù)量，因變量1個(gè)為方案總數(shù)，因此我們的狀態(tài)定義為f(i,j)，i種錢(qián)幣，拼湊j元錢(qián)的方案總數(shù)。比如f [3][10]即使用三種錢(qián)幣，湊出10元的方案總數(shù)

假設(shè)我們不使用第三種錢(qián)幣，那么此時(shí)等價(jià)于使用前兩種錢(qián)幣拼湊10元錢(qián)的方案總數(shù)，即f[2][10]。如果使用至少1張5塊錢(qián)，那么我們?cè)谶@些方案中去掉一張5元錢(qián)，剩下的方案數(shù)為f[3][5]，所以此時(shí)的遞推公式為f[3][10] = f[2][10] + f[3][5]。這只是一般情況，假設(shè)我們沒(méi)有使用第i種錢(qián)幣，拼湊j元的方案為f(i-1,j)，代表使用前i-1種錢(qián)幣的方案總數(shù)。剩下的使用了第i中錢(qián)幣，由于都存在第i錢(qián)幣1張，假設(shè)第i種錢(qián)幣的面額為val[i]，那么此時(shí)我們的前i種錢(qián)幣，湊j-val[i]的錢(qián)數(shù)，此時(shí)方案總數(shù)為f(i,j-val[i])；所以公式為f(i,j)=f(i-1,j)+f(i,j-val[i])

推理

7、動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃通常簡(jiǎn)稱(chēng)DP(dynamic programming)，如果按照問(wèn)題類(lèi)型來(lái)劃分，將分為線(xiàn)性DP、區(qū)間DP，數(shù)位DP等等，每當(dāng)說(shuō)到動(dòng)態(tài)規(guī)劃就會(huì)想最優(yōu)子結(jié)構(gòu)，重疊子問(wèn)題等等，這些詞匯苦澀難懂，不要慌，再難的問(wèn)題也是建立在基礎(chǔ)問(wèn)題上，逐步拆分，這也是動(dòng)態(tài)規(guī)劃的思想，相信通過(guò)下面動(dòng)態(tài)規(guī)劃四步走的方式，加上習(xí)題的練習(xí)，一定會(huì)讓你對(duì)動(dòng)態(tài)規(guī)劃有個(gè)新的理解。

四個(gè)步驟分為：狀態(tài)定義，狀態(tài)轉(zhuǎn)移方程，正確性的證明和實(shí)現(xiàn)

狀態(tài)定義

其實(shí)上面說(shuō)遞推的時(shí)候就已經(jīng)有所涉及狀態(tài)定義，通常在推導(dǎo)的過(guò)程中，如果感覺(jué)推不下去了，很有可能就是我們的狀態(tài)定義出現(xiàn)了問(wèn)題。

第一個(gè)狀態(tài)：dp[i][j]代表從起始點(diǎn)到(I,j)路徑的最大值

第二個(gè)狀態(tài)：dp[i][j]代表從底邊的某個(gè)點(diǎn)出發(fā)，到達(dá)(i,j)路徑的最大值

狀態(tài)轉(zhuǎn)移方程

上面的兩種狀態(tài)定義對(duì)應(yīng)這里兩個(gè)轉(zhuǎn)移方向。

狀態(tài)轉(zhuǎn)移過(guò)程

如上圖所示，我們想要求得dp[i][j]，需要知道dp|[i-1]|[j-1]和dp[i-1][j]的值。因?yàn)橹挥?i - 1, j - 1) 和 (i - 1, j) 這兩個(gè)點(diǎn)，才能能走到 (i, j)此時(shí)的狀態(tài)轉(zhuǎn)移方程為

第一種狀態(tài)轉(zhuǎn)移方程dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j]

第二冊(cè)中狀態(tài)轉(zhuǎn)移方程dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]

從這里可以知道我們的狀態(tài)定義不一樣，我們的轉(zhuǎn)移方程就很不一樣吧

正確性證明

數(shù)學(xué)歸納法通常采用三步走的方式，常用的正確性證明方法為數(shù)學(xué)歸納法。

第一步，第一個(gè)階段所有dp值可以輕松獲得，也就是初始化dp[1][1]，等于val[1][1]

第二步，假設(shè)如果第i-1階段的所有狀態(tài)值都正確得到，那么根據(jù)狀態(tài)方程dp[i][j]=max(dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j] 來(lái)說(shuō)，此時(shí)就可以計(jì)算得到第i階段中的素有狀態(tài)值

第三步：得出結(jié)論，所有的狀態(tài)值計(jì)算正確

我們繼續(xù)分析動(dòng)態(tài)規(guī)劃問(wèn)題中的0/1背包問(wèn)題，通常分為三類(lèi)，0/1背包問(wèn)題，完全背包問(wèn)題和多重背包問(wèn)題。

0/1背包問(wèn)題是另外兩種背包問(wèn)題的基礎(chǔ)，簡(jiǎn)單描述一下，假設(shè)有個(gè)背包，載重上限為W，此時(shí)有n個(gè)物品，第i個(gè)物品的重量是wi，價(jià)值為vi，那么在不超過(guò)背包重量上限的前提下，能獲得的最大物品價(jià)值總和？同樣我們采用四步走的方式

狀態(tài)定義

首先分析背包問(wèn)題中的自變量和因變量，其中因變量比較好確定，就是所求最大價(jià)值總和，自變量呢，在此自變量為物品種類(lèi)和背包承重上限，因?yàn)檫@兩者會(huì)影響價(jià)值總和的最大值，所以我們?cè)O(shè)置一個(gè)二維狀態(tài)。dp[i][j]代表使用前i個(gè)物品，背包最大載重為j的情況下最大價(jià)值總和。

狀態(tài)方程

說(shuō)白了就是找映射函數(shù)，dp[i][j]的表達(dá)式。我們將dp[i][j]分為兩大類(lèi)，第一類(lèi)是不選擇第i個(gè)物品最大價(jià)值和，第二類(lèi)為選擇了第i個(gè)物品的最大價(jià)值和。然后在兩者中選擇最大值就是價(jià)值更大的方案。

如果選擇第i個(gè)物品，此時(shí)的最大價(jià)值為dp[i-1][j-wi]+vi，既然選擇了第i個(gè)商品，那么就需要留出一個(gè)位置，那么此時(shí)對(duì)于剩余的i-1個(gè)商品的載重空間就只剩下j-wi了，此時(shí)i-1個(gè)物品選擇的最大價(jià)值和為dp[i-1][j-wi]，然后加上vi就是當(dāng)前獲得最大價(jià)值和。所以轉(zhuǎn)移方程為

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

正確性證明

首先dp[0][j]=0，意味著沒(méi)有物品的時(shí)候，無(wú)論背包限重多少，能夠得到的最大價(jià)值和都是0，所以k0爭(zhēng)取

其次，假設(shè)我們已經(jīng)獲取i-1個(gè)物品的價(jià)值最大值，所有dp[i-1]的值，那么根據(jù)狀態(tài)方程，我們能知道所有dp[i]的值

最后兩步聯(lián)合，整個(gè)求解對(duì)于任意dp[i][j]成立

實(shí)現(xiàn)

#defineMAX_V10000 #defineMAX_N100 intv[MAX_N+5],w[MAX_N+5]; intdp[MAX_N+5][MAX_V+5]; intget_dp(intn,intW){ //初始化dp[0]階段 for(inti=0;i<=?W;?i++)?dp[0][i]?=?0; ????//?假設(shè)?dp[i?-?1]?成立，計(jì)算得到?dp[i] ????//?狀態(tài)轉(zhuǎn)移過(guò)程，i?代表物品，j?代表背包限重 ????for?(int?i?=?1;?i?<=?n;?i++)?{ ???????????for?(int?j?=?0;?j?<=?W;?j++)?{ ????????//?不選擇第?i?種物品時(shí)的最大值 ????????dp[i][j]?=?dp[i?-?1][j]; ????????//?與選擇第?i?種物品的最大值作比較，并更新 ????????if?(j?>=w[i]&&dp[i][j]

8、貪心

其實(shí)我們大學(xué)學(xué)習(xí)的好幾種應(yīng)用都是采用了貪心的算法啊，比如Huffman Coding，Prim最小生成樹(shù)等

先來(lái)看一道之前美團(tuán)的一道筆試題--跳一跳

有n個(gè)盒子排成一行，每個(gè)盒子上面有一個(gè)數(shù)字a[i]，表示最多能向右跳a[i]個(gè)盒子；小林站在左邊第一個(gè)盒子，請(qǐng)問(wèn)能否到達(dá)最右邊的盒子？比如說(shuō)：[1, 2, 3, 0, 4] 可以到達(dá)第5個(gè)盒子；[3, 2, 1, 0, 4] 無(wú)法到達(dá)第5個(gè)盒子；

思路：自然而然的想法，盡可能的往右邊跳，看最后能夠到達(dá)，從第一個(gè)盒子開(kāi)始從右遍歷，對(duì)于每個(gè)經(jīng)過(guò)的盒子，不斷地更新maxRight值。那么貪心算法的思考過(guò)程通常是怎么樣的？

類(lèi)似于動(dòng)態(tài)規(guī)劃，大事化小，小事化了。所謂大事化小，將大的問(wèn)題，找到和子問(wèn)題的重復(fù)部分，將復(fù)雜問(wèn)題拆分為小的問(wèn)題。小事化了，通過(guò)對(duì)小事的打磨找到較為核心的策略。上例子

分糖果問(wèn)題

我們有 m 個(gè)糖果和 n 個(gè)孩子。我們現(xiàn)在要把糖果分給這些孩子吃，但是糖果少，孩子多（m 我的問(wèn)題是，如何分配糖果，能盡可能滿(mǎn)足最多數(shù)量的孩子？

對(duì)于一個(gè)孩子來(lái)說(shuō)，如果小的糖果可以滿(mǎn)足，那么就沒(méi)必要用更大的糖果

對(duì)糖果的大小需求的孩子更容易被滿(mǎn)足，所以我們可以從需求小得孩子開(kāi)始分配糖果

因?yàn)闈M(mǎn)足一個(gè)需求大的孩子跟滿(mǎn)足一個(gè)需求小的孩子，對(duì)我們期望值的貢獻(xiàn)是一樣的

我們每次從剩下的孩子中，找出對(duì)糖果大小需求最小的，然后發(fā)給他剩下的糖果中能滿(mǎn)足他的最小的糖果，這樣得到的分配方案，也就是滿(mǎn)足的孩子個(gè)數(shù)最多的方案

#include #include #include usingnamespacestd; /* 解題思路： 遍歷兩邊，首先每個(gè)人得一塊糖，第一遍從左到右，若當(dāng)前點(diǎn)比前一個(gè)點(diǎn)高就比前者多一塊。 這樣保證了在一個(gè)方向上滿(mǎn)足了要求。第二遍從右往左，若左右兩點(diǎn)，左側(cè)高于右側(cè)，但 左側(cè)的糖果數(shù)不多于右側(cè)，則左側(cè)糖果數(shù)等于右側(cè)糖果數(shù)+1，這就保證了另一個(gè)方向上滿(mǎn)足要求。 最后將各個(gè)位置的糖果數(shù)累加起來(lái)就可以了。 */ intcandyCount(vector&rating){ intres=0; //孩子總數(shù) intn=rating.size(); //糖果集合 vectorcandy(n,1); //從左往右遍歷 for(inti=0;irating[i])candy[i+1]=candy[i]+1; } //從右往左 for(inti=n-1;i>0;i--){ if(rating[i-1]>rating[i]&&candy[i-1]<=?candy[i]) ????????????candy[i?-?1]?=?candy[i]?+?1; ????} ????//累加結(jié)果 ????for?(auto?a?:?candy)?{ ????????res?+=?a; ????} ????return?res; } //測(cè)試函數(shù) int?main()?{ ????vectorrating{1,3,2,1,4,5,2}; cout<

責(zé)任編輯：lq