目錄
（1）為什麼學習算法
（2）時間複雜度
（3）數組、鍊表
（4）堆棧、(優先級)隊列
（5）map、set
（6）樹、圖
（7）遞歸、分治、回溯
（8）貪心算法
（9）BFS、DFS
（10）剪枝
（11）二分查找
（12）Trie樹
（13）位運算
（14）動態規劃
（15）併查集
（16）LRU Cache
（17）布隆過濾器
遞歸
定義：通過函數體來進行的循環，沒有終止條件的遞歸是死遞歸。
舉例：從前有座山，山裡有座廟，廟裡有個老和尚講故事。講的是從前有座山，山裡有座廟.....(階乘、Fibonacci數列)。
分治
定義：map reduce的思想，把大的問題分解(Divide)成一個個小問題。把小問題的解(Conquer)一個個的合併(Combine)起來，分治是藉助遞歸去解決的。
舉例：大文件在有限的資源下進行操作、二分法、快速排序、合併排序。
回溯
定義：回溯算法實際是一個類似枚舉的搜索過程，在搜索中發現原先選擇並不優或達不到目標，就返回一步嘗試別的選擇。走不通(剪枝)就退回再走的技術稱為回溯法。藉助遞歸去解決，類似DFS。
面試題
1、計算x^n，pow(x，n)
思路：直接調用庫函數求解，O(1)
暴力求解，O(n)
分治的思想，藉助遞歸實現。x^n->x^n/2->x^n/4...->x^1，O(log n)
使用位運算進行計算，O(n)
URL:https://leetcode.com/problems/powx-n/description/
2、求一個數組中出現次數最多的數，要求count(x) > n/2
思路：暴力求解，O(n^2)，外層循環進行枚舉，內存循環進行統計。每次的最後和n/2比較
引入map的方式，把數進行計數。O(n)，會引入一個map的開銷
進行排序後，相同的數字就會在一塊了。因為是個數超過一半，那麼數組排序後該元素必定佔據數組的中間位置，O(log n)
分治思想，第一次先把數組分解為2個，看left和right哪個元素的count(x)最大就返回哪個，然後繼續拆分直到只剩下一個元素了
URL:https://leetcode.com/problems/majority-element/
貪心算法
定義：貪心算法又被稱為貪婪算法。在對問題求解時，總是做出在當前看來是最好的選擇。
適用場景：問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。
貪心算法對每個子問題的解決方案都做出選擇，不能進行回退。動態規劃會保存以前的運算結果，並根據以前結果對當前進行選擇，有回退功能。
面試題
1、買賣股票的最佳時機
思路：深度遍歷優先，每天是買還是賣。O(2^n)
貪心算法，每天都進行買賣(假設無手續費)，把利益拿到手裡。O(n)
動態規劃，O(n)
URL:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
BFS
定義：廣度優先搜索適合用在樹(圖/狀態集)中尋找特定節點。一層層遞進的方式地毯式搜索，在搜索圖和狀態集的時候需要引入集合進行判重。
類比：BFS就好像是我們選擇領域的時候先從廣度進行了解後，在選擇一個領域去做。
DFS
定義：廣度優先搜索同樣也適合用在樹(圖/狀態集)中尋找特定節點。每一條路走到底，再往回走看是否有其它的路徑，再走到底往回走是否有路。
類比：DFS就是我們選擇好一個領域後，把它徹底研究透徹在研究其它領域。
面試題
1、二叉樹按照層進行遍歷
思路：使用廣度優先搜索，每一層掃描完放到一起，O(n)
使用深度優先搜索，每一次記錄下深度，按照深度歸納每層的數據，O(n)
URL:https://leetcode.com/problems/binary-tree-level-order-traversal/
2、在二叉樹中找出最大深度和最小深度
思路：DFS，每一層都記錄深度，判定到有葉子結點則更新下max和min的值，直到遍歷完
BFS，一層層的掃，判定是不是葉子結點，第一個到達葉子結點的是最小深度。最後一個到達的葉子節點是最大深度
URL:https://leetcode.com/problems/maximum-depth-of-binary-tree/
https://leetcode.com/problems/minimum-depth-of-binary-tree/
3、給出n對括號，生成有效的括號組合
思路：數學歸納法，推出n有多少種情況
深度優先搜索，給出n對括號，字符串長度固是定的2n。相當於給2n的格子，每個格子有左括號、右括號的選擇。總共有2^2n種可能，最後進行過濾
基於DFS的基礎上進行優化，不合法的直接不進行遞歸，比如直接使用右括號開頭的，把左右括號使用掉的個數記錄下來，最終只能使用到n，程序停止
URL:https://leetcode.com/problems/generate-parentheses/
剪枝
定義：在對樹、圖、狀態集等等的搜索中經常使用到的一種過濾，可以很好的降低搜索的複雜性。
類比：圍棋比象棋更加的複雜，圍棋的空間狀態比較多，可能性也很多。alpha go就是複雜的搜索樹加上剪枝的方式(過濾掉不必要的搜索高度)，快速把對方戰勝。
面試題
1、N皇后問題
思路：暴力破解的做法，把二維的平面每一個格子進行掃一遍看看能不能放Q
使用深度搜索優先，每一層判定能不能放Q
接著數組把行、列、撇、捺的位置都表示出來，然後利用剪枝進行過濾。只要在橫豎撇捺位置都沒有Q覆蓋的地方才能放新的Q
URL:https://leetcode.com/problems/n-queens/
https://leetcode.com/problems/n-queens-ii/
2、數獨問題
思路：用計算機去實現類似人的思考方式，不斷去填充，有衝突進行回溯。田數字1-9，並且判定在橫豎3x3裡面沒有重複才能放置。利用策略儘可能少的去搜索判定，從選擇少的地方進行枚舉更容易確定下來
URL:https://leetcode.com/problems/sudoku-solver/
https://leetcode.com/problems/valid-sudoku/
二分查找
符合以下三個要求的適合使用二分查找
1、Sorted（單調遞增或遞減）
2、Bounded（存在上下界）
3、Accessible by index（能夠通過索引訪問）
面試題
1、求一個數的平方根
思路：二分法，不斷的去二分枚舉然後和原值比較
牛頓迭代法
URL:https://leetcode.com/problems/sqrtx/
https://leetcode.com/problems/valid-perfect-square/
Trie樹
定義：Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷。
應用：用於統計和排序大量的字符串(不限於字符串)，還被搜尋引擎用於文本詞頻統計。
優點：最大限度減少無謂的字符串比較，查詢效率比哈希表高。
面試題
1、實現一個字典樹
思路：需要實現插入、查找、查找前綴。我們可以把單詞排序好然後去字典樹中找。
URL:https://leetcode.com/problems/implement-trie-prefix-tree/
2、二維網格中單詞搜索問題
思路：使用深度搜索優選遍歷進行搜索，看看能不能找到
把要搜索的單詞放到字典樹中，然後去網格中枚舉看是不是能走到字典樹的葉子節點
URL:https://leetcode-cn.com/problems/word-search-ii/
未完待續...