資源｜從演算法到數據結構，百道面試問題實現答案集合

選自GitHub

作者：Sherali Obidov

機器之心編譯

參與：李亞洲、微胖、蔣思源

該資源是演算法、數據結構以及面試問題解決方案的集合，裡面的 repository 包含了我對常見演算法問題的解答以及數據結構的實現（用 Java）。該資源集合處於持續更新中。

項目地址：https://github.com/sherxon/AlgoDS

目前為止，該資源集合提供了演算法、數據結構以及 200 道面試題的答案。

問題

問題被分成了三個等級：

• 簡單問題：http://suo.im/262F7q

• 中等問題：http://suo.im/11JBcd

• 困難問題：http://suo.im/3pTT1R

問題方向

針對以下不同面試問題，各自的鏈接中都給出了解決方案。

陣列（Arrays）

1. 旋轉陣列（Rotate Array）：http://suo.im/2Z3CMz

2. Contains Duplicate：http://suo.im/2E9xnW

3. 發現峰值元素：http://suo.im/4gQO3k

4. 最大化子陣列（Maximum Subarray）：http://suo.im/N0TXd

5. 陣列中第 k 最大的元素（Kth Largest Element in an Array）：http://suo.im/2P7aIi

6. 搜索陣列中的所有 Duplicates：http://suo.im/2wQwpw

7. 最長增長子序列（Longest Increasing Subsequence）：http://suo.im/PvJyK

8. 旋轉圖像、矩陣（Rotate Image, matrix）：http://suo.im/3BGG1x

9. 攪亂陣列（Shuffle an Array）：http://suo.im/3V5MBe

10. 在旋轉陣列中搜索最小值：http://suo.im/2xtLa0

11. 在旋轉陣列中搜索：http://suo.im/1Ued08

鏈表（linked list)

1. 單鏈表實現：http://suo.im/2n3Kzr

2. 雙向鏈表實現（Doubly Linked List）：http://suo.im/1y98CP

3. 刪除鏈表中的結點：http://suo.im/41ZByL

4. 迴文鏈表（Palindrome Linked List）：http://suo.im/3OWugt

5. 反向鏈表（Reverse Linked List）：http://suo.im/OxjXQ

6. 兩個鏈表的交集點（Intersection of Two Linked Lists）：http://suo.im/36rPzZ

7. 鏈表循環：http://suo.im/gANC2

8. 從表的底部一處 Nth 節點：http://suo.im/4D3RNj

9. 合并分類鏈表（Merge Sort List）：http://suo.im/4jAMx3

10. 發現鏈表循環：http://suo.im/2UFfZI

11. 合并 k 分類列表：http://suo.im/4uWyyt

12. 其他有關列表的問題：http://suo.im/4TyiJ

二叉樹（Binary Tree）

1. 二叉樹的層次遍歷（Binary Tree Level Order Traversal）：http://suo.im/1DRKTK

2. 左葉節點求和（Sum of Left Leaves）：http://suo.im/nZnDk

3. 二叉樹轉置（Invert Binary Tree）： http://suo.im/27dXUu

4. 二叉搜索樹迭代器（Binary Search Tree Iterator）：http://suo.im/4EgmWR

5. 二叉樹後序遍歷（Binary Tree Postorder Traversal）：http://suo.im/2I6r5S

6. 二叉樹前序遍歷（Binary Tree Preorder Traversal）：http://suo.im/1AF5J0

7. 平面化二叉樹為鏈表（Flatten Binary Tree to Linked List）：http://suo.im/46kRsP

8. 對稱樹（Symmetric Tree）：http://suo.im/BnxLJ

9. 二叉樹中序遍歷（Binary Tree Inorder Traversal）：http://suo.im/snOMr

10. 相似樹（Same Tree）：http://suo.im/1OCC7W

11. 二叉樹最大深度（Maximum Depth of Binary Tree）：http://suo.im/2KinyW

12. 平衡二叉樹（Balanced Binary Tree）：http://suo.im/3goksD

13. 二叉樹最小深度（Minimum Depth of Binary Tree）：http://suo.im/2f53cs

14. 平衡二叉搜索樹排序列表（Sorted List to Balanced Binary Search Tree）：http://suo.im/2D1MAo

15. 驗證二叉搜索樹（Validate Binary Search Tree）：http://suo.im/1lkBnt

16. 平衡搜索樹排序列表（Sorted List to Balanced BST）：http://suo.im/2Qr9IL

17. 平衡搜索樹第 k 最小元素（Kth Smallest Element in a BST）：http://suo.im/4mwq7K

18. 二叉樹的之字形層序遍歷（Binary Tree Zigzag Level Order Traversal）：http://suo.im/3NCvZW

19. 平衡搜索樹的結點刪除（Delete Node in a BST）：http://suo.im/1cXcP3

20. 平衡樹的最小公共祖先（Lowest Common Ancestor of BST）：http://suo.im/MBljD

21. 二叉樹的左視圖（Binary Tree Left Side View）：http://suo.im/1hzBvx

22. 二叉樹的右視圖（Binary Tree Right Side View）：http://suo.im/2Invga

23. 平衡搜索樹的眾數（Mode in BST）：http://suo.im/3Jyrn2

24. 最高頻率子樹和（Most Frequent Subtree Sum）：http://suo.im/35LlcZ

25. 搜尋每行最大元素（Find Largest Element in Each Row）：http://suo.im/32twya

其他樹型問題：http://suo.im/4TyiJ

數學

1. 整數拆分（Integer Break）：http://suo.im/lJU8r

2. 逆位（Reverse Bits）：http://suo.im/2E075a

3. 迴文數：（Palindrome Number）：http://suo.im/3pkhnt

4. 冪（Math.pow）：http://suo.im/1Wr3E9

5. 壺和水的問題（Jug and Water Problem）：http://suo.im/1gWPQG

6. 愛拉托遜新篩法（Sieve of Eratosthenes）：http://suo.im/Pi0G7

7. 費馬素數（Fermat"s primality）：http://suo.im/2HZFT3

8. 評估逆波蘭式表示法（Evaluate Reverse Polish Notation）：http://suo.im/jIGg6

堆棧&隊列（Stack & Queue）

1. 最小堆棧：http://suo.im/4FiVlB

2. 最小隊列：http://suo.im/3KEtsq

3. 使用隊列實現堆棧：http://suo.im/D5r2s

4. 使用堆棧實現隊列：http://suo.im/171IwF

動態編程（Dynamic Programming）

1. 斐波那契數列：http://suo.im/1zjJhk

2. 詞內換行（word break)：http://suo.im/3BIxnZ

3. 子集和：http://suo.im/abSSP

4. 0/1 漸縮問題：http://suo.im/1gVbIL

5. 最短迴文（KMP）：http://suo.im/362qXW

MISC

1. 並查：http://suo.im/24ZJmj

2. 排列：http://suo.im/2NZx1s

3. 子集：http://suo.im/PgGSw

演算法方向

排序與搜索（Sorting And Searching）

1. 上推排序：http://suo.im/2ofoaz

2. 插入排序：http://suo.im/2unWJM

3. 選擇排序：http://suo.im/2Sqldb

4. 計算排序：http://suo.im/ZsIt7

5. 二叉搜索，上下界：http://suo.im/10C1jM

6. 歸併排序：http://suo.im/1iBDRS

7. 快速排序：http://suo.im/1ZV7sc

圖（Graphs）

1. 寬度優先搜索（BFS）：http://suo.im/2GhGd8

2. 深度優先搜索（DFS)：http://suo.im/1xuHah

3. Prim 最小生成樹（MST)：http://suo.im/34Ignu

4. KrusKal 最小生成樹（MST)：無

5. 拓撲排序：http://suo.im/2KxOO

6. 最短路徑的戴克斯特拉演算法（Dijsktra）：http://suo.im/3uv4kJ

7. 最短路徑的 Bellman-Ford 演算法：http://suo.im/2HgD4k

8. 啟發式路徑搜索（Heuristic Path Finding):http://suo.im/2pQoF6

9. 二分圖：http://suo.im/29I5J1

字元串（String）

1. Rabin Karp 序列搜索：http://suo.im/3dUjZM

2. Ransom Note：http://suo.im/2fIVZc

3. 逆字元串（Reverse String）：http://suo.im/355a41

4. 最長公共前綴（Longest Common Prefix）：http://suo.im/1gt97D

5. Is 易位構詞（Anagram）：http://suo.im/3BWyAQ

6. Needle and Haystack：http://suo.im/lXoT4

7. 詞內換行（word break）：http://suo.im/3BIxnZ

數據結構

樹（Trees）

1. 二叉搜索樹（遞歸）：http://suo.im/2I4nfe

2. 二叉搜索樹（迭代）：http://suo.im/1M2Q6Z

3. AVL 樹：http://suo.im/151lYW

4. Trie(Prefix 樹）：http://suo.im/2evIeJ