數據結構
線性表包括順序表和鏈表，python的list是順序表，鏈表一般在動態語言中不會使用。不過鏈表還是會出現在各種算法題中。
鏈表 link list
- 單鏈表
- 逆轉鏈表： leetcode 206
- 雙鏈表
- 循環單鏈表
字符串 string
有一個重要的點就是字符串的匹配問題，其中比較重要的是無回溯匹配算法(KMP算法)，算法比較復雜，重要的思想在于匹配過程中不回溯。實際復雜度是O(m+n), m和n分別是匹配模式串和目標串，一般m<<n。
- 通配符 *和?
- * 匹配任意一個字符串
- ？匹配任意一個字符
- 正則表達式：內容很多，這里就不講了
- 原始字符串：在字符串前面加r前綴,\不作為轉義符
棧 stack
隊列 queue
python3有內置的實現模塊
二叉樹
基本概念：路徑，長度，層數。都比較好理解。
root的層數為0。
二叉樹的性質：
- 性質6.1：在非空二叉樹第i層中最多有2^i個節點
- 性質6.2：高度為h的二叉樹最多有2^(h+1)-1個節點
- 性質6.2：對于任何非空二叉樹，如果其葉節點的個數為n0,度數為2的節點個數為n2,那么n0=n2+1
滿二叉樹：所有分支節點的度數都是2 - 性質6.4: 滿二叉樹的葉節點比分支節點多一個
擴充二叉樹：把一個二叉樹的所有節點變成度數為2的節點（就是這棵樹長了一圈葉子），舊節點叫內部節點，新節點叫外部節點。 - 性質6.5：擴充二叉樹的外部路徑長度叫E, 內部路徑長度叫I, n是內部節點數量， E=I+2*n
完全二叉樹：0-(h-1)層的節點都滿，并且最后一層的節點都在左邊。 - 性質6.6：完全二叉樹節點數為n，則高度h=floor(log2n)
- 性質6.7：完全二叉樹節點數為n, 并從0開始編號（按層次按左右）
- root的編號是0
- i的父節點是floor((i-1)/2)
- if 2i+1<n, 則其left child: 2i+1 else 無left child
- if 2i+2<n, 則其right chiild: 2i +2 else 無right child
完全二叉樹到線性結構有自然的雙向映射
- 深度優先遍歷 depth first traversal, depth first search, DFS
- 先根序遍歷DLR
- 中根序遍歷LDR
- 后根序遍歷LRD
- 寬度(廣度)優先遍歷, Breadth First Search, BFS：實現BFS一般要用到一個隊列
先根序DFT
def preorder(t, proc):if not t:return Noneproc(t.val)preorder(t.left)preorder(t.right)廣度優先遍歷 BFS
def levelorder(t, proc_):q = Queue()q.put(t)while not q.empty():n = q.get()if not n:continueq.put(n.left)q.put(n.right)proc_(n.val)- 合并兩個二叉樹：leetcode 617
堆：一個完全二叉樹，并且，任意一個節點存放的數據先于其子節點的數據
小頂堆 大頂堆
堆和完全二叉樹
- 堆+一個元素 ->完全二叉樹
- 堆 去掉root 生成兩個堆
- 上面得到的兩個堆+新的root -> 完全二叉樹
- 堆去掉最后一個節點，還是堆
堆可以用來構建優先隊列(py3已經實現了)
由堆實現的優先隊列，創建的時間復雜度是O(n)，插入和彈出是O(logn)
堆還可以用來排序
heap sort python實現
def heap_sort(nums_):def siftdown(nums_i, e, begin, end):i = beginj = begin*2+1while j < end:if j + 1 < end and nums_i[j+1] < nums_i[j]:j += 1if e < nums_i[j]:breaknums_i[i] = nums_i[j]i = jj = 2*j+1nums_i[i] = eend = len(nums_)for k in range(end//2, -1, -1):siftdown(nums_, nums_[k], k, end)for k in range((end-1), 0, -1):e = nums_[k]nums_[k] = nums_[0]siftdown(nums_, e, 0, k)return nums_[::-1]heap sort c++實現 序列是數組
c++堆排序
排序算法 sort algorithm
- 內排序：在內存上排序
- 外排序
歸并是外排序的基礎
原地排序算法：空間復雜度為O(1)
穩定性
就是原序列里有一些Key一樣的元素，排序之后能否保持不改變這部分序列的相對順序。
比如key-value pair，按照key 排序：
(0, 100), (1, 50), (1, 60), (1, 45), (-2, 80)
希望排序之后(1, 50), (1, 60), (1, 45)這三個元素的相對位置不變。
適應性
如果一個排序算法對接近有序的序列工作的更快，就稱這種算法具有適應性。
也就是說，如果本來已經快排序完了，還差一點，那么算法是能夠利用這種優勢迅速完成剩下的工作，還是推倒重來，按照原本既定的方法重新排序。
9.2 簡單排序算法
- 插入排序：已經有一個排序完的序列，從剩余序列中順序拿出一個跟前面的序列挨個比較，尋找合適的位置插入。用于鏈表不錯
- 選擇排序：
- 簡單選擇排序：每次找到最小的元素放在最前面
- 直接選擇排序算法：把找到的最小元素和已排序序列后面的元素交換位置。是一個非常爛的算法。別用。
- 堆排序：堆排序的問題是不穩定
- 交換排序
- 冒泡排序
- 交錯排序：從左向右掃描一遍，從右向左再掃描一遍
9.3快速排序
)
