「面試預警」二叉搜索樹-雙指針-貪心 演算法題匯總
- 2019 年 10 月 16 日
- 筆記
本文將覆蓋 「字元串處理」 + 「動態規劃」 方面的面試演算法題，文中我將給出：
- 面試中的題目
- 解題的思路
- 特定問題的技巧和注意事項
- 考察的知識點及其概念
- 詳細的程式碼和解析
開始之前，我們先看下會有哪些重點案例：
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！
現在就讓我們開始吧！
二叉搜索樹
二叉搜索樹（Binary Search Tree），它或者是一棵空樹，或者是具有下列性質的二叉樹：
- 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
- 它的左、右子樹也分別為二叉搜索樹。
驗證二叉搜索樹
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特徵：
- 節點的左子樹只包含小於當前節點的數。
- 節點的右子樹只包含大於當前節點的數。
- 所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 :
輸入: 5 / 1 4 / 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]。 根節點的值為 5 ，但是其右子節點值為 4 。解題思路
乍一看，這是一道很簡單的題。只需要遍歷整棵樹，檢查 node.right.val > node.val 和
node.left.val < node.val 對每個結點是否成立。
問題是，這種方法並不總是正確。不僅右子結點要大於該節點，整個右子樹的元素都應該大於該節點。例如:這意味著我們需要在遍歷樹的同時保留結點的上界與下界，在比較時不僅比較子結點的值，也要與上下界比較。
上述思路可以用遞歸法實現:
- 首先將結點的值與上界和下界（如果有）比較。然後，對左子樹和右子樹遞歸進行該過程。
影片
public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode root, long min, long max){ if (root == null) { return true; } if (root.val <= min || root.val >= max){ return false; } return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); }二叉搜索樹中第K小的元素
給定一個二叉搜索樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明：
你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。
示例 :
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / 3 6 / 2 4 / 1 輸出: 3解題思路
- 增加 getCount 方法來獲取傳入節點的子節點數（包括自己）
- 從 root 節點開始判斷k值和子節點數的大小決定遞歸路徑是往左還是往右。
public int kthSmallest(TreeNode root, int k) { if (root == null) { return 0; } int leftCount = getCount(root.left); if (leftCount >= k) { return kthSmallest(root.left, k); } else if (leftCount + 1 == k) { return root.val; } else { //注（1） return kthSmallest(root.right, k - leftCount - 1); } } private int getCount(TreeNode root) { if (root == null) { return 0; } return getCount(root.left) + getCount(root.right) + 1; }註：
（1）為什麼是 k – leftCount – 1 而不是 k ，我們可以把當前的二叉樹看成左右兩部分。在執行到這個條件的時候，很明顯，左邊 leftCount 個數，加上根節點，都小於所要求的元素。接著，現在要從右子樹搜索，很明顯，搜索是往下的，不可能往上（原根節點的方向）搜索，故，之前 leftCount + 1 個數作廢，所以所傳入 k – leftCount – 1
數組 / 雙指針
所謂雙指針
指的是在遍歷對象的過程中，不是普通的使用單個指針進行訪問，而是使用兩個相同方向或者相反方向的指針進行掃描，從而達到相應的目的。
換言之，雙指針法充分使用了數組有序這一特徵，從而在某些情況下能夠簡化一些運算。
加一
給定一個非負數，表示一個數字數組，在該數的基礎上+1，返回一個新的數組。該數字按照數位高低進行排列，最高位的數在列表的最前面。
示例 :
輸入: [4,3,2,1] 輸出: [4,3,2,2] 解釋: 輸入數組表示數字 4321。解題思路
只需要判斷有沒有進位並模擬出它的進位方式，如十位數加 11 個位數置為 00，如此循環直到判斷沒有再進位就退出循環返回結果。
然後還有一些特殊情況就是當出現 9999、999999 之類的數字時，循環到最後也需要進位，出現這種情況時需要手動將它進一位。
影片
給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一
public int[] plusOne(int[] digits) { for (int i = digits.length - 1; i >= 0; i--) { digits[i]++; digits[i] = digits[i] % 10; if (digits[i] != 0) return digits; } digits = new int[digits.length + 1]; digits[0] = 1; return digits; }刪除元素
給定一個數組和一個值，在原地刪除與值相同的數字，返回新數組的長度。
解題思路
- 定義一個 index 用於記錄新數組下標，遍曆數組
- 如果與傳入值不同，則其應存在於新數組中 index++ 並存入
- 如果與傳入值相同，說明重複，則直接跳過該數
- 最後返回 index 即可
public int removeElement(int[] A, int elem) { if (A == null || A.length == 0) { return 0; } int index = 0; for (int i = 0; i < A.length; i++) { if (A[i] != elem) { A[index++] = A[i]; } } return index; }刪除排序數組中的重複數字
在原數組中「刪除」重複出現的數字，使得每個元素只出現一次，並且返回「新」數組的長度。
示例 :
給定 nums = [0,0,1,1,1,2,2,3,3,4], 函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。 你不需要考慮數組中超出新長度後面的元素。解題步驟
- 數組完成排序後，我們可以放置兩個指針 size 和 i，其中 size 是慢指針，而 i 是快指針。
- 只要 nums[size] = nums[i] ，我們就增加 i 以跳過重複項。
- 當我們遇到 nums[i] =nums[size] 時，跳過重複項的運行已經結束
- 因此我們必須把它（nums[i]）的值複製到 nums[size+1]。
- 然後遞增 i 接著我們將再次重複相同的過程，直到 size 到達數組的末尾為止。
public int removeDuplicates(int[] A) { if (A == null || A.length == 0) { return 0; } int size = 0; for (int i = 0; i < A.length; i++) { if (A[i] != A[size]) { A[++size] = A[i]; } } // (1) return size + 1; }註：因為 size 為下標，所以返回長度要加一
我的日程安排表 I
實現MyCalendar類來存儲活動。如果新添加的活動沒有重複，則可以添加。類將有方法book(int start，int end)。這代表左閉右開的間隔[start，end)有了預定，範圍內的實數x，都滿足start <= x < end，返回true。 否則，返回false，並且事件不會添加到日曆中。
示例 :
MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false MyCalendar.book(20, 30); // returns true 解釋: 第一個日程安排可以添加到日曆中. 第二個日程安排不能添加到日曆中，因為時間 15 已經被第一個日程安排預定了。 第三個日程安排可以添加到日曆中，因為第一個日程安排並不包含時間 20 。解題步驟
- TreeMap 是一個有序的key-value集合，它通過 紅黑樹 實現，繼承於AbstractMap，所以它是一個Map，即一個key-value集合。
- TreeMap可以查詢小於等於某個值的最大的key，也可查詢大於等於某個值的最小的key。
- 元素的順序可以改變，並且對新的數組不會有影響。
-
floorKey(K key) 方法用於返回小於或等於給定的鍵的所有鍵中，的最大鍵，或null，如果不存在這樣的鍵
-
ceilingKey(K key) 方法用於返回大於或等於返回到給定的鍵中，的最小鍵，或null，如果不存在這樣的鍵
class MyCalendar { TreeMap<Integer, Integer> calendar; MyCalendar() { calendar = new TreeMap(); } public boolean book(int start, int end) { Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start); if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) { calendar.put(start, end); return true; } return false; } }合併兩個有序數組
合併兩個排序的整數數組A和B變成一個新的數組。可以假設A具有足夠的空間去添加B中的元素。
說明:
初始化 A 和 B 的元素數量分別為 m 和 n。
你可以假設 A 有足夠的空間（空間大小大於或等於 m + n）來保存 B 中的元素。
示例:
輸入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 輸出: [1,2,2,3,5,6]解題思路
- 雙指針 / 從後往前
- 這裡的指針 p 用於追蹤添加元素的位置。
public void mergeSortedArray(int[] A, int m, int[] B, int n) { int i = m - 1, j = n - 1, index = m + n - 1; while (i >= 0 && j >= 0) { if (A[i] > B[j]) { A[index--] = A[i--]; } else { A[index--] = B[j--]; } } while (i >= 0) { A[index--] = A[i--]; } while (j >= 0) { A[index--] = B[j--]; } }貪心
顧名思義，貪心演算法總是作出在當前看來最好的選擇。也就是說貪心演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心演算法得到的最終結果也是整體最優的。雖然貪心演算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心演算法不能得到整體最優解，其最終結果卻是最優解的很好近似。
影片
買賣股票的最佳時機
假設有一個數組，它的第i個元素是一支給定的股票在第i天的價格。如果你最多只允許完成一次交易(例如，一次買賣股票)，設計一個演算法來找出最大利潤。
注意:
- 你不能在買入股票前賣出股票。
示例 :
輸入: [7,1,5,3,6,4] 輸出: 5 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格。如果將測試範例 [7, 1, 5, 3, 6, 4]
繪製成圖，我們發現：
- 我們需要找到最小的谷之後的最大的峰。
- 我們可以維持兩個變數 —— min 和 profit，它們分別對應迄今為止所得到的最小的谷值和最大的利潤（賣出價格與最低價格之間的最大差值）。
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int min = Integer.MAX_VALUE; //記錄最低的價格 int profit = 0; for (int price : prices) { min = Math.min(price, min); profit = Math.max(price - min, profit); } return profit; }買賣股票的最佳時機 II
給定一個數組 prices 表示一支股票每天的價格。可以完成任意次數的交易, 不過不能同時參與多個交易，設計一個演算法求出最大的利潤。
解題思路
貪心：
- 只要相鄰的兩天股票的價格是上升的,
- 我們就進行一次交易, 獲得一定利潤。
影片
public int maxProfit(int[] prices) { int profit = 0; for(int i = 0 ; i < prices.length -1; i++) { if(prices[i + 1] > prices[i]) { profit += prices[i + 1] - prices[i]; } } return profit; }最大子數組
給定一個整數數組，找到一個具有最大和的子數組，返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。解題思路
public int maxSubArray(int[] nums) { if(nums == null || nums.length == 0) { return 0; } int max = Integer.MIN_VALUE; int sum = 0; for (int num : nums) { sum += num; max = Math.max(sum, max); sum = Math.max(sum, 0); } return max; }主元素
給定一個整型數組，找出主元素，它在數組中的出現次數嚴格大於數組元素個數的二分之一(可以假設數組非空，且數組中總是存在主元素)。
解題思路
- 重點在於：主元素數量大於數組所有元素的二分之一
- 所以我們要做的是，選出一個出現次數大於其他所有數，出現次數和的數即可
- 設一個計數器 currentMajor 候選數 和 一個 count 用於記錄次數
- 每噹噹前數和 currentMajor 值相同時， count 值 +1
- 每噹噹前數和 currentMajor 值不同時， count 值 -1
- 每次 count 等於 0 時，說明在之前訪問的數組裡 currentMajor 的數量小於或等於一半
- 則將 currentMajor 賦值為當前數，繼續尋找。
public int majorityNumber(List<Integer> nums) { int currentMajor = 0; int count = 0; for(Integer num : nums) { if(count == 0) { currentMajor = num; } if(num == currentMajor) { count++; } else { count--; } } return currentMajor; }Attention
- 為了提高文章品質，防止冗長乏味
下一部分演算法題
-
本片文章篇幅總結越長。我一直覺得，一片過長的文章，就像一堂超長的 會議/課堂，體驗很不好，所以我打算再開一篇文章
-
在後續文章中，我將繼續針對
鏈表棧隊列堆動態規劃矩陣位運算等近百種，面試高頻演算法題，及其圖文解析 + 教學影片 + 範例程式碼，進行深入剖析有興趣可以繼續關注 _yuanhao 的編程世界 -
不求快，只求優質，每篇文章將以 2 ～ 3 天的周期進行更新，力求保持高品質輸出
# 相關文章
面試高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」之 二分 + 哈希表 + 堆 + 優先隊列 合集
?面試必備：高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」必知必會 排序 + 二叉樹 部分！?
每個人都要學的圖片壓縮終極奧義，有效解決 Android 程式 OOM
Android 讓你的 Room 搭上 RxJava 的順風車 從重複的程式碼中解脫出來
ViewModel 和 ViewModelProvider.Factory：ViewModel 的創建者
單例模式-全局可用的 context 對象，這一篇就夠了
縮放手勢 ScaleGestureDetector 源碼解析，這一篇就夠了
Android 屬性動畫框架 ObjectAnimator、ValueAnimator ，這一篇就夠了
看完這篇再不會 View 的動畫框架，我跪搓衣板
看完這篇還不會 GestureDetector 手勢檢測，我跪搓衣板！
請點贊！因為你的鼓勵是我寫作的最大動力！
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！
