算法和數(shù)據(jù)結(jié)構(gòu)體系學(xué)習(xí)班
00 算法和數(shù)據(jù)結(jié)構(gòu)學(xué)前必看
內(nèi)容：
算法和數(shù)據(jù)結(jié)構(gòu)課程體系介紹
算法和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)路線
算法和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)方式推薦
算法和數(shù)據(jù)結(jié)構(gòu)面試軟技巧
同學(xué)們的各種答疑問(wèn)題
01 時(shí)間復(fù)雜度碱屁、空間復(fù)雜度掂咒、對(duì)數(shù)器和二分法
內(nèi)容：
評(píng)估算法優(yōu)劣的核心指標(biāo)
時(shí)間復(fù)雜度迹蛤、空間復(fù)雜度、估算方式仑扑、意義
常數(shù)時(shí)間的操作
選擇排序、冒泡排序置鼻、插入排序
最優(yōu)解
對(duì)數(shù)器
二分法
題目：
選擇排序及其對(duì)數(shù)器驗(yàn)證
冒泡排序及其對(duì)數(shù)器驗(yàn)證
插入排序及其對(duì)數(shù)器驗(yàn)證
有序數(shù)組中找到num
有序數(shù)組中找到>=num最左的位置
有序數(shù)組中找到<=num最右的位置
局部最小值問(wèn)題
定義何為局部最小值：
arr[0] < arr[1]镇饮，0位置是局部最小箕母；
arr[N-1] < arr[N-2]储藐，N-1位置是局部最芯慵谩；
arr[i-1] > arr[i] < arr[i+1]钙勃，i位置是局部最兄肼怠；
給定一個(gè)數(shù)組arr辖源，已知任何兩個(gè)相鄰的數(shù)都不相等蔚携，找到隨便一個(gè)局部最小位置返回
02 異或運(yùn)算、進(jìn)一步認(rèn)識(shí)對(duì)數(shù)器的重要性
內(nèi)容：
異或運(yùn)算的性質(zhì)
異或運(yùn)算的題目
題目：
不用額外變量交換兩個(gè)數(shù)的值
不用額外變量交換數(shù)組中兩個(gè)數(shù)的值
一個(gè)數(shù)組中有一種數(shù)出現(xiàn)了奇數(shù)次克饶，其他數(shù)都出現(xiàn)了偶數(shù)次酝蜒，怎么找到并打印這種數(shù)
怎么把一個(gè)int類型的數(shù)，提取出二進(jìn)制中最右側(cè)的1來(lái)
一個(gè)數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次彤路，其他數(shù)都出現(xiàn)了偶數(shù)次秕硝，怎么找到并打印這兩種數(shù)
一個(gè)數(shù)組中有一種數(shù)出現(xiàn)K次，其他數(shù)都出現(xiàn)了M次洲尊，
已知M > 1远豺，K < M，找到出現(xiàn)了K次的數(shù)
要求額外空間復(fù)雜度O(1)坞嘀，時(shí)間復(fù)雜度O(N)
03 單雙鏈表躯护、棧和隊(duì)列、遞歸和Master公式丽涩、哈希表和有序表的使用和性能
內(nèi)容：
單鏈表棺滞、雙鏈表
棧、隊(duì)列
遞歸的物理實(shí)質(zhì)
評(píng)估遞歸復(fù)雜度的Master公式
哈希表的使用和性能
有序表的使用和性能
題目：
反轉(zhuǎn)單鏈表矢渊、反轉(zhuǎn)雙鏈表
在鏈表中刪除指定值的所有節(jié)點(diǎn)
用雙鏈表實(shí)現(xiàn)棧和隊(duì)列
用環(huán)形數(shù)組實(shí)現(xiàn)棧和隊(duì)列
實(shí)現(xiàn)有g(shù)etMin功能的棧
兩個(gè)棧實(shí)現(xiàn)隊(duì)列
兩個(gè)隊(duì)列實(shí)現(xiàn)棧
用遞歸行為得到數(shù)組中的最大值继准，并用master公式來(lái)估計(jì)時(shí)間復(fù)雜度
哈希表和有序表使用的code展示
04 歸并排序及其常見(jiàn)面試題
內(nèi)容：
歸并排序
題目：
歸并排序的遞歸和非遞歸實(shí)現(xiàn)
在一個(gè)數(shù)組中，一個(gè)數(shù)左邊比它小的數(shù)的總和矮男，叫該數(shù)的小和
所有數(shù)的小和累加起來(lái)移必，叫數(shù)組小和
例子： [1,3,4,2,5]
1左邊比1小的數(shù)：沒(méi)有
3左邊比3小的數(shù)：1
4左邊比4小的數(shù)：1、3
2左邊比2小的數(shù)：1
5左邊比5小的數(shù)：1毡鉴、3崔泵、4、 2
所以數(shù)組的小和為1+1+3+1+1+3+4+2=16
給定一個(gè)數(shù)組arr猪瞬，求數(shù)組小和
在一個(gè)數(shù)組中憎瘸，任何一個(gè)前面的數(shù)a，和任何一個(gè)后面的數(shù)b陈瘦，如果(a,b)是降序的幌甘，就稱為降序?qū)?br> 給定一個(gè)數(shù)組arr，求數(shù)組的降序?qū)倲?shù)量
在一個(gè)數(shù)組中，對(duì)于任何一個(gè)數(shù)num含潘，求有多少個(gè)(后面的數(shù)*2)依然<num饲做，返回總個(gè)數(shù)
比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0遏弱，2
0的后面沒(méi)有
2的后面沒(méi)有
所以總共有5個(gè)
05 歸并排序面試題(續(xù))盆均、快速排序
內(nèi)容：
再來(lái)一個(gè)歸并排序面試題
荷蘭國(guó)旗問(wèn)題
快速排序1.0
快速排序2.0
快速排序3.0
題目：
給定一個(gè)數(shù)組arr，兩個(gè)整數(shù)lower和upper漱逸，
返回arr中有多少個(gè)子數(shù)組的累加和在[lower,upper]范圍上
Leetcode題目：https://leetcode.com/problems/count-of-range-sum/
荷蘭國(guó)旗問(wèn)題的實(shí)現(xiàn)
快速排序從1.0到3.0的實(shí)現(xiàn)
快速排序的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)
code附加泪姨，雙向鏈表進(jìn)行快速排序的code實(shí)現(xiàn)
06 比較器、堆結(jié)構(gòu)饰抒、堆排序
內(nèi)容：
比較器
堆結(jié)構(gòu)
堆排序
建立大根堆的兩種方式肮砾，從上到下、從下到上袋坑，及其復(fù)雜度分析
題目：
比較器使用的code展示
堆結(jié)構(gòu)的實(shí)現(xiàn)
堆排序的實(shí)現(xiàn)
已知一個(gè)幾乎有序的數(shù)組仗处。幾乎有序是指，如果把數(shù)組排好順序的話枣宫，每個(gè)元素移動(dòng)的距離一定不超過(guò)k
k相對(duì)于數(shù)組長(zhǎng)度來(lái)說(shuō)是比較小的婆誓。請(qǐng)選擇一個(gè)合適的排序策略，對(duì)這個(gè)數(shù)組進(jìn)行排序也颤。
07 和堆有關(guān)的面試題洋幻、加強(qiáng)堆結(jié)構(gòu)
內(nèi)容：
線段最大重合問(wèn)題
加強(qiáng)堆的實(shí)現(xiàn)
題目：
給定很多線段，每個(gè)線段都有兩個(gè)數(shù)[start, end]翅娶，
表示線段開(kāi)始位置和結(jié)束位置文留，左右都是閉區(qū)間
規(guī)定：
1）線段的開(kāi)始和結(jié)束位置一定都是整數(shù)值
2）線段重合區(qū)域的長(zhǎng)度必須>=1
返回線段最多重合區(qū)域中，包含了幾條線段
加強(qiáng)堆的實(shí)現(xiàn)竭沫、注意點(diǎn)解析
做一個(gè)加強(qiáng)堆的題目燥翅，給定一個(gè)整型數(shù)組，int[] arr蜕提；和一個(gè)布爾類型數(shù)組权旷，boolean[] op
兩個(gè)數(shù)組一定等長(zhǎng)，假設(shè)長(zhǎng)度為N贯溅，arr[i]表示客戶編號(hào)，op[i]表示客戶操作
arr= [3,3,1,2,1,2,5…
op = [T,T,T,T,F,T,F…
依次表示：
3用戶購(gòu)買了一件商品
3用戶購(gòu)買了一件商品
1用戶購(gòu)買了一件商品
2用戶購(gòu)買了一件商品
1用戶退貨了一件商品
2用戶購(gòu)買了一件商品
5用戶退貨了一件商品…
一對(duì)arr[i]和op[i]就代表一個(gè)事件：
用戶號(hào)為arr[i]躲查，op[i] == T就代表這個(gè)用戶購(gòu)買了一件商品
op[i] == F就代表這個(gè)用戶退貨了一件商品
現(xiàn)在你作為電商平臺(tái)負(fù)責(zé)人它浅，你想在每一個(gè)事件到來(lái)的時(shí)候，
都給購(gòu)買次數(shù)最多的前K名用戶頒獎(jiǎng)镣煮。
所以每個(gè)事件發(fā)生后姐霍，你都需要一個(gè)得獎(jiǎng)名單（得獎(jiǎng)區(qū)）。
得獎(jiǎng)系統(tǒng)的規(guī)則：
1，如果某個(gè)用戶購(gòu)買商品數(shù)為0镊折，但是又發(fā)生了退貨事件胯府，
則認(rèn)為該事件無(wú)效，得獎(jiǎng)名單和上一個(gè)事件發(fā)生后一致恨胚，例子中的5用戶
2骂因，某用戶發(fā)生購(gòu)買商品事件，購(gòu)買商品數(shù)+1赃泡，發(fā)生退貨事件寒波，購(gòu)買商品數(shù)-1
3，每次都是最多K個(gè)用戶得獎(jiǎng)升熊，K也為傳入的參數(shù)
如果根據(jù)全部規(guī)則俄烁，得獎(jiǎng)人數(shù)確實(shí)不夠K個(gè)，那就以不夠的情況輸出結(jié)果
4级野，得獎(jiǎng)系統(tǒng)分為得獎(jiǎng)區(qū)和候選區(qū)页屠，任何用戶只要購(gòu)買數(shù)>0，
一定在這兩個(gè)區(qū)域中的一個(gè)
5蓖柔，購(gòu)買數(shù)最大的前K名用戶進(jìn)入得獎(jiǎng)區(qū)辰企，
在最初時(shí)如果得獎(jiǎng)區(qū)沒(méi)有到達(dá)K個(gè)用戶，那么新來(lái)的用戶直接進(jìn)入得獎(jiǎng)區(qū)
6渊抽，如果購(gòu)買數(shù)不足以進(jìn)入得獎(jiǎng)區(qū)的用戶蟆豫，進(jìn)入候選區(qū)
7，如果候選區(qū)購(gòu)買數(shù)最多的用戶懒闷，已經(jīng)足以進(jìn)入得獎(jiǎng)區(qū)十减，
該用戶就會(huì)替換得獎(jiǎng)區(qū)中購(gòu)買數(shù)最少的用戶（大于才能替換），
如果得獎(jiǎng)區(qū)中購(gòu)買數(shù)最少的用戶有多個(gè)愤估，就替換最早進(jìn)入得獎(jiǎng)區(qū)的用戶
如果候選區(qū)中購(gòu)買數(shù)最多的用戶有多個(gè)帮辟，機(jī)會(huì)會(huì)給最早進(jìn)入候選區(qū)的用戶
8，候選區(qū)和得獎(jiǎng)區(qū)是兩套時(shí)間玩焰，
因用戶只會(huì)在其中一個(gè)區(qū)域由驹，所以只會(huì)有一個(gè)區(qū)域的時(shí)間，另一個(gè)沒(méi)有
從得獎(jiǎng)區(qū)出來(lái)進(jìn)入候選區(qū)的用戶昔园，得獎(jiǎng)區(qū)時(shí)間刪除蔓榄，
進(jìn)入候選區(qū)的時(shí)間就是當(dāng)前事件的時(shí)間（可以理解為arr[i]和op[i]中的i）
從候選區(qū)出來(lái)進(jìn)入得獎(jiǎng)區(qū)的用戶，候選區(qū)時(shí)間刪除默刚，
進(jìn)入得獎(jiǎng)區(qū)的時(shí)間就是當(dāng)前事件的時(shí)間（可以理解為arr[i]和op[i]中的i）
9甥郑，如果某用戶購(gòu)買數(shù)==0，不管在哪個(gè)區(qū)域都離開(kāi)荤西，區(qū)域時(shí)間刪除澜搅，
離開(kāi)是指徹底離開(kāi)伍俘，哪個(gè)區(qū)域也不會(huì)找到該用戶
如果下次該用戶又發(fā)生購(gòu)買行為，產(chǎn)生>0的購(gòu)買數(shù)勉躺，
會(huì)再次根據(jù)之前規(guī)則回到某個(gè)區(qū)域中癌瘾，進(jìn)入?yún)^(qū)域的時(shí)間重記
請(qǐng)遍歷arr數(shù)組和op數(shù)組，遍歷每一步輸出一個(gè)得獎(jiǎng)名單
public List<List<Integer>> topK (int[] arr, boolean[] op, int k)
08 前綴樹(shù)饵溅、不基于比較的排序（計(jì)數(shù)排序妨退、基數(shù)排序）、排序算法的穩(wěn)定性
內(nèi)容：
前綴樹(shù)
計(jì)數(shù)排序
基數(shù)排序
排序算法的穩(wěn)定性
題目：
前綴樹(shù)實(shí)現(xiàn)
計(jì)數(shù)排序
基數(shù)排序
09 排序算法大總結(jié)概说、鏈表及其相關(guān)面試題
內(nèi)容：
排序算法總結(jié)
排序算法常見(jiàn)的坑
工程上對(duì)排序的常見(jiàn)改進(jìn)
鏈表面試題的常見(jiàn)技巧
題目：
輸入鏈表頭節(jié)點(diǎn)碧注，奇數(shù)長(zhǎng)度返回中點(diǎn)，偶數(shù)長(zhǎng)度返回上中點(diǎn)
輸入鏈表頭節(jié)點(diǎn)糖赔，奇數(shù)長(zhǎng)度返回中點(diǎn)萍丐，偶數(shù)長(zhǎng)度返回下中點(diǎn)
輸入鏈表頭節(jié)點(diǎn)，奇數(shù)長(zhǎng)度返回中點(diǎn)前一個(gè)放典，偶數(shù)長(zhǎng)度返回上中點(diǎn)前一個(gè)
輸入鏈表頭節(jié)點(diǎn)逝变，奇數(shù)長(zhǎng)度返回中點(diǎn)前一個(gè)，偶數(shù)長(zhǎng)度返回下中點(diǎn)前一個(gè)
給定一個(gè)單鏈表的頭節(jié)點(diǎn)head奋构，請(qǐng)判斷該鏈表是否為回文結(jié)構(gòu)
給定一個(gè)單鏈表的頭節(jié)點(diǎn)head壳影，給定一個(gè)整數(shù)n，將鏈表按n劃分成左邊<n弥臼、中間==n宴咧、右邊>n
一種特殊的單鏈表節(jié)點(diǎn)類描述如下
class Node {
int value;
Node next;
Node rand;
Node(int val) { value = val; }
}
rand指針是單鏈表節(jié)點(diǎn)結(jié)構(gòu)中新增的指針，rand可能指向鏈表中的任意一個(gè)節(jié)點(diǎn)径缅，也可能指向null
給定一個(gè)由Node節(jié)點(diǎn)類型組成的無(wú)環(huán)單鏈表的頭節(jié)點(diǎn)head掺栅，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)完成這個(gè)鏈表的復(fù)制
返回復(fù)制的新鏈表的頭節(jié)點(diǎn)，要求時(shí)間復(fù)雜度O(N)纳猪，額外空間復(fù)雜度O(1)
10 鏈表相關(guān)面試題（續(xù)）氧卧、二叉樹(shù)的常見(jiàn)遍歷
內(nèi)容：
單鏈表的相交節(jié)點(diǎn)系列問(wèn)題
一種看似高效其實(shí)搞笑的節(jié)點(diǎn)刪除方式
二叉樹(shù)的中序、先序氏堤、后序遍歷
題目：
給定兩個(gè)可能有環(huán)也可能無(wú)環(huán)的單鏈表沙绝，頭節(jié)點(diǎn)head1和head2
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，如果兩個(gè)鏈表相交鼠锈，請(qǐng)返回相交的第一個(gè)節(jié)點(diǎn)闪檬。如果不相交返回null
要求如果兩個(gè)鏈表長(zhǎng)度之和為N，時(shí)間復(fù)雜度請(qǐng)達(dá)到O(N)购笆，額外空間復(fù)雜度請(qǐng)達(dá)到O(1)
能不能不給單鏈表的頭節(jié)點(diǎn)谬以，只給想要?jiǎng)h除的節(jié)點(diǎn)，就能做到在鏈表上把這個(gè)點(diǎn)刪掉由桌？
二叉樹(shù)先序、中序、后序的遞歸遍歷和遞歸序
二叉樹(shù)先序行您、中序铭乾、后序的非遞歸遍歷
11 二叉樹(shù)常見(jiàn)面試題和二叉樹(shù)的遞歸套路（上）
內(nèi)容：
通過(guò)題目來(lái)熟悉二叉樹(shù)的解題技巧
題目：
二叉樹(shù)的按層遍歷
二叉樹(shù)的序列化和反序列化
N叉樹(shù)如何通過(guò)二叉樹(shù)來(lái)序列化、并完成反序列化
Leetcode題目：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/
打印二叉樹(shù)的函數(shù)設(shè)計(jì)
求二叉樹(shù)的最大寬度
求二叉樹(shù)某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)
二叉樹(shù)結(jié)構(gòu)如下定義：
Class Node {
V value;
Node left;
Node right;
Node parent;
}
給你二叉樹(shù)中的某個(gè)節(jié)點(diǎn)娃循，返回該節(jié)點(diǎn)的后繼節(jié)點(diǎn)
折紙問(wèn)題
請(qǐng)把一段紙條豎著放在桌子上炕檩，然后從紙條的下邊向上方對(duì)折1次，壓出折痕后展開(kāi)
此時(shí)折痕是凹下去的捌斧，即折痕突起的方向指向紙條的背面
如果從紙條的下邊向上方連續(xù)對(duì)折2次笛质，壓出折痕后展開(kāi)
此時(shí)有三條折痕，從上到下依次是下折痕捞蚂、下折痕和上折痕妇押。
給定一個(gè)輸入?yún)?shù)N，代表紙條都從下邊向上方連續(xù)對(duì)折N次
請(qǐng)從上到下打印所有折痕的方向姓迅。
N=1時(shí)敲霍，打印: down
N=2時(shí)，打印: down down up
12 二叉樹(shù)常見(jiàn)面試題和二叉樹(shù)的遞歸套路（中）
內(nèi)容：
通過(guò)題目來(lái)熟悉二叉樹(shù)的解題技巧
介紹二叉樹(shù)的遞歸套路
1）假設(shè)以X節(jié)點(diǎn)為頭丁存，假設(shè)可以向X左樹(shù)和X右樹(shù)要任何信息
2）在上一步的假設(shè)下肩杈，討論以X為頭節(jié)點(diǎn)的樹(shù)，得到答案的可能性（最重要）
3）列出所有可能性后解寝，確定到底需要向左樹(shù)和右樹(shù)要什么樣的信息
4）把左樹(shù)信息和右樹(shù)信息求全集扩然，就是任何一棵子樹(shù)都需要返回的信息S
5）遞歸函數(shù)都返回S，每一棵子樹(shù)都這么要求
6）寫代碼聋伦，在代碼中考慮如何把左樹(shù)的信息和右樹(shù)信息整合出整棵樹(shù)的信息
題目：
判斷二叉樹(shù)是不是搜索二叉樹(shù)
判斷二叉樹(shù)是不是平衡二叉樹(shù)
判斷二叉樹(shù)是不是滿二叉樹(shù)
給定一棵二叉樹(shù)的頭節(jié)點(diǎn)head夫偶，返回這顆二叉樹(shù)中最大的二叉搜索子樹(shù)的大小
給定一棵二叉樹(shù)的頭節(jié)點(diǎn)head宠默，任何兩個(gè)節(jié)點(diǎn)之間都存在距離汇恤，返回整棵二叉樹(shù)的最大距離
13 二叉樹(shù)常見(jiàn)面試題和二叉樹(shù)的遞歸套路（下）、貪心算法
內(nèi)容：
二叉樹(shù)遞歸套路繼續(xù)實(shí)踐
一道貪心算法從頭到尾的完整做法
解決貪心題目的重要技巧室叉，即對(duì)數(shù)器來(lái)驗(yàn)證腦洞
再次強(qiáng)調(diào)對(duì)數(shù)器的重要性
題目：
判斷二叉樹(shù)是不是完全二叉樹(shù)（一般方法解決抑片、遞歸套路解決）
給定一棵二叉樹(shù)的頭節(jié)點(diǎn)head卵佛，返回這顆二叉樹(shù)中最大的二叉搜索子樹(shù)的頭節(jié)點(diǎn)
給定一棵二叉樹(shù)的頭節(jié)點(diǎn)head，和另外兩個(gè)節(jié)點(diǎn)a和b敞斋，返回a和b的最低公共祖先
派對(duì)的最大快樂(lè)值
員工信息的定義如下:
class Employee {
public int happy; // 這名員工可以帶來(lái)的快樂(lè)值
List<Employee> subordinates; // 這名員工有哪些直接下級(jí)
}
公司的每個(gè)員工都符合 Employee 類的描述截汪。整個(gè)公司的人員結(jié)構(gòu)可以看作是一棵標(biāo)準(zhǔn)的、 沒(méi)有環(huán)的多叉樹(shù)
樹(shù)的頭節(jié)點(diǎn)是公司唯一的老板植捎，除老板之外的每個(gè)員工都有唯一的直接上級(jí)
葉節(jié)點(diǎn)是沒(méi)有任何下屬的基層員工(subordinates列表為空)衙解，除基層員工外每個(gè)員工都有一個(gè)或多個(gè)直接下級(jí)
這個(gè)公司現(xiàn)在要辦party，你可以決定哪些員工來(lái)焰枢，哪些員工不來(lái)蚓峦，規(guī)則：
1.如果某個(gè)員工來(lái)了舌剂，那么這個(gè)員工的所有直接下級(jí)都不能來(lái)
2.派對(duì)的整體快樂(lè)值是所有到場(chǎng)員工快樂(lè)值的累加
3.你的目標(biāo)是讓派對(duì)的整體快樂(lè)值盡量大
給定一棵多叉樹(shù)的頭節(jié)點(diǎn)boss，請(qǐng)返回派對(duì)的最大快樂(lè)值暑椰。
給定一個(gè)由字符串組成的數(shù)組strs霍转，必須把所有的字符串拼接起來(lái)，返回所有可能的拼接結(jié)果中字典序最小的結(jié)果
14 貪心算法（續(xù)）一汽、并查集
內(nèi)容：
貪心算法繼續(xù)實(shí)戰(zhàn)
并查集詳解
題目：
給定一個(gè)字符串str避消，只由'X'和'.'兩種字符構(gòu)成
'X'表示墻，不能放燈召夹，也不需要點(diǎn)亮岩喷；'.'表示居民點(diǎn)，可以放燈监憎，需要點(diǎn)亮
如果燈放在i位置纱意，可以讓i-1，i和i+1三個(gè)位置被點(diǎn)亮
返回如果點(diǎn)亮str中所有需要點(diǎn)亮的位置枫虏，至少需要幾盞燈
一塊金條切成兩半妇穴，是需要花費(fèi)和長(zhǎng)度數(shù)值一樣的銅板
比如長(zhǎng)度為20的金條，不管怎么切都要花費(fèi)20個(gè)銅板隶债，一群人想整分整塊金條腾它，怎么分最省銅板?
例如，給定數(shù)組{10,20,30}死讹，代表一共三個(gè)人瞒滴，整塊金條長(zhǎng)度為60，金條要分成10赞警，20妓忍，30三個(gè)部分。
如果先把長(zhǎng)度60的金條分成10和50愧旦，花費(fèi)60世剖；再把長(zhǎng)度50的金條分成20和30，花費(fèi)50笤虫；一共花費(fèi)110銅板
但如果先把長(zhǎng)度60的金條分成30和30旁瘫，花費(fèi)60；再把長(zhǎng)度30金條分成10和20琼蚯，花費(fèi)30酬凳；一共花費(fèi)90銅板
?輸入一個(gè)數(shù)組，返回分割的最小代價(jià)
一些項(xiàng)目要占用一個(gè)會(huì)議室宣講遭庶，會(huì)議室不能同時(shí)容納兩個(gè)項(xiàng)目的宣講宁仔，給你每一個(gè)項(xiàng)目開(kāi)始的時(shí)間和結(jié)束的時(shí)間
你來(lái)安排宣講的日程，要求會(huì)議室進(jìn)行的宣講的場(chǎng)次最多峦睡，返回最多的宣講場(chǎng)次
輸入正數(shù)數(shù)組costs翎苫、正數(shù)數(shù)組profits权埠、正數(shù)K和正數(shù)M
?costs[i]表示i號(hào)項(xiàng)目的花費(fèi)
profits[i]表示i號(hào)項(xiàng)目在扣除花費(fèi)之后還能掙到的錢(利潤(rùn))
K表示你只能串行的最多做k個(gè)項(xiàng)目
M表示你初始的資金
說(shuō)明：每做完一個(gè)項(xiàng)目，馬上獲得的收益拉队，可以支持你去做下一個(gè)項(xiàng)目弊知，不能并行的做項(xiàng)目。
輸出：最后獲得的最大錢數(shù)
并查集的實(shí)現(xiàn)
15 并查集相關(guān)的常見(jiàn)面試題
內(nèi)容：
通過(guò)解答實(shí)際出現(xiàn)的面試題來(lái)體會(huì)并查集的優(yōu)勢(shì)粱快、熟悉并查集的使用
題目：
一群朋友中，有幾個(gè)不相交的朋友圈
Leetcode題目：https://leetcode.com/problems/friend-circles/
島問(wèn)題（遞歸解法 + 并查集解法 + 并行解法）
給定一個(gè)二維數(shù)組matrix叔扼，里面的值不是1就是0事哭，上、下瓜富、左鳍咱、右相鄰的1認(rèn)為是一片島，返回matrix中島的數(shù)量
16 圖及其與圖相關(guān)的算法
內(nèi)容：
圖的表達(dá)方式
圖的常見(jiàn)描述
圖的寬度優(yōu)先遍歷
圖的深度優(yōu)先遍歷
圖的拓?fù)渑判?/p>
最小生成樹(shù)算法Kruskal
最小生成樹(shù)算法Prim
單元最短路徑算法Dijkstra
題目：
圖的數(shù)據(jù)結(jié)構(gòu)抽象
實(shí)現(xiàn)圖的寬度優(yōu)先遍歷
實(shí)現(xiàn)圖的深度優(yōu)先遍歷
三種方式實(shí)現(xiàn)圖的拓?fù)渑判?/p>
用并查集實(shí)現(xiàn)Kruskal算法
用堆實(shí)現(xiàn)Prim算法
實(shí)現(xiàn)Dijkstra算法与柑，用加強(qiáng)堆做更好的實(shí)現(xiàn)（16節(jié)+17節(jié)一開(kāi)始）
17 用加強(qiáng)堆更好的實(shí)現(xiàn)Dijkstra算法谤辜、常見(jiàn)的遞歸
內(nèi)容：
加強(qiáng)堆實(shí)現(xiàn)Dijkstra算法
遞歸的設(shè)計(jì)
常見(jiàn)的遞歸
題目：
打印n層漢諾塔從最左邊移動(dòng)到最右邊的全部過(guò)程（遞歸+非遞歸實(shí)現(xiàn)）
打印一個(gè)字符串的全部子序列
打印一個(gè)字符串的全部子序列，要求不要出現(xiàn)重復(fù)字面值的子序列
打印一個(gè)字符串的全部排列
打印一個(gè)字符串的全部排列价捧，要求不要出現(xiàn)重復(fù)的排列
給定一個(gè)棧丑念，請(qǐng)逆序這個(gè)棧，不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)结蟋，只能使用遞歸函數(shù)
18 暴力遞歸到動(dòng)態(tài)規(guī)劃（一）
內(nèi)容：
講述暴力遞歸和動(dòng)態(tài)規(guī)劃的關(guān)系
記憶化搜索
動(dòng)態(tài)規(guī)劃都可以由暴力遞歸改進(jìn)過(guò)來(lái)脯倚，解決動(dòng)態(tài)規(guī)劃的套路
常見(jiàn)的嘗試模型
設(shè)計(jì)嘗試過(guò)程的原則
本節(jié)是暴力遞歸到動(dòng)態(tài)規(guī)劃的總綱（很重要）
后續(xù)的課都是在講述這一系列的套路
題目：
假設(shè)有排成一行的N個(gè)位置記為1~N，N一定大于或等于2
開(kāi)始時(shí)機(jī)器人在其中的M位置上(M一定是1~N中的一個(gè))
如果機(jī)器人來(lái)到1位置嵌屎，那么下一步只能往右來(lái)到2位置推正；
如果機(jī)器人來(lái)到N位置，那么下一步只能往左來(lái)到N-1位置宝惰；
如果機(jī)器人來(lái)到中間位置植榕，那么下一步可以往左走或者往右走；
規(guī)定機(jī)器人必須走K步尼夺，最終能來(lái)到P位置(P也是1~N中的一個(gè))的方法有多少種
給定四個(gè)參數(shù) N尊残、M、K汞斧、P夜郁，返回方法數(shù)
給定一個(gè)整型數(shù)組arr，代表數(shù)值不同的紙牌排成一條線
玩家A和玩家B依次拿走每張紙牌
規(guī)定玩家A先拿粘勒，玩家B后拿
但是每個(gè)玩家每次只能拿走最左或最右的紙牌
玩家A和玩家B都絕頂聰明
請(qǐng)返回最后獲勝者的分?jǐn)?shù)
19 暴力遞歸到動(dòng)態(tài)規(guī)劃（二）
內(nèi)容：
以18節(jié)為總綱
背包問(wèn)題
記憶化搜索的一個(gè)很重要的注意點(diǎn)
通過(guò)面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
題目：
背包問(wèn)題
給定兩個(gè)長(zhǎng)度都為N的數(shù)組weights和values竞端，weights[i]和values[i]分別代表 i號(hào)物品的重量和價(jià)值
給定一個(gè)正數(shù)bag，表示一個(gè)載重bag的袋子庙睡，裝的物品不能超過(guò)這個(gè)重量
返回能裝下的最大價(jià)值
規(guī)定1和A對(duì)應(yīng)事富、2和B對(duì)應(yīng)技俐、3和C對(duì)應(yīng)...26和Z對(duì)應(yīng)
那么一個(gè)數(shù)字字符串比如"111”就可以轉(zhuǎn)化為:
"AAA"、"KA"和"AK"
給定一個(gè)只有數(shù)字字符組成的字符串str统台，返回有多少種轉(zhuǎn)化結(jié)果
給定一個(gè)字符串str雕擂，給定一個(gè)字符串類型的數(shù)組arr，出現(xiàn)的字符都是小寫英文
arr每一個(gè)字符串贱勃，代表一張貼紙井赌，你可以把單個(gè)字符剪開(kāi)使用，目的是拼出str來(lái)
返回需要至少多少?gòu)堎N紙可以完成這個(gè)任務(wù)
例子：str= "babac"贵扰，arr = {"ba","c","abcd"}
ba + ba + c 3 abcd + abcd 2 abcd+ba 2
所以返回2
給定兩個(gè)字符串str1和str2仇穗，
返回這兩個(gè)字符串的最長(zhǎng)公共子序列長(zhǎng)度
比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最長(zhǎng)公共子序列是“123456”，所以返回長(zhǎng)度6
20 暴力遞歸到動(dòng)態(tài)規(guī)劃（三）
內(nèi)容：
以18節(jié)為總綱
通過(guò)面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
題目：
給定一個(gè)字符串str戚绕，返回這個(gè)字符串的最長(zhǎng)回文子序列長(zhǎng)度
比如 ： str = “a12b3c43def2ghi1kpm”
最長(zhǎng)回文子序列是“1234321”或者“123c321”纹坐，返回長(zhǎng)度7
請(qǐng)同學(xué)們自行搜索或者想象一個(gè)象棋的棋盤，
然后把整個(gè)棋盤放入第一象限舞丛，棋盤的最左下角是(0,0)位置
那么整個(gè)棋盤就是橫坐標(biāo)上9條線耘子、縱坐標(biāo)上10條線的區(qū)域
給你三個(gè) 參數(shù) x，y球切，k
返回“馬”從(0,0)位置出發(fā)谷誓，必須走k步
最后落在(x,y)上的方法數(shù)有多少種?
給定一個(gè)數(shù)組arr，arr[i]代表第i號(hào)咖啡機(jī)泡一杯咖啡的時(shí)間
給定一個(gè)正數(shù)N欧聘，表示N個(gè)人等著咖啡機(jī)泡咖啡片林，每臺(tái)咖啡機(jī)只能輪流泡咖啡
只有一臺(tái)咖啡機(jī)，一次只能洗一個(gè)杯子怀骤，時(shí)間耗費(fèi)a费封，洗完才能洗下一杯
每個(gè)咖啡杯也可以自己揮發(fā)干凈，時(shí)間耗費(fèi)b蒋伦，咖啡杯可以并行揮發(fā)
假設(shè)所有人拿到咖啡之后立刻喝干凈弓摘，
返回從開(kāi)始等到所有咖啡機(jī)變干凈的最短時(shí)間
三個(gè)參數(shù)：int[] arr、int N痕届，int a韧献、int b
21 暴力遞歸到動(dòng)態(tài)規(guī)劃（四）
內(nèi)容：
以18節(jié)為總綱
通過(guò)面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
題目：
給定一個(gè)二維數(shù)組matrix，一個(gè)人必須從左上角出發(fā)研叫，最后到達(dá)右下角
沿途只可以向下或者向右走锤窑，沿途的數(shù)字都累加就是距離累加和
返回最小距離累加和
arr是貨幣數(shù)組，其中的值都是正數(shù)嚷炉。再給定一個(gè)正數(shù)aim渊啰。
每個(gè)值都認(rèn)為是一張貨幣，
即便是值相同的貨幣也認(rèn)為每一張都是不同的，
返回組成aim的方法數(shù)
例如：arr = {1,1,1}绘证，aim = 2
第0個(gè)和第1個(gè)能組成2隧膏，第1個(gè)和第2個(gè)能組成2，第0個(gè)和第2個(gè)能組成2
一共就3種方法嚷那，所以返回3
arr是面值數(shù)組胞枕，其中的值都是正數(shù)且沒(méi)有重復(fù)。再給定一個(gè)正數(shù)aim魏宽。
每個(gè)值都認(rèn)為是一種面值腐泻，且認(rèn)為張數(shù)是無(wú)限的。
返回組成aim的方法數(shù)
例如：arr = {1,2}队询，aim = 4
方法如下：1+1+1+1贫悄、1+1+2、2+2
一共就3種方法娘摔，所以返回3
arr是貨幣數(shù)組，其中的值都是正數(shù)唤反。再給定一個(gè)正數(shù)aim凳寺。
每個(gè)值都認(rèn)為是一張貨幣，
認(rèn)為值相同的貨幣沒(méi)有任何不同彤侍，
返回組成aim的方法數(shù)
例如：arr = {1,2,1,1,2,1,2}肠缨，aim = 4
方法：1+1+1+1、1+1+2盏阶、2+2
一共就3種方法晒奕，所以返回3
給定5個(gè)參數(shù)，N名斟，M脑慧，row，col砰盐，k
表示在NM的區(qū)域上闷袒，醉漢Bob初始在(row,col)位置
Bob一共要邁出k步，且每步都會(huì)等概率向上下左右四個(gè)方向走一個(gè)單位
任何時(shí)候Bob只要離開(kāi)NM的區(qū)域岩梳，就直接死亡
返回k步之后囊骤，Bob還在N*M的區(qū)域的概率
22 暴力遞歸到動(dòng)態(tài)規(guī)劃（五）
內(nèi)容：
以18節(jié)為總綱
通過(guò)面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
斜率優(yōu)化技巧
題目：
給定3個(gè)參數(shù)，N冀值，M也物，K
怪獸有N滴血，等著英雄來(lái)砍自己
英雄每一次打擊列疗，都會(huì)讓怪獸流失[0~M]的血量
到底流失多少滑蚯？每一次在[0~M]上等概率的獲得一個(gè)值
求K次打擊之后，英雄把怪獸砍死的概率
arr是面值數(shù)組作彤，其中的值都是正數(shù)且沒(méi)有重復(fù)膘魄。再給定一個(gè)正數(shù)aim乌逐。
每個(gè)值都認(rèn)為是一種面值，且認(rèn)為張數(shù)是無(wú)限的创葡。
返回組成aim的最少貨幣數(shù)
給定一個(gè)正數(shù)n浙踢，求n的裂開(kāi)方法數(shù)，
規(guī)定：后面的數(shù)不能比前面的數(shù)小
比如4的裂開(kāi)方法有：
1+1+1+1灿渴、1+1+2洛波、1+3、2+2骚露、4
5種蹬挤，所以返回5
23 暴力遞歸到動(dòng)態(tài)規(guī)劃（六）
內(nèi)容：
以18節(jié)為總綱
通過(guò)面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
位信息技巧
題目：
給定一個(gè)正數(shù)數(shù)組arr，
請(qǐng)把a(bǔ)rr中所有的數(shù)分成兩個(gè)集合棘幸，盡量讓兩個(gè)集合的累加和接近
返回最接近的情況下焰扳，較小集合的累加和
給定一個(gè)正數(shù)數(shù)組arr，請(qǐng)把a(bǔ)rr中所有的數(shù)分成兩個(gè)集合
如果arr長(zhǎng)度為偶數(shù)误续，兩個(gè)集合包含數(shù)的個(gè)數(shù)要一樣多
如果arr長(zhǎng)度為奇數(shù)吨悍，兩個(gè)集合包含數(shù)的個(gè)數(shù)必須只差一個(gè)
請(qǐng)盡量讓兩個(gè)集合的累加和接近
返回最接近的情況下，較小集合的累加和
N皇后問(wèn)題是指在N*N的棋盤上要擺N個(gè)皇后蹋嵌，
要求任何兩個(gè)皇后不同行育瓜、不同列， 也不在同一條斜線上
?給定一個(gè)整數(shù)n栽烂，返回n皇后的擺法有多少種躏仇。?n=1，返回1
n=2或3腺办，2皇后和3皇后問(wèn)題無(wú)論怎么擺都不行焰手，返回0
n=8，返回92
24 窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)
內(nèi)容：
滑動(dòng)窗口
窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)
用題目來(lái)學(xué)習(xí)窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)提供的便利性
題目：
窗口內(nèi)最大值或最小值更新結(jié)構(gòu)的實(shí)現(xiàn)
假設(shè)一個(gè)固定大小為W的窗口菇晃，依次劃過(guò)arr册倒，
返回每一次滑出狀況的最大值
例如，arr = [4,3,5,4,3,3,6,7], W = 3
返回：[5,5,5,4,6,7]
給定一個(gè)整型數(shù)組arr磺送，和一個(gè)整數(shù)num
某個(gè)arr中的子數(shù)組sub驻子，如果想達(dá)標(biāo)，必須滿足：sub中最大值 – sub中最小值 <= num估灿，
返回arr中達(dá)標(biāo)子數(shù)組的數(shù)量
加油站的良好出發(fā)點(diǎn)問(wèn)題
動(dòng)態(tài)規(guī)劃中利用窗口內(nèi)最大值或最小值更新結(jié)構(gòu)做優(yōu)化（難）
arr是貨幣數(shù)組崇呵，其中的值都是正數(shù)。再給定一個(gè)正數(shù)aim馅袁。
每個(gè)值都認(rèn)為是一張貨幣域慷，
返回組成aim的最少貨幣數(shù)
注意：因?yàn)槭乔笞钌儇泿艛?shù)，所以每一張貨幣認(rèn)為是相同或者不同就不重要了
25 單調(diào)棧
內(nèi)容：
單調(diào)棧的原理（無(wú)重復(fù)數(shù)+有重復(fù)數(shù)）
用題目來(lái)學(xué)習(xí)單調(diào)棧提供的便利性
題目：
單調(diào)棧實(shí)現(xiàn)（無(wú)重復(fù)數(shù)+有重復(fù)數(shù)）
給定一個(gè)只包含正數(shù)的數(shù)組arr，arr中任何一個(gè)子數(shù)組sub犹褒，
一定都可以算出(sub累加和 )* (sub中的最小值)是什么抵窒，
那么所有子數(shù)組中，這個(gè)值最大是多少叠骑？
給定一個(gè)非負(fù)數(shù)組arr李皇，代表直方圖，返回直方圖的最大長(zhǎng)方形面積
給定一個(gè)二維數(shù)組matrix宙枷，其中的值不是0就是1掉房，返回全部由1組成的最大子矩形內(nèi)部有多少個(gè)1（面積）
給定一個(gè)二維數(shù)組matrix，其中的值不是0就是1慰丛，返回全部由1組成的子矩形數(shù)量
26 單調(diào)棧相關(guān)的題目（續(xù)）卓囚、斐波那契數(shù)列的矩陣快速冪模型
內(nèi)容：
再講一個(gè)單調(diào)棧相關(guān)的面試題
斐波那契數(shù)列的矩陣快速冪模型詳解
題目：
給定一個(gè)數(shù)組arr，返回所有子數(shù)組最小值的累加和
斐波那契數(shù)列矩陣乘法方式的實(shí)現(xiàn)
臺(tái)階方法數(shù)問(wèn)題
一個(gè)人可以一次往上邁1個(gè)臺(tái)階诅病，也可以邁2個(gè)臺(tái)階哪亿，返回邁上N級(jí)臺(tái)階的方法數(shù)
奶牛生小牛問(wèn)題
第一年農(nóng)場(chǎng)有1只成熟的母牛A，往后的每年：
1）每一只成熟的母牛都會(huì)生一只母牛
2）每一只新出生的母牛都在出生的第三年成熟
3）每一只母牛永遠(yuǎn)不會(huì)死
返回N年后牛的數(shù)量
給定一個(gè)數(shù)N贤笆，想象只由0和1兩種字符锣夹，組成的所有長(zhǎng)度為N的字符串
如果某個(gè)字符串，任何0字符的左邊都有1緊挨著苏潜，認(rèn)為這個(gè)字符串達(dá)標(biāo)
返回有多少達(dá)標(biāo)的字符串
用12的瓷磚，把N2的區(qū)域填滿变勇，返回鋪瓷磚的方法數(shù)
27 KMP算法
內(nèi)容：
KMP算法
和KMP算法相關(guān)的面試題
題目：
KMP算法實(shí)現(xiàn)
給定兩棵二叉樹(shù)的頭節(jié)點(diǎn)head1和head2恤左，返回head1中是否有某個(gè)子樹(shù)的結(jié)構(gòu)和head2完全一樣
判斷str1和str2是否互為旋轉(zhuǎn)字符串
28 Manacher算法
內(nèi)容：
Manacher算法
和Manacher算法相關(guān)的面試題
題目：
Manacher算法實(shí)現(xiàn)
給定一個(gè)字符串str，只能在str的后面添加字符搀绣，想讓str整體變成回文串飞袋，返回至少要添加幾個(gè)字符
29 在無(wú)序數(shù)組中找到第K小的數(shù)、蓄水池算法
內(nèi)容：
時(shí)間復(fù)雜度O(N)可以解決在無(wú)序數(shù)組中找到第K小的數(shù)链患，這個(gè)經(jīng)典的面試題
改寫快排的partition方法
bfprt算法
蓄水池算法
題目：
在無(wú)序數(shù)組中找到第K小的數(shù)（改寫快排+bfprt）
設(shè)計(jì)在無(wú)序數(shù)組中收集最大的前K個(gè)數(shù)字的算法（根據(jù)不同的三個(gè)時(shí)間復(fù)雜度巧鸭，設(shè)計(jì)三個(gè)算法）
給定一個(gè)無(wú)序數(shù)組arr中，長(zhǎng)度為N麻捻，給定一個(gè)正數(shù)k纲仍，返回top k個(gè)最大的數(shù)
不同時(shí)間復(fù)雜度三個(gè)方法：
1）O(NlogN)
2）O(N + KlogN)
3）O(n + k*logk)
蓄水池算法實(shí)現(xiàn)
假設(shè)有一個(gè)源源吐出不同球的機(jī)器，
只有裝下10個(gè)球的袋子贸毕，每一個(gè)吐出的球郑叠，要么放入袋子，要么永遠(yuǎn)扔掉
如何做到機(jī)器吐出每一個(gè)球之后明棍，所有吐出的球都等概率被放進(jìn)袋子里
30 二叉樹(shù)的Morris遍歷
內(nèi)容：
二叉樹(shù)之前的遍歷方式有空間浪費(fèi)的問(wèn)題
Morris遍歷時(shí)間復(fù)雜度O(N)乡革，額外空間復(fù)雜度O(1)，通過(guò)利用原樹(shù)中大量空閑指針的方式，達(dá)到節(jié)省空間的目的
假設(shè)來(lái)到當(dāng)前節(jié)點(diǎn)cur沸版，開(kāi)始時(shí)cur來(lái)到頭節(jié)點(diǎn)位置
1）如果cur沒(méi)有左孩子嘁傀，cur向右移動(dòng)(cur = cur.right)
2）如果cur有左孩子，找到左子樹(shù)上最右的節(jié)點(diǎn)mostRight：
a.如果mostRight的右指針指向空视粮，讓其指向cur细办，
然后cur向左移動(dòng)(cur = cur.left)
b.如果mostRight的右指針指向cur，讓其指向null馒铃，
然后cur向右移動(dòng)(cur = cur.right)
3）cur為空時(shí)遍歷停止
Morris遍歷實(shí)現(xiàn)二叉樹(shù)的先序蟹腾、中序、后序遍歷
題目：
Morris遍歷的實(shí)現(xiàn)
給定一棵二叉樹(shù)的頭節(jié)點(diǎn)head区宇，求以head為頭的樹(shù)中娃殖，最小深度是多少？
31 線段樹(shù)
內(nèi)容：
線段樹(shù)是一種支持范圍整體修改和范圍整體查詢的數(shù)據(jù)結(jié)構(gòu)
線段樹(shù)解決的問(wèn)題范疇：大范圍信息可以只由左议谷、右兩側(cè)信息加工出炉爆，而不必遍歷左右兩個(gè)子范圍的具體狀況
題目：
給定一個(gè)數(shù)組arr，用戶希望你實(shí)現(xiàn)如下三個(gè)方法
1）void add(int L, int R, int V) : 讓數(shù)組arr[L…R]上每個(gè)數(shù)都加上V
2）void update(int L, int R, int V) : 讓數(shù)組arr[L…R]上每個(gè)數(shù)都變成V
3）int sum(int L, int R) :讓返回arr[L…R]這個(gè)范圍整體的累加和
怎么讓這三個(gè)方法卧晓，時(shí)間復(fù)雜度都是O(logN)
想象一下標(biāo)準(zhǔn)的俄羅斯方塊游戲芬首，X軸是積木最終下落到底的軸線
下面是這個(gè)游戲的簡(jiǎn)化版：
1）只會(huì)下落正方形積木
2）[a,b] -> 代表一個(gè)邊長(zhǎng)為b的正方形積木，積木左邊緣沿著X = a這條線從上方掉落
3）認(rèn)為整個(gè)X軸都可能接住積木逼裆，也就是說(shuō)簡(jiǎn)化版游戲是沒(méi)有整體的左右邊界的
4）沒(méi)有整體的左右邊界郁稍，所以簡(jiǎn)化版游戲不會(huì)消除積木，因?yàn)椴粫?huì)有哪一層被填滿胜宇。
給定一個(gè)N*2的二維數(shù)組matrix耀怜，可以代表N個(gè)積木依次掉落，
返回每一次掉落之后的最大高度
Leetcode題目：https://leetcode.com/problems/falling-squares/
32 IndexTree桐愉、AC自動(dòng)機(jī)
內(nèi)容：
IndexTree
1）支持區(qū)間查詢
2）沒(méi)有線段樹(shù)那么強(qiáng)财破，但是非常容易改成一維、二維从诲、三維的結(jié)構(gòu)
3）只支持單點(diǎn)更新
AC自動(dòng)機(jī)
解決在一個(gè)大字符串中左痢，找到多個(gè)候選字符串的問(wèn)題
1）把所有匹配串生成一棵前綴樹(shù)
2）前綴樹(shù)節(jié)點(diǎn)增加fail指針
3）fail指針的含義：如果必須以當(dāng)前字符結(jié)尾，當(dāng)前形成的路徑是str系洛，剩下哪一個(gè)字符串的前綴和str的后綴
擁有最大的匹配長(zhǎng)度俊性。fail指針就指向那個(gè)字符串的最后一個(gè)字符所對(duì)應(yīng)的節(jié)點(diǎn)（迷不迷？聽(tīng)講述Ｃ璩丁）
題目：
IndexTree在一維數(shù)組和二維數(shù)組上的實(shí)現(xiàn)
AC自動(dòng)機(jī)的實(shí)現(xiàn)
33 與哈希函數(shù)有關(guān)的結(jié)構(gòu)
內(nèi)容：
哈希函數(shù)
哈希函數(shù)的應(yīng)用
布隆過(guò)濾器
一致性哈希
題目：
原理講述為主磅废，面試只會(huì)聊設(shè)計(jì)，所以本節(jié)無(wú)題目
34 資源限制類題目的解題套路
內(nèi)容：
布隆過(guò)濾器用于集合的建立與查詢荆烈，并可以節(jié)省大量空間
一致性哈希解決數(shù)據(jù)服務(wù)器的負(fù)載管理問(wèn)題
利用并查集結(jié)構(gòu)做島問(wèn)題的并行計(jì)算
哈希函數(shù)可以把數(shù)據(jù)按照種類均勻分流
位圖解決某一范圍上數(shù)字的出現(xiàn)情況拯勉，并可以節(jié)省大量空間
利用分段統(tǒng)計(jì)思想竟趾、并進(jìn)一步節(jié)省大量空間
利用堆、外排序來(lái)做多個(gè)處理單元的結(jié)果合并
題目：
32位無(wú)符號(hào)整數(shù)的范圍是0~4,294,967,295宫峦，
現(xiàn)在有一個(gè)正好包含40億個(gè)無(wú)符號(hào)整數(shù)的文件岔帽，
可以使用最多1GB的內(nèi)存，怎么找到出現(xiàn)次數(shù)最多的數(shù)导绷？
32位無(wú)符號(hào)整數(shù)的范圍是0~4,294,967,295犀勒，現(xiàn)在有一個(gè)正好包含40億個(gè)無(wú)符號(hào)整數(shù)的文件，
所以在整個(gè)范圍中必然存在沒(méi)出現(xiàn)過(guò)的數(shù)妥曲，可以使用最多1GB的內(nèi)存贾费，怎么找到所有未出現(xiàn)過(guò)的數(shù)？
進(jìn)階：內(nèi)存限制為 3KB檐盟，但是只用找到一個(gè)沒(méi)出現(xiàn)過(guò)的數(shù)即可
有一個(gè)包含100億個(gè)URL的大文件褂萧，假設(shè)每個(gè)URL占用64B，請(qǐng)找出其中所有重復(fù)的URL
補(bǔ)充：某搜索公司一天的用戶搜索詞匯是海量的(百億數(shù)據(jù)量)葵萎，請(qǐng)?jiān)O(shè)計(jì)一種求出每天熱門Top100詞匯的可行辦法
32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295导犹，現(xiàn)在有40億個(gè)無(wú)符號(hào)整數(shù)，可以使用最多1GB的內(nèi)存羡忘，找出所有出現(xiàn)了兩次的數(shù)
32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295谎痢，現(xiàn)在有40億個(gè)無(wú)符號(hào)整數(shù)，可以使用最多3K的內(nèi)存卷雕，怎么找到這40億個(gè)整數(shù)的中位數(shù)节猿？
32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295，有一個(gè)10G大小的文件漫雕，每一行都裝著這種類型的數(shù)字沐批，
整個(gè)文件是無(wú)序的，給你5G的內(nèi)存空間蝎亚，請(qǐng)你輸出一個(gè)10G大小的文件，就是原文件所有數(shù)字排序的結(jié)果
35 有序表（上）
內(nèi)容：
平衡搜索二叉樹(shù)
左旋
右旋
AVL樹(shù)的節(jié)點(diǎn)違規(guī)4種類型（LL先馆，LR发框，RL，RR）
題目：
AVL樹(shù)的實(shí)現(xiàn)
36 有序表（中）
內(nèi)容：
size-balanced-tree詳解
skiplist詳解
聊聊紅黑樹(shù)
題目：
size-balanced-tree實(shí)現(xiàn)
skiplist實(shí)現(xiàn)
37 有序表（下）
內(nèi)容：
講解有序表相關(guān)的面試題
講解改寫有序表的題目核心點(diǎn)
題目：
給定一個(gè)數(shù)組arr煤墙，和兩個(gè)整數(shù)a和b（a<=b）梅惯。求arr中有多少個(gè)子數(shù)組，累加和在[a,b]這個(gè)范圍上仿野。返回達(dá)標(biāo)的子數(shù)組數(shù)量
有一個(gè)滑動(dòng)窗口：
1）L是滑動(dòng)窗口最左位置铣减、R是滑動(dòng)窗口最右位置，一開(kāi)始LR都在數(shù)組左側(cè)
2）任何一步都可能R往右動(dòng)脚作，表示某個(gè)數(shù)進(jìn)了窗口
3）任何一步都可能L往右動(dòng)葫哗，表示某個(gè)數(shù)出了窗口
想知道每一個(gè)窗口狀態(tài)的中位數(shù)
設(shè)計(jì)一個(gè)結(jié)構(gòu)包含如下兩個(gè)方法：
void add(int index, int num)：把num加入到index位置
int get(int index) ：取出index位置的值
void remove(int index) ：把index位置上的值刪除
要求三個(gè)方法時(shí)間復(fù)雜度O(logN)
假設(shè)有打亂順序的一群人站成一個(gè)隊(duì)列缔刹，數(shù)組people表示隊(duì)列中一些人的屬性（不一定按順序）
每個(gè)people[i]=[hi, ki]表示第i個(gè)人的身高為hi，前面正好有ki個(gè)身高大于或等于hi的人
請(qǐng)你重新構(gòu)造并返回輸入數(shù)組people所表示的隊(duì)列劣针，返回的隊(duì)列應(yīng)該格式化為數(shù)組queue
其中queue[j]=[hj, kj]是隊(duì)列中第j個(gè)人的屬性（queue[0] 是排在隊(duì)列前面的人）校镐。
Leetcode題目：https://leetcode.com/problems/queue-reconstruction-by-height/
38 根據(jù)對(duì)數(shù)器找規(guī)律、根據(jù)數(shù)據(jù)量猜解法
內(nèi)容：
講解對(duì)數(shù)器找規(guī)律的解題技巧
講解根據(jù)數(shù)據(jù)量猜解法的技巧
1）C/C++捺典，1秒處理的指令條數(shù)為10的8次方
2）Java等語(yǔ)言鸟廓，1~4秒處理的指令條數(shù)為10的8次方
3）這里就有大量的分析提示了
題目：
小虎去買蘋果，商店只提供兩種類型的塑料袋襟己，每種類型都有任意數(shù)量
1）能裝下6個(gè)蘋果的袋子
2）能裝下8個(gè)蘋果的袋子
小虎可以自由使用兩種袋子來(lái)裝蘋果引谜，但是小虎有強(qiáng)迫癥，他要求自己使用的袋子數(shù)量必須最少擎浴，
且使用的每個(gè)袋子必須裝滿员咽，給定一個(gè)正整數(shù)N，返回至少使用多少袋子退客。如果N無(wú)法讓使用的每個(gè)袋子必須裝滿骏融，返回-1
給定一個(gè)正整數(shù)N，表示有N份青草統(tǒng)一堆放在倉(cāng)庫(kù)里萌狂，有一只牛和一只羊档玻，牛先吃，羊后吃茫藏，它倆輪流吃草
不管是牛還是羊误趴，每一輪能吃的草量必須是：1，4务傲，16凉当，64…(4的某次方)
誰(shuí)最先把草吃完，誰(shuí)獲勝售葡，假設(shè)牛和羊都絕頂聰明看杭，都想贏，都會(huì)做出理性的決定挟伙。根據(jù)唯一的參數(shù)N楼雹，返回誰(shuí)會(huì)贏
定義一種數(shù)：可以表示成若干（數(shù)量>1）連續(xù)正數(shù)和的數(shù)
比如，5=2+3尖阔，5就是這樣的數(shù)贮缅；12=3+4+5，12就是這樣的數(shù)
2=1+1介却，2不是這樣的數(shù)谴供，因?yàn)榈忍?hào)右邊不是連續(xù)正數(shù)
給定一個(gè)參數(shù)N，返回是不是可以表示成若干連續(xù)正數(shù)和的數(shù)
int[] d齿坷，d[i]：i號(hào)怪獸的能力
int[] p桂肌，p[i]：i號(hào)怪獸要求的錢
開(kāi)始時(shí)你的能力是0数焊，你的目標(biāo)是從0號(hào)怪獸開(kāi)始，通過(guò)所有的怪獸轴或。
如果你當(dāng)前的能力昌跌，小于i號(hào)怪獸的能力，你必須付出p[i]的錢照雁，賄賂這個(gè)怪獸蚕愤，然后怪獸就會(huì)加入你
他的能力直接累加到你的能力上；如果你當(dāng)前的能力饺蚊，大于等于i號(hào)怪獸的能力
你可以選擇直接通過(guò)萍诱，你的能力并不會(huì)下降，你也可以選擇賄賂這個(gè)怪獸污呼，然后怪獸就會(huì)加入你
他的能力直接累加到你的能力上
返回通過(guò)所有的怪獸裕坊，需要花的最小錢數(shù)
（課上會(huì)給出不同的數(shù)據(jù)量描述）
39 根據(jù)數(shù)據(jù)量猜解法（續(xù)）、分治技巧燕酷、卡特蘭數(shù)
內(nèi)容：
繼續(xù)熟悉根據(jù)數(shù)據(jù)量猜解法
講解分治法
講解卡特蘭數(shù)（課上證明的時(shí)候有小錯(cuò)籍凝，在40節(jié)開(kāi)始處修正了）
題目：
給定一個(gè)非負(fù)數(shù)組arr，和一個(gè)正數(shù)m苗缩，返回arr的所有子序列中累加和%m之后的最大值
牛牛家里一共有n袋零食, 第i袋零食體積為v[i]饵蒂，背包容量為w，牛牛想知道在總體積不超過(guò)背包容量的情況下,
一共有多少種零食放法酱讶，體積為0也算一種放法
1 <= n <= 30, 1 <= w <= 2 * 10^9退盯，v[I] (0 <= v[i] <= 10^9）
假設(shè)給你N個(gè)0，和N個(gè)1泻肯，你必須用全部數(shù)字拼序列渊迁，返回有多少個(gè)序列滿足任何前綴串，1的數(shù)量都不少于0的數(shù)量
有N個(gè)二叉樹(shù)節(jié)點(diǎn)灶挟，每個(gè)節(jié)點(diǎn)彼此之間無(wú)任何差別琉朽，返回由N個(gè)二叉樹(shù)節(jié)點(diǎn)，組成的不同結(jié)構(gòu)數(shù)量是多少稚铣？
題目補(bǔ)充： arr中的值可能為正箱叁，可能為負(fù)，可能為0榛泛，自由選擇arr中的數(shù)字，能不能累加得到sum（多種做法）
40 子數(shù)組達(dá)到規(guī)定累加和的最大長(zhǎng)度系列問(wèn)題噩斟、矩陣處理技巧題
內(nèi)容：
修正了39節(jié)卡特蘭數(shù)講解時(shí)的一個(gè)小錯(cuò)誤
熟悉子數(shù)組達(dá)到規(guī)定累加和的三個(gè)模型（正曹锨、有正有負(fù)有0、累加和<=K）
矩陣處理技巧的宏觀調(diào)度coding技巧
題目：
給定一個(gè)正整數(shù)組成的無(wú)序數(shù)組arr剃允，給定一個(gè)正整數(shù)值K沛简，找到arr的所有子數(shù)組里齐鲤，哪個(gè)子數(shù)組的累加和等于K
并且是長(zhǎng)度最大的，返回其長(zhǎng)度
給定一個(gè)整數(shù)組成的無(wú)序數(shù)組arr椒楣，值可能正给郊、可能負(fù)、可能0捧灰，給定一個(gè)整數(shù)值K
找到arr的所有子數(shù)組里淆九，哪個(gè)子數(shù)組的累加和等于K，并且是長(zhǎng)度最大的毛俏，返回其長(zhǎng)度
給定一個(gè)整數(shù)組成的無(wú)序數(shù)組arr炭庙，值可能正、可能負(fù)煌寇、可能0芥备，給定一個(gè)整數(shù)值K
找到arr的所有子數(shù)組里笆凌，哪個(gè)子數(shù)組的累加和<=K，并且是長(zhǎng)度最大的，返回其長(zhǎng)度
給定一個(gè)數(shù)組arr绊起，給定一個(gè)值v，求子數(shù)組平均值小于等于v的最長(zhǎng)子數(shù)組長(zhǎng)度
給定一個(gè)正方形矩陣matrix酥筝，原地調(diào)整成順時(shí)針90度轉(zhuǎn)動(dòng)的樣子
給定一個(gè)正方形或者長(zhǎng)方形矩陣matrix遭京，實(shí)現(xiàn)轉(zhuǎn)圈打印
給定一個(gè)正方形或者長(zhǎng)方形矩陣matrix，實(shí)現(xiàn)zigzag打印
轉(zhuǎn)圈打印星號(hào)*問(wèn)題
41 四邊形不等式技巧（上）
內(nèi)容：
區(qū)間劃分問(wèn)題中的劃分點(diǎn)不回退現(xiàn)象
四邊形不等式技巧特征
1徒仓，兩個(gè)可變參數(shù)的區(qū)間劃分問(wèn)題
2腐碱，每個(gè)格子有枚舉行為
3，當(dāng)兩個(gè)可變參數(shù)固定一個(gè)掉弛，另一個(gè)參數(shù)和答案之間存在單調(diào)性關(guān)系
4症见，而且兩組單調(diào)關(guān)系是反向的：(升 升，降 降) (升 降殃饿，降 升)
5谋作，能否獲得指導(dǎo)枚舉優(yōu)化的位置對(duì)：上+右，或者乎芳，左+下
四邊形不等式技巧注意點(diǎn)
1遵蚜，不要證明！用對(duì)數(shù)器驗(yàn)證奈惑！
2吭净，枚舉的時(shí)候面對(duì)最優(yōu)答案相等的時(shí)候怎么處理？用對(duì)數(shù)器都試試肴甸！
3寂殉，可以把時(shí)間復(fù)雜度降低一階
O(N^3) -> O(N^2)
O(N^2 * M) -> O(N * M)
O(N * M^2) -> O(N * M)
4，四邊形不等式有些時(shí)候是最優(yōu)解原在，有些時(shí)候不是
不是的原因：嘗試思路友扰，在根兒上不夠好
題目：
給定一個(gè)非負(fù)數(shù)組arr彤叉，長(zhǎng)度為N，
那么有N-1種方案可以把a(bǔ)rr切成左右兩部分
每一種方案都有村怪，min{左部分累加和秽浇，右部分累加和}
求這么多方案中，min{左部分累加和甚负，右部分累加和}的最大值是多少柬焕？
整個(gè)過(guò)程要求時(shí)間復(fù)雜度O(N)
把題目一中提到的，min{左部分累加和腊敲，右部分累加和}击喂，定義為S(N-1)，也就是說(shuō)：
S(N-1)：在arr[0…N-1]范圍上碰辅，做最優(yōu)劃分所得到的min{左部分累加和懂昂，右部分累加和}的最大值
現(xiàn)在要求返回一個(gè)長(zhǎng)度為N的s數(shù)組，
s[i] =在arr[0…i]范圍上没宾，做最優(yōu)劃分所得到的min{左部分累加和凌彬，右部分累加和}的最大值
得到整個(gè)s數(shù)組的過(guò)程，做到時(shí)間復(fù)雜度O(N)
擺放著n堆石子⊙ィ現(xiàn)要將石子有次序地合并成一堆铲敛，規(guī)定每次只能選相鄰的2堆石子合并成新的一堆
并將新的一堆石子數(shù)記為該次合并的得分，求出將n堆石子合并成一堆的最小得分（或最大得分）合并方案
給定一個(gè)整型數(shù)組 arr会钝，數(shù)組中的每個(gè)值都為正數(shù)伐蒋，表示完成一幅畫作需要的時(shí)間，再給定一個(gè)整數(shù)num
表示畫匠的數(shù)量迁酸，每個(gè)畫匠只能畫連在一起的畫作
所有的畫家并行工作先鱼，返回完成所有的畫作需要的最少時(shí)間
arr=[3,1,4]，num=2奸鬓。
最好的分配方式為第一個(gè)畫匠畫3和1焙畔，所需時(shí)間為4
第二個(gè)畫匠畫4，所需時(shí)間為4
所以返回4
arr=[1,1,1,4,3]串远，num=3
最好的分配方式為第一個(gè)畫匠畫前三個(gè)1宏多，所需時(shí)間為3
第二個(gè)畫匠畫4，所需時(shí)間為4
第三個(gè)畫匠畫3澡罚，所需時(shí)間為3
返回4
42 四邊形不等式技巧（下）
內(nèi)容：
繼續(xù)熟悉四邊形不等式
展示好的嘗試是最關(guān)鍵的
題目：
一條直線上有居民點(diǎn)伸但，郵局只能建在居民點(diǎn)上
給定一個(gè)有序正數(shù)數(shù)組arr，每個(gè)值表示 居民點(diǎn)的一維坐標(biāo)留搔，再給定一個(gè)正數(shù) num更胖，表示郵局?jǐn)?shù)量
選擇num個(gè)居民點(diǎn)建立num個(gè)郵局，使所有的居民點(diǎn)到最近郵局的總距離最短，返回最短的總距離
arr=[1,2,3,4,5,1000]函喉，num=2
第一個(gè)郵局建立在3位置，第二個(gè)郵局建立在1000位置
那么1位置到郵局的距離為2荣月，2位置到郵局距離為1管呵，3位置到郵局的距離為0，4位置到郵局的距離為1哺窄，5位置到郵局的距離為2
1000位置到郵局的距離為0
這種方案下的總距離為6捐下，其他任何方案的總距離都不會(huì)比該方案的總距離更短，所以返回6
一座大樓有0~N層萌业，地面算作第0層坷襟，最高的一層為第N層
已知棋子從第0層掉落肯定不會(huì)摔碎，從第i層掉落可能會(huì)摔碎生年，也可能不會(huì)摔碎(1≤i≤N)
給定整數(shù)N作為樓層數(shù)婴程，再給定整數(shù)K作為棋子數(shù)
返回如果想找到棋子不會(huì)摔碎的最高層數(shù)，即使在最差的情況下扔的最少次數(shù)
一次只能扔一個(gè)棋子
N=10抱婉，K=1
返回10
因?yàn)橹挥?棵棋子档叔，所以不得不從第1層開(kāi)始一直試到第10層
在最差的情況下，即第10層是不會(huì)摔壞的最高層蒸绩，最少也要扔10次
N=3衙四，K=2
返回2
先在2層扔1棵棋子，如果碎了試第1層患亿，如果沒(méi)碎試第3層
N=105传蹈，K=2
返回14
第一個(gè)棋子先在14層扔，碎了則用僅存的一個(gè)棋子試1~13
若沒(méi)碎步藕，第一個(gè)棋子繼續(xù)在27層扔惦界，碎了則用僅存的一個(gè)棋子試15~26
若沒(méi)碎，第一個(gè)棋子繼續(xù)在39層扔漱抓，碎了則用僅存的一個(gè)棋子試28~38
若沒(méi)碎表锻，第一個(gè)棋子繼續(xù)在50層扔，碎了則用僅存的一個(gè)棋子試40~49
若沒(méi)碎乞娄，第一個(gè)棋子繼續(xù)在60層扔瞬逊，碎了則用僅存的一個(gè)棋子試51~59
若沒(méi)碎，第一個(gè)棋子繼續(xù)在69層扔仪或，碎了則用僅存的一個(gè)棋子試61~68
若沒(méi)碎确镊，第一個(gè)棋子繼續(xù)在77層扔，碎了則用僅存的一個(gè)棋子試70~76
若沒(méi)碎范删，第一個(gè)棋子繼續(xù)在84層扔蕾域，碎了則用僅存的一個(gè)棋子試78~83
若沒(méi)碎，第一個(gè)棋子繼續(xù)在90層扔，碎了則用僅存的一個(gè)棋子試85~89
若沒(méi)碎旨巷，第一個(gè)棋子繼續(xù)在95層扔巨缘，碎了則用僅存的一個(gè)棋子試91~94
若沒(méi)碎，第一個(gè)棋子繼續(xù)在99層扔采呐，碎了則用僅存的一個(gè)棋子試96~98
若沒(méi)碎若锁，第一個(gè)棋子繼續(xù)在102層扔，碎了則用僅存的一個(gè)棋子試100斧吐、101
若沒(méi)碎又固，第一個(gè)棋子繼續(xù)在104層扔，碎了則用僅存的一個(gè)棋子試103
若沒(méi)碎煤率，第一個(gè)棋子繼續(xù)在105層扔仰冠，若到這一步還沒(méi)碎，那么105便是結(jié)果
43 狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃
內(nèi)容：
動(dòng)態(tài)規(guī)劃的狀態(tài)壓縮技巧
題目：
在"100 game"這個(gè)游戲中蝶糯，兩名玩家輪流選擇從1到10的任意整數(shù)洋只，累計(jì)整數(shù)和
先使得累計(jì)整數(shù)和達(dá)到或超過(guò)100的玩家，即為勝者昼捍，如果我們將游戲規(guī)則改為 “玩家不能重復(fù)使用整數(shù)” 呢木张？
例如，兩個(gè)玩家可以輪流從公共整數(shù)池中抽取從1到15的整數(shù)（不放回）端三，直到累計(jì)整數(shù)和 >= 100
給定一個(gè)整數(shù) maxChoosableInteger （整數(shù)池中可選擇的最大數(shù)）和另一個(gè)整數(shù) desiredTotal（累計(jì)和）
判斷先出手的玩家是否能穩(wěn)贏（假設(shè)兩位玩家游戲時(shí)都表現(xiàn)最佳）
你可以假設(shè) maxChoosableInteger 不會(huì)大于 20舷礼， desiredTotal 不會(huì)大于 300。
Leetcode題目：https://leetcode.com/problems/can-i-win/
TSP問(wèn)題
有N個(gè)城市郊闯，任何兩個(gè)城市之間的都有距離妻献，任何一座城市到自己的距離都為0
所有點(diǎn)到點(diǎn)的距離都存在一個(gè)N*N的二維數(shù)組matrix里，也就是整張圖由鄰接矩陣表示
現(xiàn)要求一旅行商從k城市出發(fā)必須經(jīng)過(guò)每一個(gè)城市且只在一個(gè)城市逗留一次团赁，最后回到出發(fā)的k城
參數(shù)給定一個(gè)matrix育拨，給定k。返回總距離最短的路的距離
鋪磚問(wèn)題（最優(yōu)解其實(shí)是輪廓線dp欢摄，但是這個(gè)解法對(duì)大廠刷題來(lái)說(shuō)比較難熬丧，掌握課上的解法即可）
你有無(wú)限的12的磚塊，要鋪滿MN的區(qū)域怀挠，
不同的鋪法有多少種?
44 DC3生成后綴數(shù)組詳解
內(nèi)容：
后綴數(shù)組
介紹用DC3算法生成后綴數(shù)組的流程
題目：
給你一個(gè)字符串 s析蝴，找出它的所有子串并按字典序排列，返回排在最后的那個(gè)子串
Leetcode題目：https://leetcode.com/problems/last-substring-in-lexicographical-order/
DC3算法的實(shí)現(xiàn)（完全根據(jù)論文描述）
45 后綴數(shù)組解決的面試題
內(nèi)容：
通過(guò)題目進(jìn)一步熟悉DC3算法
通過(guò)DC3算法得到height數(shù)組
題目：
給定兩個(gè)字符串str1和str2绿淋，想把str2整體插入到str1中的某個(gè)位置闷畸，形成最大的字典序，返回字典序最大的結(jié)果
給兩個(gè)長(zhǎng)度分別為M和N的整型數(shù)組nums1和nums2吞滞，其中每個(gè)值都不大于9佑菩，再給定一個(gè)正數(shù)K盾沫。 你可以在nums1和nums2中挑選數(shù)字，要求一共挑選K個(gè)殿漠，并且要從左到右挑赴精。返回所有可能的結(jié)果中，代表最大數(shù)字的結(jié)果
最長(zhǎng)公共子串問(wèn)題是面試常見(jiàn)題目之一绞幌，假設(shè)str1長(zhǎng)度N祖娘，str2長(zhǎng)度M
一般在面試場(chǎng)上回答出O(NM)的解法已經(jīng)是比較優(yōu)秀了
因?yàn)榈玫絆(NM)的解法，就已經(jīng)需要用到動(dòng)態(tài)規(guī)劃了
但其實(shí)這個(gè)問(wèn)題的最優(yōu)解是O(N+M)啊奄，需要用到后綴數(shù)組+height數(shù)組
課上將對(duì)本題解法代碼進(jìn)行詳解
46 動(dòng)態(tài)規(guī)劃猜法中和外部信息簡(jiǎn)化的相關(guān)問(wèn)題（上）、哈夫曼樹(shù)
內(nèi)容：
以18節(jié)做總綱
有些動(dòng)態(tài)規(guī)劃面試題掀潮，需要很好的設(shè)計(jì)參數(shù)菇夸，這種設(shè)計(jì)方式都有"外部信息簡(jiǎn)化"的特征
哈夫曼樹(shù)
題目：
有n個(gè)氣球，編號(hào)為0到n-1仪吧，每個(gè)氣球上都標(biāo)有一個(gè)數(shù)字庄新，這些數(shù)字存在數(shù)組nums中
現(xiàn)在要求你戳破所有的氣球。戳破第i個(gè)氣球薯鼠，你可以獲得nums[i - 1] * nums[i] * nums[i + 1] 枚硬幣
這里的i-1和i+1代表和i相鄰的择诈、沒(méi)有被戳爆的！兩個(gè)氣球的序號(hào)
如果i-1或i+1超出了數(shù)組的邊界出皇，那么就當(dāng)它是一個(gè)數(shù)字為1的氣球
求所能獲得硬幣的最大數(shù)量
Leetcode題目：https://leetcode.com/problems/burst-balloons/
給出一些不同顏色的盒子羞芍，盒子的顏色由數(shù)字表示，即不同的數(shù)字表示不同的顏色郊艘，你將經(jīng)過(guò)若干輪操作去去掉盒子
直到所有的盒子都去掉為止荷科，每一輪你可以移除具有相同顏色的連續(xù)k個(gè)盒子（k >= 1）
這樣一輪之后你將得到 k * k 個(gè)積分，當(dāng)你將所有盒子都去掉之后纱注，求你能獲得的最大積分和
Leetcode題目：https://leetcode.com/problems/remove-boxes/
如果一個(gè)字符相鄰的位置沒(méi)有相同字符畏浆，那么這個(gè)位置的字符出現(xiàn)不能被消掉
比如:"ab"，其中a和b都不能被消掉
如果一個(gè)字符相鄰的位置有相同字符狞贱，就可以一起消掉
比如:"abbbc"刻获，中間一串的b是可以被消掉的，消除之后剩下"ac"
某些字符如果消掉了瞎嬉，剩下的字符認(rèn)為重新靠在一起
給定一個(gè)字符串蝎毡，你可以決定每一步消除的順序，目標(biāo)是請(qǐng)盡可能多的消掉字符氧枣，返回最少的剩余字符數(shù)量
比如："aacca", 如果先消掉最左側(cè)的"aa"顶掉，那么將剩下"cca"，然后把"cc"消掉挑胸，剩下的"a"將無(wú)法再消除痒筒，返回1
但是如果先消掉中間的"cc"，那么將剩下"aaa"，最后都消掉就一個(gè)字符也不剩了簿透，返回0移袍，這才是最優(yōu)解。
再比如："baaccabb"老充，
如果先消除最左側(cè)的兩個(gè)a葡盗，剩下"bccabb"，如果再消除最左側(cè)的兩個(gè)c啡浊，剩下"babb"觅够，最后消除最右側(cè)的兩個(gè)b，剩下"ba"無(wú)法再消除巷嚣，返回2
而最優(yōu)策略是：
如果先消除中間的兩個(gè)c喘先，剩下"baaabb"，如果再消除中間的三個(gè)a廷粒，剩下"bbb"窘拯，最后消除三個(gè)b，不留下任何字符坝茎，返回0涤姊，這才是最優(yōu)解
給定一個(gè)數(shù)組arr，和一個(gè)正數(shù)M嗤放，返回在arr的子數(shù)組在長(zhǎng)度不超過(guò)M的情況下思喊，最大的累加和
哈夫曼樹(shù)的實(shí)現(xiàn)
47 動(dòng)態(tài)規(guī)劃猜法中和外部信息簡(jiǎn)化的相關(guān)問(wèn)題（下）、最大網(wǎng)絡(luò)流算法之Dinic算法
內(nèi)容：
進(jìn)一步解決帶有"外部信息簡(jiǎn)化"特征的動(dòng)態(tài)規(guī)劃
Dinic算法
題目：
有臺(tái)奇怪的打印機(jī)有以下兩個(gè)特殊要求：
打印機(jī)每次只能打印由同一個(gè)字符組成的序列次酌。
每次可以在任意起始和結(jié)束位置打印新字符搔涝，并且會(huì)覆蓋掉原來(lái)已有的字符。
給你一個(gè)字符串s和措，你的任務(wù)是計(jì)算這個(gè)打印機(jī)打印它需要的最少打印次數(shù)庄呈。
Leetcode題目：https://leetcode.com/problems/strange-printer/
整型數(shù)組arr長(zhǎng)度為n(3 <= n <= 10^4)，最初每個(gè)數(shù)字是<=200的正數(shù)且滿足如下條件：
- 0位置的要求：arr[0]<=arr[1]
- n-1位置的要求：arr[n-1]<=arr[n-2]
- 中間i位置的要求：arr[i]<=max(arr[i-1],arr[i+1])
但是在arr有些數(shù)字丟失了派阱，比如k位置的數(shù)字之前是正數(shù)诬留，丟失之后k位置的數(shù)字為0
請(qǐng)你根據(jù)上述條件，計(jì)算可能有多少種不同的arr可以滿足以上條件
比如 [6,0,9] 只有還原成 [6,9,9]滿足全部三個(gè)條件贫母，所以返回1文兑，即[6,9,9]達(dá)標(biāo)
Dinic算法詳解
測(cè)試鏈接：https://lightoj.com/problem/internet-bandwidth
