算法和數(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é)們的各種答疑問題
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最右的位置
局部最小值問題
定義何為局部最小值：
arr[0] < arr[1]，0位置是局部最?。?br>
arr[N-1] < arr[N-2]，N-1位置是局部最小；
arr[i-1] > arr[i] < arr[i+1]，i位置是局部最?。?br>
給定一個(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來
一個(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公式來估計(jì)時(shí)間復(fù)雜度
哈希表和有序表使用的code展示
04 歸并排序及其常見面試題
內(nèi)容：
歸并排序
題目：
歸并排序的遞歸和非遞歸實(shí)現(xiàn)
在一個(gè)數(shù)組中，一個(gè)數(shù)左邊比它小的數(shù)的總和，叫該數(shù)的小和
所有數(shù)的小和累加起來，叫數(shù)組小和
例子： [1,3,4,2,5]
1左邊比1小的數(shù)：沒有
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的后面沒有
2的后面沒有
所以總共有5個(gè)
05 歸并排序面試題(續(xù))、快速排序
內(nèi)容：
再來一個(gè)歸并排序面試題
荷蘭國旗問題
快速排序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/
荷蘭國旗問題的實(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)的距離一定不超過k
k相對(duì)于數(shù)組長度來說是比較小的。請(qǐng)選擇一個(gè)合適的排序策略，對(duì)這個(gè)數(shù)組進(jìn)行排序。
07 和堆有關(guān)的面試題、加強(qiáng)堆結(jié)構(gòu)
內(nèi)容：
線段最大重合問題
加強(qiáng)堆的實(shí)現(xiàn)
題目：
給定很多線段，每個(gè)線段都有兩個(gè)數(shù)[start, end]，
表示線段開始位置和結(jié)束位置，左右都是閉區(qū)間
規(guī)定：
1）線段的開始和結(jié)束位置一定都是整數(shù)值
2）線段重合區(qū)域的長度必須>=1
返回線段最多重合區(qū)域中，包含了幾條線段
加強(qiáng)堆的實(shí)現(xiàn)、注意點(diǎn)解析
做一個(gè)加強(qiáng)堆的題目，給定一個(gè)整型數(shù)組，int[] arr；和一個(gè)布爾類型數(shù)組，boolean[] op
兩個(gè)數(shù)組一定等長，假設(shè)長度為N，arr[i]表示客戶編號(hào)，op[i]表示客戶操作
arr= [3,3,1,2,1,2,5…
op = [T,T,T,T,F,T,F…
依次表示：
3用戶購買了一件商品
3用戶購買了一件商品
1用戶購買了一件商品
2用戶購買了一件商品
1用戶退貨了一件商品
2用戶購買了一件商品
5用戶退貨了一件商品…
一對(duì)arr[i]和op[i]就代表一個(gè)事件：
用戶號(hào)為arr[i]，op[i] == T就代表這個(gè)用戶購買了一件商品
op[i] == F就代表這個(gè)用戶退貨了一件商品
現(xiàn)在你作為電商平臺(tái)負(fù)責(zé)人，你想在每一個(gè)事件到來的時(shí)候，
都給購買次數(shù)最多的前K名用戶頒獎(jiǎng)。
所以每個(gè)事件發(fā)生后，你都需要一個(gè)得獎(jiǎng)名單（得獎(jiǎng)區(qū)）。
得獎(jiǎng)系統(tǒng)的規(guī)則：
1，如果某個(gè)用戶購買商品數(shù)為0，但是又發(fā)生了退貨事件，
則認(rèn)為該事件無效，得獎(jiǎng)名單和上一個(gè)事件發(fā)生后一致，例子中的5用戶
2，某用戶發(fā)生購買商品事件，購買商品數(shù)+1，發(fā)生退貨事件，購買商品數(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ū)，任何用戶只要購買數(shù)>0，
一定在這兩個(gè)區(qū)域中的一個(gè)
5，購買數(shù)最大的前K名用戶進(jìn)入得獎(jiǎng)區(qū)，
在最初時(shí)如果得獎(jiǎng)區(qū)沒有到達(dá)K個(gè)用戶，那么新來的用戶直接進(jìn)入得獎(jiǎng)區(qū)
6，如果購買數(shù)不足以進(jìn)入得獎(jiǎng)區(qū)的用戶，進(jìn)入候選區(qū)
7，如果候選區(qū)購買數(shù)最多的用戶，已經(jīng)足以進(jìn)入得獎(jiǎng)區(qū)，
該用戶就會(huì)替換得獎(jiǎng)區(qū)中購買數(shù)最少的用戶（大于才能替換），
如果得獎(jiǎng)區(qū)中購買數(shù)最少的用戶有多個(gè)，就替換最早進(jìn)入得獎(jiǎng)區(qū)的用戶
如果候選區(qū)中購買數(shù)最多的用戶有多個(gè)，機(jī)會(huì)會(huì)給最早進(jìn)入候選區(qū)的用戶
8，候選區(qū)和得獎(jiǎng)區(qū)是兩套時(shí)間，
因用戶只會(huì)在其中一個(gè)區(qū)域，所以只會(huì)有一個(gè)區(qū)域的時(shí)間，另一個(gè)沒有
從得獎(jiǎng)區(qū)出來進(jìn)入候選區(qū)的用戶，得獎(jiǎng)區(qū)時(shí)間刪除，
進(jìn)入候選區(qū)的時(shí)間就是當(dāng)前事件的時(shí)間（可以理解為arr[i]和op[i]中的i）
從候選區(qū)出來進(jìn)入得獎(jiǎng)區(qū)的用戶，候選區(qū)時(shí)間刪除，
進(jìn)入得獎(jiǎng)區(qū)的時(shí)間就是當(dāng)前事件的時(shí)間（可以理解為arr[i]和op[i]中的i）
9，如果某用戶購買數(shù)==0，不管在哪個(gè)區(qū)域都離開，區(qū)域時(shí)間刪除，
離開是指徹底離開，哪個(gè)區(qū)域也不會(huì)找到該用戶
如果下次該用戶又發(fā)生購買行為，產(chǎn)生>0的購買數(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 前綴樹、不基于比較的排序（計(jì)數(shù)排序、基數(shù)排序）、排序算法的穩(wěn)定性
內(nèi)容：
前綴樹
計(jì)數(shù)排序
基數(shù)排序
排序算法的穩(wěn)定性
題目：
前綴樹實(shí)現(xiàn)
計(jì)數(shù)排序
基數(shù)排序
09 排序算法大總結(jié)、鏈表及其相關(guān)面試題
內(nèi)容：
排序算法總結(jié)
排序算法常見的坑
工程上對(duì)排序的常見改進(jìn)
鏈表面試題的常見技巧
題目：
輸入鏈表頭節(jié)點(diǎn)，奇數(shù)長度返回中點(diǎn)，偶數(shù)長度返回上中點(diǎn)
輸入鏈表頭節(jié)點(diǎn)，奇數(shù)長度返回中點(diǎn)，偶數(shù)長度返回下中點(diǎn)
輸入鏈表頭節(jié)點(diǎn)，奇數(shù)長度返回中點(diǎn)前一個(gè)，偶數(shù)長度返回上中點(diǎn)前一個(gè)
輸入鏈表頭節(jié)點(diǎn)，奇數(shù)長度返回中點(diǎn)前一個(gè)，偶數(shù)長度返回下中點(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)類型組成的無環(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ù)）、二叉樹的常見遍歷
內(nèi)容：
單鏈表的相交節(jié)點(diǎn)系列問題
一種看似高效其實(shí)搞笑的節(jié)點(diǎn)刪除方式
二叉樹的中序、先序、后序遍歷
題目：
給定兩個(gè)可能有環(huán)也可能無環(huán)的單鏈表，頭節(jié)點(diǎn)head1和head2
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，如果兩個(gè)鏈表相交，請(qǐng)返回相交的第一個(gè)節(jié)點(diǎn)。如果不相交返回null
要求如果兩個(gè)鏈表長度之和為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)刪掉？
二叉樹先序、中序、后序的遞歸遍歷和遞歸序
二叉樹先序、中序、后序的非遞歸遍歷
11 二叉樹常見面試題和二叉樹的遞歸套路（上）
內(nèi)容：
通過題目來熟悉二叉樹的解題技巧
題目：
二叉樹的按層遍歷
二叉樹的序列化和反序列化
N叉樹如何通過二叉樹來序列化、并完成反序列化
Leetcode題目：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/
打印二叉樹的函數(shù)設(shè)計(jì)
求二叉樹的最大寬度
求二叉樹某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)
二叉樹結(jié)構(gòu)如下定義：
Class Node {
V value;
Node left;
Node right;
Node parent;
}
給你二叉樹中的某個(gè)節(jié)點(diǎn)，返回該節(jié)點(diǎn)的后繼節(jié)點(diǎn)
折紙問題
請(qǐng)把一段紙條豎著放在桌子上，然后從紙條的下邊向上方對(duì)折1次，壓出折痕后展開
此時(shí)折痕是凹下去的，即折痕突起的方向指向紙條的背面
如果從紙條的下邊向上方連續(xù)對(duì)折2次，壓出折痕后展開
此時(shí)有三條折痕，從上到下依次是下折痕、下折痕和上折痕。
給定一個(gè)輸入?yún)?shù)N，代表紙條都從下邊向上方連續(xù)對(duì)折N次
請(qǐng)從上到下打印所有折痕的方向。
N=1時(shí)，打印: down
N=2時(shí)，打印: down down up
12 二叉樹常見面試題和二叉樹的遞歸套路（中）
內(nèi)容：
通過題目來熟悉二叉樹的解題技巧
介紹二叉樹的遞歸套路
1）假設(shè)以X節(jié)點(diǎn)為頭，假設(shè)可以向X左樹和X右樹要任何信息
2）在上一步的假設(shè)下，討論以X為頭節(jié)點(diǎn)的樹，得到答案的可能性（最重要）
3）列出所有可能性后，確定到底需要向左樹和右樹要什么樣的信息
4）把左樹信息和右樹信息求全集，就是任何一棵子樹都需要返回的信息S
5）遞歸函數(shù)都返回S，每一棵子樹都這么要求
6）寫代碼，在代碼中考慮如何把左樹的信息和右樹信息整合出整棵樹的信息
題目：
判斷二叉樹是不是搜索二叉樹
判斷二叉樹是不是平衡二叉樹
判斷二叉樹是不是滿二叉樹
給定一棵二叉樹的頭節(jié)點(diǎn)head，返回這顆二叉樹中最大的二叉搜索子樹的大小
給定一棵二叉樹的頭節(jié)點(diǎn)head，任何兩個(gè)節(jié)點(diǎn)之間都存在距離，返回整棵二叉樹的最大距離
13 二叉樹常見面試題和二叉樹的遞歸套路（下）、貪心算法
內(nèi)容：
二叉樹遞歸套路繼續(xù)實(shí)踐
一道貪心算法從頭到尾的完整做法
解決貪心題目的重要技巧，即對(duì)數(shù)器來驗(yàn)證腦洞
再次強(qiáng)調(diào)對(duì)數(shù)器的重要性
題目：
判斷二叉樹是不是完全二叉樹（一般方法解決、遞歸套路解決）
給定一棵二叉樹的頭節(jié)點(diǎn)head，返回這顆二叉樹中最大的二叉搜索子樹的頭節(jié)點(diǎn)
給定一棵二叉樹的頭節(jié)點(diǎn)head，和另外兩個(gè)節(jié)點(diǎn)a和b，返回a和b的最低公共祖先
派對(duì)的最大快樂值
員工信息的定義如下:
class Employee {
public int happy; // 這名員工可以帶來的快樂值
List<Employee> subordinates; // 這名員工有哪些直接下級(jí)
}
公司的每個(gè)員工都符合 Employee 類的描述。整個(gè)公司的人員結(jié)構(gòu)可以看作是一棵標(biāo)準(zhǔn)的、 沒有環(huán)的多叉樹
樹的頭節(jié)點(diǎn)是公司唯一的老板，除老板之外的每個(gè)員工都有唯一的直接上級(jí)
葉節(jié)點(diǎn)是沒有任何下屬的基層員工(subordinates列表為空)，除基層員工外每個(gè)員工都有一個(gè)或多個(gè)直接下級(jí)
這個(gè)公司現(xiàn)在要辦party，你可以決定哪些員工來，哪些員工不來，規(guī)則：
1.如果某個(gè)員工來了，那么這個(gè)員工的所有直接下級(jí)都不能來
2.派對(duì)的整體快樂值是所有到場員工快樂值的累加
3.你的目標(biāo)是讓派對(duì)的整體快樂值盡量大
給定一棵多叉樹的頭節(jié)點(diǎn)boss，請(qǐng)返回派對(duì)的最大快樂值。
給定一個(gè)由字符串組成的數(shù)組strs，必須把所有的字符串拼接起來，返回所有可能的拼接結(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)和長度數(shù)值一樣的銅板
比如長度為20的金條，不管怎么切都要花費(fèi)20個(gè)銅板，一群人想整分整塊金條，怎么分最省銅板?
例如，給定數(shù)組{10,20,30}，代表一共三個(gè)人，整塊金條長度為60，金條要分成10，20，30三個(gè)部分。
如果先把長度60的金條分成10和50，花費(fèi)60；再把長度50的金條分成20和30，花費(fèi)50；一共花費(fèi)110銅板
但如果先把長度60的金條分成30和30，花費(fèi)60；再把長度30金條分成10和20，花費(fèi)30；一共花費(fèi)90銅板
?輸入一個(gè)數(shù)組，返回分割的最小代價(jià)
一些項(xiàng)目要占用一個(gè)會(huì)議室宣講，會(huì)議室不能同時(shí)容納兩個(gè)項(xiàng)目的宣講，給你每一個(gè)項(xiàng)目開始的時(shí)間和結(jié)束的時(shí)間
你來安排宣講的日程，要求會(huì)議室進(jìn)行的宣講的場次最多，返回最多的宣講場次
輸入正數(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)之后還能掙到的錢(利潤)
K表示你只能串行的最多做k個(gè)項(xiàng)目
M表示你初始的資金
說明：每做完一個(gè)項(xiàng)目，馬上獲得的收益，可以支持你去做下一個(gè)項(xiàng)目，不能并行的做項(xiàng)目。
輸出：最后獲得的最大錢數(shù)
并查集的實(shí)現(xiàn)
15 并查集相關(guān)的常見面試題
內(nèi)容：
通過解答實(shí)際出現(xiàn)的面試題來體會(huì)并查集的優(yōu)勢(shì)、熟悉并查集的使用
題目：
一群朋友中，有幾個(gè)不相交的朋友圈
Leetcode題目：https://leetcode.com/problems/friend-circles/
島問題（遞歸解法 + 并查集解法 + 并行解法）
給定一個(gè)二維數(shù)組matrix，里面的值不是1就是0，上、下、左、右相鄰的1認(rèn)為是一片島，返回matrix中島的數(shù)量
16 圖及其與圖相關(guān)的算法
內(nèi)容：
圖的表達(dá)方式
圖的常見描述
圖的寬度優(yōu)先遍歷
圖的深度優(yōu)先遍歷
圖的拓?fù)渑判?/p>
最小生成樹算法Kruskal
最小生成樹算法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é)一開始）
17 用加強(qiáng)堆更好的實(shí)現(xiàn)Dijkstra算法、常見的遞歸
內(nèi)容：
加強(qiáng)堆實(shí)現(xiàn)Dijkstra算法
遞歸的設(shè)計(jì)
常見的遞歸
題目：
打印n層漢諾塔從最左邊移動(dòng)到最右邊的全部過程（遞歸+非遞歸實(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)過來，解決動(dòng)態(tài)規(guī)劃的套路
常見的嘗試模型
設(shè)計(jì)嘗試過程的原則
本節(jié)是暴力遞歸到動(dòng)態(tài)規(guī)劃的總綱（很重要）
后續(xù)的課都是在講述這一系列的套路
題目：
假設(shè)有排成一行的N個(gè)位置記為1~N，N一定大于或等于2
開始時(shí)機(jī)器人在其中的M位置上(M一定是1~N中的一個(gè))
如果機(jī)器人來到1位置，那么下一步只能往右來到2位置；
如果機(jī)器人來到N位置，那么下一步只能往左來到N-1位置；
如果機(jī)器人來到中間位置，那么下一步可以往左走或者往右走；
規(guī)定機(jī)器人必須走K步，最終能來到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é)為總綱
背包問題
記憶化搜索的一個(gè)很重要的注意點(diǎn)
通過面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
題目：
背包問題
給定兩個(gè)長度都為N的數(shù)組weights和values，weights[i]和values[i]分別代表 i號(hào)物品的重量和價(jià)值
給定一個(gè)正數(shù)bag，表示一個(gè)載重bag的袋子，裝的物品不能超過這個(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è)字符剪開使用，目的是拼出str來
返回需要至少多少張貼紙可以完成這個(gè)任務(wù)
例子：str= "babac"，arr = {"ba","c","abcd"}
ba + ba + c 3 abcd + abcd 2 abcd+ba 2
所以返回2
給定兩個(gè)字符串str1和str2，
返回這兩個(gè)字符串的最長公共子序列長度
比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最長公共子序列是“123456”，所以返回長度6
20 暴力遞歸到動(dòng)態(tài)規(guī)劃（三）
內(nèi)容：
以18節(jié)為總綱
通過面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
題目：
給定一個(gè)字符串str，返回這個(gè)字符串的最長回文子序列長度
比如 ： str = “a12b3c43def2ghi1kpm”
最長回文子序列是“1234321”或者“123c321”，返回長度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è)所有人拿到咖啡之后立刻喝干凈，
返回從開始等到所有咖啡機(jī)變干凈的最短時(shí)間
三個(gè)參數(shù)：int[] arr、int N，int a、int b
21 暴力遞歸到動(dòng)態(tài)規(guī)劃（四）
內(nèi)容：
以18節(jié)為總綱
通過面試題進(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ù)且沒有重復(fù)。再給定一個(gè)正數(shù)aim。
每個(gè)值都認(rèn)為是一種面值，且認(rèn)為張數(shù)是無限的。
返回組成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)為值相同的貨幣沒有任何不同，
返回組成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只要離開NM的區(qū)域，就直接死亡
返回k步之后，Bob還在N*M的區(qū)域的概率
22 暴力遞歸到動(dòng)態(tài)規(guī)劃（五）
內(nèi)容：
以18節(jié)為總綱
通過面試題進(jìn)一步強(qiáng)化動(dòng)態(tài)規(guī)劃的解題套路
斜率優(yōu)化技巧
題目：
給定3個(gè)參數(shù)，N，M，K
怪獸有N滴血，等著英雄來砍自己
英雄每一次打擊，都會(huì)讓怪獸流失[0~M]的血量
到底流失多少？每一次在[0~M]上等概率的獲得一個(gè)值
求K次打擊之后，英雄把怪獸砍死的概率
arr是面值數(shù)組，其中的值都是正數(shù)且沒有重復(fù)。再給定一個(gè)正數(shù)aim。
每個(gè)值都認(rèn)為是一種面值，且認(rèn)為張數(shù)是無限的。
返回組成aim的最少貨幣數(shù)
給定一個(gè)正數(shù)n，求n的裂開方法數(shù)，
規(guī)定：后面的數(shù)不能比前面的數(shù)小
比如4的裂開方法有：
1+1+1+1、1+1+2、1+3、2+2、4
5種，所以返回5
23 暴力遞歸到動(dòng)態(tài)規(guī)劃（六）
內(nèi)容：
以18節(jié)為總綱
通過面試題進(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長度為偶數(shù)，兩個(gè)集合包含數(shù)的個(gè)數(shù)要一樣多
如果arr長度為奇數(shù)，兩個(gè)集合包含數(shù)的個(gè)數(shù)必須只差一個(gè)
請(qǐng)盡量讓兩個(gè)集合的累加和接近
返回最接近的情況下，較小集合的累加和
N皇后問題是指在N*N的棋盤上要擺N個(gè)皇后，
要求任何兩個(gè)皇后不同行、不同列， 也不在同一條斜線上
?給定一個(gè)整數(shù)n，返回n皇后的擺法有多少種。?n=1，返回1
n=2或3，2皇后和3皇后問題無論怎么擺都不行，返回0
n=8，返回92
24 窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)
內(nèi)容：
滑動(dòng)窗口
窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)
用題目來學(xué)習(xí)窗口內(nèi)最大值或最小值的更新結(jié)構(gòu)提供的便利性
題目：
窗口內(nèi)最大值或最小值更新結(jié)構(gòu)的實(shí)現(xiàn)
假設(shè)一個(gè)固定大小為W的窗口，依次劃過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)問題
動(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)棧的原理（無重復(fù)數(shù)+有重復(fù)數(shù)）
用題目來學(xué)習(xí)單調(diào)棧提供的便利性
題目：
單調(diào)棧實(shí)現(xiàn)（無重復(fù)數(shù)+有重復(fù)數(shù)）
給定一個(gè)只包含正數(shù)的數(shù)組arr，arr中任何一個(gè)子數(shù)組sub，
一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
那么所有子數(shù)組中，這個(gè)值最大是多少？
給定一個(gè)非負(fù)數(shù)組arr，代表直方圖，返回直方圖的最大長方形面積
給定一個(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ù)問題
一個(gè)人可以一次往上邁1個(gè)臺(tái)階，也可以邁2個(gè)臺(tái)階，返回邁上N級(jí)臺(tái)階的方法數(shù)
奶牛生小牛問題
第一年農(nóng)場有1只成熟的母牛A，往后的每年：
1）每一只成熟的母牛都會(huì)生一只母牛
2）每一只新出生的母牛都在出生的第三年成熟
3）每一只母牛永遠(yuǎn)不會(huì)死
返回N年后牛的數(shù)量
給定一個(gè)數(shù)N，想象只由0和1兩種字符，組成的所有長度為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)
給定兩棵二叉樹的頭節(jié)點(diǎn)head1和head2，返回head1中是否有某個(gè)子樹的結(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 在無序數(shù)組中找到第K小的數(shù)、蓄水池算法
內(nèi)容：
時(shí)間復(fù)雜度O(N)可以解決在無序數(shù)組中找到第K小的數(shù)，這個(gè)經(jīng)典的面試題
改寫快排的partition方法
bfprt算法
蓄水池算法
題目：
在無序數(shù)組中找到第K小的數(shù)（改寫快排+bfprt）
設(shè)計(jì)在無序數(shù)組中收集最大的前K個(gè)數(shù)字的算法（根據(jù)不同的三個(gè)時(shí)間復(fù)雜度，設(shè)計(jì)三個(gè)算法）
給定一個(gè)無序數(shù)組arr中，長度為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 二叉樹的Morris遍歷
內(nèi)容：
二叉樹之前的遍歷方式有空間浪費(fèi)的問題
Morris遍歷時(shí)間復(fù)雜度O(N)，額外空間復(fù)雜度O(1)，通過利用原樹中大量空閑指針的方式，達(dá)到節(jié)省空間的目的
假設(shè)來到當(dāng)前節(jié)點(diǎn)cur，開始時(shí)cur來到頭節(jié)點(diǎn)位置
1）如果cur沒有左孩子，cur向右移動(dòng)(cur = cur.right)
2）如果cur有左孩子，找到左子樹上最右的節(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)二叉樹的先序、中序、后序遍歷
題目：
Morris遍歷的實(shí)現(xiàn)
給定一棵二叉樹的頭節(jié)點(diǎn)head，求以head為頭的樹中，最小深度是多少？
31 線段樹
內(nèi)容：
線段樹是一種支持范圍整體修改和范圍整體查詢的數(shù)據(jù)結(jié)構(gòu)
線段樹解決的問題范疇：大范圍信息可以只由左、右兩側(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è)游戲的簡化版：
1）只會(huì)下落正方形積木
2）[a,b] -> 代表一個(gè)邊長為b的正方形積木，積木左邊緣沿著X = a這條線從上方掉落
3）認(rèn)為整個(gè)X軸都可能接住積木，也就是說簡化版游戲是沒有整體的左右邊界的
4）沒有整體的左右邊界，所以簡化版游戲不會(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）沒有線段樹那么強(qiáng)，但是非常容易改成一維、二維、三維的結(jié)構(gòu)
3）只支持單點(diǎn)更新
AC自動(dòng)機(jī)
解決在一個(gè)大字符串中，找到多個(gè)候選字符串的問題
1）把所有匹配串生成一棵前綴樹
2）前綴樹節(jié)點(diǎn)增加fail指針
3）fail指針的含義：如果必須以當(dāng)前字符結(jié)尾，當(dāng)前形成的路徑是str，剩下哪一個(gè)字符串的前綴和str的后綴
擁有最大的匹配長度。fail指針就指向那個(gè)字符串的最后一個(gè)字符所對(duì)應(yīng)的節(jié)點(diǎn)（迷不迷？聽講述?。?/p>
題目：
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)用
布隆過濾器
一致性哈希
題目：
原理講述為主，面試只會(huì)聊設(shè)計(jì)，所以本節(jié)無題目
34 資源限制類題目的解題套路
內(nèi)容：
布隆過濾器用于集合的建立與查詢，并可以節(jié)省大量空間
一致性哈希解決數(shù)據(jù)服務(wù)器的負(fù)載管理問題
利用并查集結(jié)構(gòu)做島問題的并行計(jì)算
哈希函數(shù)可以把數(shù)據(jù)按照種類均勻分流
位圖解決某一范圍上數(shù)字的出現(xiàn)情況，并可以節(jié)省大量空間
利用分段統(tǒng)計(jì)思想、并進(jìn)一步節(jié)省大量空間
利用堆、外排序來做多個(gè)處理單元的結(jié)果合并
題目：
32位無符號(hào)整數(shù)的范圍是0~4,294,967,295，
現(xiàn)在有一個(gè)正好包含40億個(gè)無符號(hào)整數(shù)的文件，
可以使用最多1GB的內(nèi)存，怎么找到出現(xiàn)次數(shù)最多的數(shù)？
32位無符號(hào)整數(shù)的范圍是0~4,294,967,295，現(xiàn)在有一個(gè)正好包含40億個(gè)無符號(hào)整數(shù)的文件，
所以在整個(gè)范圍中必然存在沒出現(xiàn)過的數(shù)，可以使用最多1GB的內(nèi)存，怎么找到所有未出現(xiàn)過的數(shù)？
進(jìn)階：內(nèi)存限制為 3KB，但是只用找到一個(gè)沒出現(xiàn)過的數(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位無符號(hào)整數(shù)的范圍是0~4294967295，現(xiàn)在有40億個(gè)無符號(hào)整數(shù)，可以使用最多1GB的內(nèi)存，找出所有出現(xiàn)了兩次的數(shù)
32位無符號(hào)整數(shù)的范圍是0~4294967295，現(xiàn)在有40億個(gè)無符號(hào)整數(shù)，可以使用最多3K的內(nèi)存，怎么找到這40億個(gè)整數(shù)的中位數(shù)？
32位無符號(hào)整數(shù)的范圍是0~4294967295，有一個(gè)10G大小的文件，每一行都裝著這種類型的數(shù)字，
整個(gè)文件是無序的，給你5G的內(nèi)存空間，請(qǐng)你輸出一個(gè)10G大小的文件，就是原文件所有數(shù)字排序的結(jié)果
35 有序表（上）
內(nèi)容：
平衡搜索二叉樹
左旋
右旋
AVL樹的節(jié)點(diǎn)違規(guī)4種類型（LL，LR，RL，RR）
題目：
AVL樹的實(shí)現(xiàn)
36 有序表（中）
內(nèi)容：
size-balanced-tree詳解
skiplist詳解
聊聊紅黑樹
題目：
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)窗口最右位置，一開始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等語言，1~4秒處理的指令條數(shù)為10的8次方
3）這里就有大量的分析提示了
題目：
小虎去買蘋果，商店只提供兩種類型的塑料袋，每種類型都有任意數(shù)量
1）能裝下6個(gè)蘋果的袋子
2）能裝下8個(gè)蘋果的袋子
小虎可以自由使用兩種袋子來裝蘋果，但是小虎有強(qiáng)迫癥，他要求自己使用的袋子數(shù)量必須最少，
且使用的每個(gè)袋子必須裝滿，給定一個(gè)正整數(shù)N，返回至少使用多少袋子。如果N無法讓使用的每個(gè)袋子必須裝滿，返回-1
給定一個(gè)正整數(shù)N，表示有N份青草統(tǒng)一堆放在倉庫里，有一只牛和一只羊，牛先吃，羊后吃，它倆輪流吃草
不管是牛還是羊，每一輪能吃的草量必須是：1，4，16，64…(4的某次方)
誰最先把草吃完，誰獲勝，假設(shè)牛和羊都絕頂聰明，都想贏，都會(huì)做出理性的決定。根據(jù)唯一的參數(shù)N，返回誰會(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)怪獸要求的錢
開始時(shí)你的能力是0，你的目標(biāo)是從0號(hào)怪獸開始，通過所有的怪獸。
如果你當(dāng)前的能力，小于i號(hào)怪獸的能力，你必須付出p[i]的錢，賄賂這個(gè)怪獸，然后怪獸就會(huì)加入你
他的能力直接累加到你的能力上；如果你當(dāng)前的能力，大于等于i號(hào)怪獸的能力
你可以選擇直接通過，你的能力并不會(huì)下降，你也可以選擇賄賂這個(gè)怪獸，然后怪獸就會(huì)加入你
他的能力直接累加到你的能力上
返回通過所有的怪獸，需要花的最小錢數(shù)
（課上會(huì)給出不同的數(shù)據(jù)量描述）
39 根據(jù)數(shù)據(jù)量猜解法（續(xù)）、分治技巧、卡特蘭數(shù)
內(nèi)容：
繼續(xù)熟悉根據(jù)數(shù)據(jù)量猜解法
講解分治法
講解卡特蘭數(shù)（課上證明的時(shí)候有小錯(cuò)，在40節(jié)開始處修正了）
題目：
給定一個(gè)非負(fù)數(shù)組arr，和一個(gè)正數(shù)m，返回arr的所有子序列中累加和%m之后的最大值
牛牛家里一共有n袋零食, 第i袋零食體積為v[i]，背包容量為w，牛牛想知道在總體積不超過背包容量的情況下,
一共有多少種零食放法，體積為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è)二叉樹節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)彼此之間無任何差別，返回由N個(gè)二叉樹節(jié)點(diǎn)，組成的不同結(jié)構(gòu)數(shù)量是多少？
題目補(bǔ)充： arr中的值可能為正，可能為負(fù)，可能為0，自由選擇arr中的數(shù)字，能不能累加得到sum（多種做法）
40 子數(shù)組達(dá)到規(guī)定累加和的最大長度系列問題、矩陣處理技巧題
內(nèi)容：
修正了39節(jié)卡特蘭數(shù)講解時(shí)的一個(gè)小錯(cuò)誤
熟悉子數(shù)組達(dá)到規(guī)定累加和的三個(gè)模型（正、有正有負(fù)有0、累加和<=K）
矩陣處理技巧的宏觀調(diào)度coding技巧
題目：
給定一個(gè)正整數(shù)組成的無序數(shù)組arr，給定一個(gè)正整數(shù)值K，找到arr的所有子數(shù)組里，哪個(gè)子數(shù)組的累加和等于K
并且是長度最大的，返回其長度
給定一個(gè)整數(shù)組成的無序數(shù)組arr，值可能正、可能負(fù)、可能0，給定一個(gè)整數(shù)值K
找到arr的所有子數(shù)組里，哪個(gè)子數(shù)組的累加和等于K，并且是長度最大的，返回其長度
給定一個(gè)整數(shù)組成的無序數(shù)組arr，值可能正、可能負(fù)、可能0，給定一個(gè)整數(shù)值K
找到arr的所有子數(shù)組里，哪個(gè)子數(shù)組的累加和<=K，并且是長度最大的，返回其長度
給定一個(gè)數(shù)組arr，給定一個(gè)值v，求子數(shù)組平均值小于等于v的最長子數(shù)組長度
給定一個(gè)正方形矩陣matrix，原地調(diào)整成順時(shí)針90度轉(zhuǎn)動(dòng)的樣子
給定一個(gè)正方形或者長方形矩陣matrix，實(shí)現(xiàn)轉(zhuǎn)圈打印
給定一個(gè)正方形或者長方形矩陣matrix，實(shí)現(xiàn)zigzag打印
轉(zhuǎn)圈打印星號(hào)*問題
41 四邊形不等式技巧（上）
內(nèi)容：
區(qū)間劃分問題中的劃分點(diǎn)不回退現(xiàn)象
四邊形不等式技巧特征
1，兩個(gè)可變參數(shù)的區(qū)間劃分問題
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，長度為N，
那么有N-1種方案可以把a(bǔ)rr切成左右兩部分
每一種方案都有，min{左部分累加和，右部分累加和}
求這么多方案中，min{左部分累加和，右部分累加和}的最大值是多少？
整個(gè)過程要求時(shí)間復(fù)雜度O(N)
把題目一中提到的，min{左部分累加和，右部分累加和}，定義為S(N-1)，也就是說：
S(N-1)：在arr[0…N-1]范圍上，做最優(yōu)劃分所得到的min{左部分累加和，右部分累加和}的最大值
現(xiàn)在要求返回一個(gè)長度為N的s數(shù)組，
s[i] =在arr[0…i]范圍上，做最優(yōu)劃分所得到的min{左部分累加和，右部分累加和}的最大值
得到整個(gè)s數(shù)組的過程，做到時(shí)間復(fù)雜度O(N)
擺放著n堆石子?，F(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層開始一直試到第10層
在最差的情況下，即第10層是不會(huì)摔壞的最高層，最少也要扔10次
N=3，K=2
返回2
先在2層扔1棵棋子，如果碎了試第1層，如果沒碎試第3層
N=105，K=2
返回14
第一個(gè)棋子先在14層扔，碎了則用僅存的一個(gè)棋子試1~13
若沒碎，第一個(gè)棋子繼續(xù)在27層扔，碎了則用僅存的一個(gè)棋子試15~26
若沒碎，第一個(gè)棋子繼續(xù)在39層扔，碎了則用僅存的一個(gè)棋子試28~38
若沒碎，第一個(gè)棋子繼續(xù)在50層扔，碎了則用僅存的一個(gè)棋子試40~49
若沒碎，第一個(gè)棋子繼續(xù)在60層扔，碎了則用僅存的一個(gè)棋子試51~59
若沒碎，第一個(gè)棋子繼續(xù)在69層扔，碎了則用僅存的一個(gè)棋子試61~68
若沒碎，第一個(gè)棋子繼續(xù)在77層扔，碎了則用僅存的一個(gè)棋子試70~76
若沒碎，第一個(gè)棋子繼續(xù)在84層扔，碎了則用僅存的一個(gè)棋子試78~83
若沒碎，第一個(gè)棋子繼續(xù)在90層扔，碎了則用僅存的一個(gè)棋子試85~89
若沒碎，第一個(gè)棋子繼續(xù)在95層扔，碎了則用僅存的一個(gè)棋子試91~94
若沒碎，第一個(gè)棋子繼續(xù)在99層扔，碎了則用僅存的一個(gè)棋子試96~98
若沒碎，第一個(gè)棋子繼續(xù)在102層扔，碎了則用僅存的一個(gè)棋子試100、101
若沒碎，第一個(gè)棋子繼續(xù)在104層扔，碎了則用僅存的一個(gè)棋子試103
若沒碎，第一個(gè)棋子繼續(xù)在105層扔，若到這一步還沒碎，那么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á)到或超過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問題
有N個(gè)城市，任何兩個(gè)城市之間的都有距離，任何一座城市到自己的距離都為0
所有點(diǎn)到點(diǎn)的距離都存在一個(gè)N*N的二維數(shù)組matrix里，也就是整張圖由鄰接矩陣表示
現(xiàn)要求一旅行商從k城市出發(fā)必須經(jīng)過每一個(gè)城市且只在一個(gè)城市逗留一次，最后回到出發(fā)的k城
參數(shù)給定一個(gè)matrix，給定k。返回總距離最短的路的距離
鋪磚問題（最優(yōu)解其實(shí)是輪廓線dp，但是這個(gè)解法對(duì)大廠刷題來說比較難，掌握課上的解法即可）
你有無限的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)容：
通過題目進(jìn)一步熟悉DC3算法
通過DC3算法得到height數(shù)組
題目：
給定兩個(gè)字符串str1和str2，想把str2整體插入到str1中的某個(gè)位置，形成最大的字典序，返回字典序最大的結(jié)果
給兩個(gè)長度分別為M和N的整型數(shù)組nums1和nums2，其中每個(gè)值都不大于9，再給定一個(gè)正數(shù)K。 你可以在nums1和nums2中挑選數(shù)字，要求一共挑選K個(gè)，并且要從左到右挑。返回所有可能的結(jié)果中，代表最大數(shù)字的結(jié)果
最長公共子串問題是面試常見題目之一，假設(shè)str1長度N，str2長度M
一般在面試場上回答出O(NM)的解法已經(jīng)是比較優(yōu)秀了
因?yàn)榈玫絆(NM)的解法，就已經(jīng)需要用到動(dòng)態(tài)規(guī)劃了
但其實(shí)這個(gè)問題的最優(yōu)解是O(N+M)，需要用到后綴數(shù)組+height數(shù)組
課上將對(duì)本題解法代碼進(jìn)行詳解
46 動(dòng)態(tài)規(guī)劃猜法中和外部信息簡化的相關(guān)問題（上）、哈夫曼樹
內(nèi)容：
以18節(jié)做總綱
有些動(dòng)態(tài)規(guī)劃面試題，需要很好的設(shè)計(jì)參數(shù)，這種設(shè)計(jì)方式都有"外部信息簡化"的特征
哈夫曼樹
題目：
有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相鄰的、沒有被戳爆的！兩個(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)過若干輪操作去去掉盒子
直到所有的盒子都去掉為止，每一輪你可以移除具有相同顏色的連續(xù)k個(gè)盒子（k >= 1）
這樣一輪之后你將得到 k * k 個(gè)積分，當(dāng)你將所有盒子都去掉之后，求你能獲得的最大積分和
Leetcode題目：https://leetcode.com/problems/remove-boxes/
如果一個(gè)字符相鄰的位置沒有相同字符，那么這個(gè)位置的字符出現(xiàn)不能被消掉
比如:"ab"，其中a和b都不能被消掉
如果一個(gè)字符相鄰的位置有相同字符，就可以一起消掉
比如:"abbbc"，中間一串的b是可以被消掉的，消除之后剩下"ac"
某些字符如果消掉了，剩下的字符認(rèn)為重新靠在一起
給定一個(gè)字符串，你可以決定每一步消除的順序，目標(biāo)是請(qǐng)盡可能多的消掉字符，返回最少的剩余字符數(shù)量
比如："aacca", 如果先消掉最左側(cè)的"aa"，那么將剩下"cca"，然后把"cc"消掉，剩下的"a"將無法再消除，返回1
但是如果先消掉中間的"cc"，那么將剩下"aaa"，最后都消掉就一個(gè)字符也不剩了，返回0，這才是最優(yōu)解。
再比如："baaccabb"，
如果先消除最左側(cè)的兩個(gè)a，剩下"bccabb"，如果再消除最左側(cè)的兩個(gè)c，剩下"babb"，最后消除最右側(cè)的兩個(gè)b，剩下"ba"無法再消除，返回2
而最優(yōu)策略是：
如果先消除中間的兩個(gè)c，剩下"baaabb"，如果再消除中間的三個(gè)a，剩下"bbb"，最后消除三個(gè)b，不留下任何字符，返回0，這才是最優(yōu)解
給定一個(gè)數(shù)組arr，和一個(gè)正數(shù)M，返回在arr的子數(shù)組在長度不超過M的情況下，最大的累加和
哈夫曼樹的實(shí)現(xiàn)
47 動(dòng)態(tài)規(guī)劃猜法中和外部信息簡化的相關(guān)問題（下）、最大網(wǎng)絡(luò)流算法之Dinic算法
內(nèi)容：
進(jìn)一步解決帶有"外部信息簡化"特征的動(dòng)態(tài)規(guī)劃
Dinic算法
題目：
有臺(tái)奇怪的打印機(jī)有以下兩個(gè)特殊要求：
打印機(jī)每次只能打印由同一個(gè)字符組成的序列。
每次可以在任意起始和結(jié)束位置打印新字符，并且會(huì)覆蓋掉原來已有的字符。
給你一個(gè)字符串s，你的任務(wù)是計(jì)算這個(gè)打印機(jī)打印它需要的最少打印次數(shù)。
Leetcode題目：https://leetcode.com/problems/strange-printer/
整型數(shù)組arr長度為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算法詳解
測試鏈接：https://lightoj.com/problem/internet-bandwidth
