面試必備：高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」必知必會 排序 + 二叉樹 部分！
- 2019 年 10 月 11 日
- 筆記
排序
所謂排序演算法，即通過特定的演算法因式將一組或多組數據按照既定模式進行重新排序。這種新序列遵循著一定的規則，體現出一定的規律，因此，經處理後的數據便於篩選和計算，大大提高了計算效率。
對於排序：
- 我們首先要求其具有一定的穩定性
- 即當兩個相同的元素同時出現於某個序列之中
- 則經過一定的排序演算法之後
- 兩者在排序前後的相對位置不發生變化。
所以，就讓我們先來看看，面試中，有哪些超高頻的排序演算法
冒泡排序
冒泡排序可以說是最基礎的了，無非就是兩個 for 循環嵌套，然後兩兩比較交換罷了。這就不多說了。
步驟：
1、比較相鄰的元素。如果第一個比第二個大（小），就交換他們兩個。
2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大（小）的數。
3、針對所有的元素重複以上的步驟，除了最後已經選出的元素（有序）。
4、持續每次對越來越少的元素（無序元素）重複上面的步驟，直到沒有任何
影片：
示例程式碼：
public void bubbleSort(int[] arr) { int temp = 0; boolean swap; for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的長度 // 增加一個swap的標誌，當前一輪沒有進行交換時，說明數組已經有序 swap = false; for (int j = 0; j < i; j++) { // 從第一個元素到第i個元素 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swap = true; } } if (!swap){ break; } } }
歸併排序
對於歸併排序而言，思想可以概括為：分而治之。也就是將一個數組，首先劃分為一堆單個的數，然後再一個接一個的，進行兩兩有序合併，最後就得到了一個有序數組。
步驟：
將待排序的數列分成若干個長度為1的子數列
然後將這些數列兩兩合併；得到若干個長度為2的有序數列
再將這些數列兩兩合併；得到若干個長度為4的有序數列
再將它們兩兩合併；直接合併成一個數列為止
這樣就得到了我們想要的排序結果
影片：
示例程式碼：
// 入口 public void mergeSort(int[] arr) { int[] temp = new int[arr.length]; internalMergeSort(arr, temp, 0, arr.length - 1); } private void internalMergeSort(int[] arr, int[] temp, int left, int right) { // 當left == right時，不需要再劃分 if (left < right) { int mid = (left + right) / 2; // 左右往下拆分 internalMergeSort(arr, temp, left, mid); internalMergeSort(arr, temp, mid + 1, right); // 拆分結束後返回結果進行合併 mergeSortedArray(arr, temp, left, mid, right); } } // 合併兩個有序子序列 public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++]; } // 合併完，將非空的那列拼入 while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // 把temp數據複製回原數組 for (i = 0; i < k; i++) { arr[left + i] = temp[i]; } }
快速排序
快速排序的思想，可以簡單的概括為：兩邊包抄、一次一個。每選一個基準點，一次排序後確定它的最終位置，一步到位。
步驟：
1、先從數列中取出一個數作為基準數
2、分區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊
3、再對左右區間重複第二步，直到各區間只有一個數
概括來說為 挖坑填數+分治法
註： 快排演算法不唯一，到目前為止我已經看到三種排法，這裡我用最老的，就是很多教材上的排法解析
影片：
示例程式碼：
public void quickSort(int[] arr){ quickSort(arr, 0, arr.length-1); } private void quickSort(int[] arr, int low, int high){ if (low >= high) return; int pivot = partition(arr, low, high); //將數組分為兩部分 quickSort(arr, low, pivot - 1); //遞歸排序左子數組 quickSort(arr, pivot + 1, high); //遞歸排序右子數組 } private int partition(int[] arr, int low, int high){ int pivot = arr[low]; //基準 while (low < high){ while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; //交換比基準大的記錄到左端 while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; //交換比基準小的記錄到右端 } //掃描完成，基準到位 arr[low] = pivot; //返回的是基準的位置 return low; }
計數排序
計數排序顧名思義，其思想就在於記錄各個數的出現次數，最後按順序取出即可。
步驟：
建一個長度為K+1的的數組C，裡面的每一個元素初始都置為0(Java裡面默認就是0)。
遍歷待排序的數組，計算其中的每一個元素出現的次數，比如一個key為i的元素出現了3次，那麼C[i]=3。
累加C數組，獲得元素的排位，從0開始遍歷C, C[i+1]=C[i]+C[i-1]
建一個臨時數組T，長度與待排序數組一樣。從數組末尾遍歷待排序數組，把元素都安排到T裡面，直接從C裡面就可以得到元素的具體位置， 不過記得每處理過一個元素之後都要把C裡面對應位置的計數減1。
影片：
示例程式碼：
我在網上看了巨多程式碼，但基本都是用來處理 0 以上數的計數排序。下面介紹的這個演算法，可以適應小於 0 的數的計數排序，不過我加了很多注釋，也很好理解：
public void countSort(int[] arr) { // 找到最大值和最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int[] b = new int[arr.length]; // 存儲數組 int[] count = new int[max - min + 1]; // 計數數組 for (int num = min; num <= max; num++) { // 初始化各元素值為0，數組下標從0開始因此減min count[num - min] = 0; } for (int i = 0; i < arr.length; i++) { int num = arr[i]; count[num - min]++; // 每出現一個值，計數數組對應元素的值+1 // 此時count[i]表示數值等於i的元素的個數 } for (int i = min + 1; i <= max; i++) { count[i - min] += count[i - min - 1]; // 此時count[i]表示數值<=i的元素的個數 // 這樣做的目的是為了方便最後賦值， // 「從下個方法的 『count[num - min]--』 可以看出」 } for (int i = 0; i < arr.length; i++) { int num = arr[i]; // 原數組第i位的值 int index = count[num - min] - 1; //加總數組中對應元素的下標 b[index] = num; // 將該值存入存儲數組對應下標中 count[num - min]--; // 加總數組中，該值的總和減少1。 } // 將存儲數組的值替換給原數組 for(int i=0; i < arr.length;i++){ arr[i] = b[i]; } }
桶排序
桶排序的思想是，首先按特定規則，劃分出若干個』桶『，每個『桶』有個範圍，將大小在對應『桶』範圍內的數，對號入座。再依次將每個『桶』內的數有序排列，最後按順序拼接各個『桶』即可。
步驟：
- 根據待排序集合中最大元素和最小元素的差值範圍和映射規則，確定申請的桶個數；
- 遍歷待排序集合，將每一個元素移動到對應的桶中；
對每一個桶中元素進行排序，並移動到已排序集合中。
步驟 3 中提到的已排序集合，和步驟 1、2 中的待排序集合是同一個集合。與計數排序不同，桶排序的步驟 2 完成之後，所有元素都處於桶中，並且對桶中元素排序後，移動元素過程中不再依賴原始集合，所以可以將桶中元素移動回原始集合即可。
影片：
示例程式碼：
上面講的計數排序其實一定程度上，也可以看作一種特殊的桶排序，同樣的，網上桶排序程式碼大一堆，啥語言都有。但卻沒有一個解決小於 0 數排序問題的，要麼就不處理要麼就拋出異常，下面這個演算法，有效的解決了，小於 0 數排序的難題
public static void bucketSort(int[] arr){ // 首先還是找出最大、最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } // 桶數 // 在桶排序中，對桶的劃分個數是隨意的 // 這個方法劃分的桶數量隨帶劃分數列的密集程度改變而改變 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); // 初始化各個桶 for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } // 將每個元素放入相應的桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } // 對每個桶進行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); for (int j = 0; j < bucketArr.get(i).size(); j++) { arr[j] = bucketArr.get(i).get(j); } } }
二叉樹
在電腦科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。
這裡就我們就來看看，面試中會怎麼樣來考察我們有關二叉樹的問題，首先我們先定義一個節點類：
後文測試所使用的節點類如下：
ps：解釋LeetCode上那種class TreeNode { public TreeNode left, right; public int val; public TreeNode(int val) { this.val = val; } }
順序遍歷
二叉樹的遍歷分為以下三種：
先序遍歷：遍歷順序規則為【根左右】
中序遍歷：遍歷順序規則為【左根右】
後序遍歷：遍歷順序規則為【左右根】
下面以上圖為例，我們通過程式碼實現三種基本遍歷：
先序遍歷：
首先是程式碼實現：
// 先序遍歷 public void preTraverse(TreeNode root) { if (root != null) { System.out.println(root.val); preTraverse(root.left); preTraverse(root.right); } }遍歷結果：ABCDEFGHK
中序遍歷：
首先是程式碼實現：
// 中序遍歷 public void inTraverse(TreeNode root) { if (root != null) { inTraverse(root.left); System.out.println(root.val); inTraverse(root.right); } }遍歷結果：BDCAEHGKF
後序遍歷：
首先是程式碼實現：
// 後序遍歷 public void postTraverse(TreeNode root) { if (root != null) { postTraverse(root.left); postTraverse(root.right); System.out.println(root.val); } }遍歷結果：DCBHKGFEA
影片
層次遍歷
二叉樹的層次遍歷很好理解，在這裡我舉個例子。首先我們先給出一棵二叉樹：
層次遍歷顧名思義，就是從上到下，逐層遍歷，每層從左往右輸出
計算結果：5 - 4 - 8 - 11 - 13 - 4 - 7 - 2 - 1
關於遍歷演算法，常見的有：
- 深度優先遍歷（DFS）
- 廣度優先遍歷（BFS）
在我刷題的過程中遇到過這樣一道題：
Given a binary tree, return the zigzag level order traversal of its nodes』 values. (ie, from left to right, then right to left for the next level and alternate between).即 Z 字型遍歷，所以這裡再加上一種：
- Z 字形遍歷
下面我們來看看程式碼上的實現：
深度優先遍歷（DFS）
我們所學的層次遍歷只有 BFS（廣搜），DFS 深搜本身是用於順序排序的非遞歸實現。『用DFS』 來解決層次遍歷這種題我也是第一次見。
它的步驟可以簡要概括為：
常規深度搜索，記錄下當前節點所在層 level
將當前節點加入 List 中對應的層
由於是從左往右搜索，所以也是從左往右加入
最後得到一個類似下面的結構
0 -- 5
1 -- 4 -> 8
2 -- 11 -> 13 - > 4
3 -- 7 -> 2 -> 1
這種遍歷方式太少見，找不到相關的影片，好在原理容易理解
// 層次遍歷(DFS) public static List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } dfs(root, res, 0); return res; } private void dfs(TreeNode root, List<List<Integer>> res, int level) { if (root == null) { return; } if (level == res.size()) { res.add(new ArrayList<>()); } res.get(level).add(root.val); dfs(root.left, res, level + 1); dfs(root.right, res, level + 1); }廣度優先遍歷（BFS）
與 DFS 用遞歸去實現不同，BFS需要用隊列去實現。
層次遍歷的步驟是：
對於不為空的結點，先把該結點加入到隊列中
從隊中拿出結點，如果該結點的左右結點不為空，就分別把左右結點加入到隊列中
重複以上操作直到隊列為空
說白了就是：
父節點入隊，父節點出隊列，先左子節點入隊，後右子節點入隊。遞歸遍歷全部節點即可
影片
public List<List<Integer>> levelOrder(TreeNode root) { List result = new ArrayList(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { ArrayList<Integer> level = new ArrayList<Integer>(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode head = queue.poll(); level.add(head.val); if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } } result.add(level); } return result; }Z 字形遍歷
這個題型也很罕見，源於 LeetCode 上一道面試原題：
Given a binary tree, return the zigzag level order traversal of its nodes』 values. (ie, from left to right, then right to left for the next level and alternate between).給定一棵二叉樹，從頂向下，進行Z字形分層遍歷，即：如果本層是從左向右的，下層就是從右向左。
流程與 BFS 類似，就是多了個用於區分左右的 flag
對於不為空的結點，先把該結點加入到隊列中
從隊中拿出結點，如果該結點的左右結點不為空，就分別把左右結點加入到隊列中
將 isFromLeft 值取反
重複以上操作直到隊列為空
影片
同樣的這個體型太特殊，所以沒有相關影片解析，不過好在演算法過程也很好理解
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null){ return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean isFromLeft = false; while(!queue.isEmpty()){ int size = queue.size(); isFromLeft = !isFromLeft; List<Integer> list = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode node; if (isFromLeft){ node = queue.pollFirst(); }else{ node = queue.pollLast(); } list.add(node.val); if (isFromLeft){ if (node.left != null){ queue.offerLast(node.left); } if (node.right != null){ queue.offerLast(node.right); } }else{ if (node.right != null){ queue.offerFirst(node.right); } if (node.left != null){ queue.offerFirst(node.left); } } } result.add(list); } return result; }
### 左右翻轉
這是一道華為面試原題，題目大意是：
輸入二叉樹如下：
反轉後輸出：
乍一看很難辦，其實想一個解決方案很簡單，這裡我直接舉三個方案：
方法一：比如我們用遞歸的思路，本質思想是：
本質思想也是左右節點進行交換
交換前遞歸調用對根結點的左右節點分別進行處理
保證交換前左右節點已經翻轉。
三步搞定，我們看下程式碼實現：
public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { final TreeNode node = stack.pop(); final TreeNode left = node.left; node.left = node.right; node.right = left; if(node.left != null) { stack.push(node.left); } if(node.right != null) { stack.push(node.right); } } return root; }方法二：循環，隊列存儲（BFS，非遞歸）
本質思想是：
左右節點進行交換
循環翻轉每個節點的左右子節點
將未翻轉的子節點存入隊列中
循環直到棧里所有節點都循環交換完為止。
public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode left = node.left; node.left = node.right; node.right = left; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } return root; }方法三：「壓軸出場，三步秒殺」遞歸
本質思想是：
左右節點進行交換
交換前遞歸調用對根結點的左右節點分別進行處理
保證交換前左右節點已經翻轉。
同樣三步搞定，我們看下程式碼：
public void invert(TreeNode root) { if (root == null) { return; } TreeNode temp = root.left; root.left = root.right; root.right = temp; invert(root.left); invert(root.right); }
最大值
乍一看，是到送分題。我第一眼的想法就是：在方法中定義max用來保存遍歷得到的最大值，結果每次遞歸時，都等於在重新定義max，這種方法不對。所以怎麼辦？
採用分治思想
從整棵樹的底部開始
兩兩比較，放回最大值
看一眼演算法你就懂了
public int getMax(TreeNode root) { if (root == null) { return Integer.MIN_VALUE; } else { int left = getMax(root.left); int right = getMax(root.right); return Math.max(Math.max(left, rigth), root.val); } }
最大深度
深度問題和最大值一樣，容易想複雜，其實非常簡單，也可以看作一種分治的思想
二叉樹的最大深度是距根節點路徑最長的某一樹葉節點的深度。
二叉樹的深度等於二叉樹的高度，也就等於根節點的高度。根節點的高度為左右子樹的高度較大者+1。
影片
public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }
最小深度
這道題目太常見了，當我一看到題目時就錯了：
題目：最小深度是從根節點到最近
葉子節點的最短路徑上的節點數量。
說明: 葉子節點是指沒有子節點的節點。
看到了吧，這時就得明確正確的遞歸結束條件
舉個例子:
很多人寫出的程式碼都不符合 1,2 這個測試用例，是因為沒搞清楚題意
題目中說明: 葉子節點是指沒有子節點的節點，這句話的意思是 1 不是葉子節點
題目問的是到葉子節點的最短距離，所以所有返回結果為 1 當然不是這個結果
另外這道題的關鍵是搞清楚遞歸結束條件
- 葉子節點的定義是左孩子和右孩子都為 null 時叫做葉子節點
- 當 root 節點左右孩子都為空時，返回 1
- 當 root 節點左右孩子有一個為空時，返回不為空的孩子節點的深度
- 當 root 節點左右孩子都不為空時，返回左右孩子較小深度的節點值
影片
public int minDepth(TreeNode root) { if (root == null) { return 0; } int left = minDepth(root.left); int right = minDepth(root.right); if (left == 0) { return right + 1; } else if (right == 0) { return left + 1; } else { return Math.min(left, right) + 1; } }
平衡二叉樹
概念：平衡二叉樹每一個節點的左右兩個子樹的高度差不超過 1
設一個 flag
如果發現不平衡則就返回非 flag
影片
public boolean isBalanced(TreeNode root) { return maxDepth(root) != -1; } private int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); if (left == -1 || right == -1 || Math.abs(left - right) > 1) { return -1; } return Math.max(left, right) + 1; }
Attention
為了提高文章品質，防止冗長乏味
下一部分演算法題
本片文章篇幅總結越長。我一直覺得，一片過長的文章，就像一場超長的 會議/課堂，體驗很不好，所以打算再開一篇文章來總結其餘的考點
在後續文章中，我將繼續針對
鏈表棧隊列堆動態規劃矩陣位運算等近百種，面試高頻演算法題，及其圖文解析 + 教學影片 + 範例程式碼，進行深入剖析有興趣可以繼續關注 _yuanhao 的編程世界
相關文章
每個人都要學的圖片壓縮終極奧義，有效解決 Android 程式 OOM
Android 讓你的 Room 搭上 RxJava 的順風車 從重複的程式碼中解脫出來
ViewModel 和 ViewModelProvider.Factory：ViewModel 的創建者
單例模式-全局可用的 context 對象，這一篇就夠了
縮放手勢 ScaleGestureDetector 源碼解析，這一篇就夠了
Android 屬性動畫框架 ObjectAnimator、ValueAnimator ，這一篇就夠了
看完這篇再不會 View 的動畫框架，我跪搓衣板
看完這篇還不會 GestureDetector 手勢檢測，我跪搓衣板！
android 自定義控制項之-繪製鐘錶盤
Android 進階自定義 ViewGroup 自定義布局
歡迎關注_yuanhao的部落格園！
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！