打牢演算法基礎，從動手出發！
- 2019 年 11 月 15 日
- 筆記
0.導語
大家好，我是光城。演算法在電腦領域的重要性，就不用我多說了，每個人都想要學演算法，打牢演算法基礎，可是不知道如何做，今天我來推薦一波學習思路。
最近我也在打牢演算法，於是買了波波老師的慕課網課程《玩轉兒數據結構》，由於官方為JAVA版本，但是本人用的C++，因此我將本課程的演算法用C++實現了一遍，裡面採用了操作符重載，介面使用，繼承，組合等面向對象的思想，把我這個倉庫學完，C++基礎部分也就會了。
筆記倉庫地址：
https://github.com/Light-City/algPratice
後面將更新波波老師的其他課程學習筆記。歡迎大家star與fork!
當前倉庫共有2萬多行程式碼，59個文件，全部自己寫的程式碼，學習演算法沒有途徑，只待你動手實踐！
1.玩轉數據結構 從入門到進階C++版
- 動態數組 學習要點：動態數組的增刪改查、時間複雜度、防止複雜度震蕩策略。
- 動態數組實現
- 動態數組測試
- 棧和隊列
- 隊列的公共介面
- 基於底層為動態數組的隊列實現
- 基於底層為動態數組的循環隊實現
- 基於底層為鏈表的隊列實現
- 隊列的測試
- 棧的公共介面
- 基於底層為動態數組的棧實現
- 基於底層為鏈表的棧實現
- 棧的測試
- LeetCode20題
- 棧 學習要點：使用組合方案來完成棧的底層數據結構為數組，定義棧的入棧與出隊策略。
- 隊列 學習要點：多種底層實現的效率對比，介面的定義，定義隊列的入隊與出隊策略。
- 鏈表 學習要點：鏈表內部節點結構定義、dummyHead使用、時間複雜度分析、鏈表棧與鏈表隊列實現。z掌握遞歸的宏觀與微觀、如何對遞歸進行測試。
- 鏈表的實現
- 鏈表棧實現
- 鏈表隊列實現
- 鏈表、鏈表棧、鏈表隊列實現
- LeetCode203題不帶與帶dummyHead兩種實現
- LeetCode203題遞歸實現
- 求和遞歸實現
- 二分搜索樹 學習要點：掌握二分搜索樹的結構、四種遍歷方式的遞歸與非遞歸，bst樹中最大與最小節點，刪除節點原則，拓展二分查找法與基於floo、ceil的實現，當bst樹退化為鏈表的時候對應的順序查找表實現，順序查找表與二分搜索樹的效率對比。
- 補充
- 順序查找表實現
- 二分查找法實現
- 基於floor與ceil的二分查找法實現
- 二分搜索樹實現
- 二分搜索樹測試
- 集合與映射
- 映射介面
- 基於底層為二分搜索樹的映射
- 基於底層為鏈表的映射
- LeetCode804問題
- 拓展
- 基於底層為順序查找表的映射
- 集合介面
- 基於底層為二分搜索樹的集合
- 基於底層為鏈表的集合
- LeetCode804問題
- 拓展
- 基於底層為順序查找表的集合
- 集合 學習要點：集合介面定義、二分搜索樹與鏈表集合的效率對比。
- 映射 學習要點：映射介面定義、二分搜索樹與鏈表映射的效率對比。學會什麼時候用映射，什麼時候用集合。
- 優先隊列和堆 學習要點：堆的sift up與sift down、heapify、堆與優先隊列的關係、如何使用STL的大頂堆與小頂堆、如何使用自己的優先隊列解題。
- 基於動態數組的大頂堆實現
- 基於底層為大頂堆的優先隊列實現
- 大頂堆與優先隊列測試
- 使用C++ STL的優先隊列解LeetCode347題
- 使用我們自己的優先隊列解LeetCode347題
- 線段樹 學習要點：掌握線段樹的概念與應用，經典應用區間更新查詢等，學會使用動態數組作為線段樹的底層數據結構，掌握開闢多大空間存儲。掌握其不是完全二叉樹也不是滿二叉樹，但是平衡二叉樹,依然可以用數組表示,看做滿二叉樹,後面不存在的節點在數組中用空來表示即可。
- 基於動態數組的線段樹實現
- 線段樹測試
- LeetCode303題
- LeetCode307題
- 字典樹 學習要點：掌握字典樹節點定義，學會使用自己的字典樹解題。
- 字典樹的實現
- LeetCode211題
- LeetCode677題
- 並查集 學習要點：quickfind、基於樹高度優化的並查集、基於樹的大小(只是當前父親節點+孩子節點總數)優化、基於rank(樹的深度)的優化、路徑壓縮1、路徑壓縮2。
- 基於動態數組的並查集六種實現
- 並查集測試
- 平衡樹AVL 學習要點：左旋轉、右旋轉、平衡因子維護等。
- AVL實現
- AVL測試
- 紅黑樹 學習要點：紅黑樹節點顏色標記、左旋轉、右旋轉、顏色翻轉、插入節點顏色調整。
- 紅黑樹實現
- 紅黑樹測試
- 哈希表 學習要點：哈希表動態擴容、哈希函數定義等。
- 簡單的哈希表
- 簡單的哈希表測試
- 素數哈希函數的哈希表
- 素數哈希函數的哈希表測試
