這個課時，我們找一些大廠的真題進行分析和演練。在看真題前，我們依然是再重復一遍通用的解題方法論，它可以分為以下 4 個步驟： 1. 復雜度分析。估算問題中復雜度的上限和下限。 2. 定位問題。根據問題類型，確定采用何種算法思維。 3. 數據操作分析。根據增、刪、查和數據順序關系去選擇合適的數據結構，利用空間換取時間。 4. 編碼實現。 #### 大廠真題實戰演練 **例題 1：判斷數組中所有的數字是否只出現一次** 【題目】 判斷數組中所有的數字是否只出現一次。給定一個個數字 arr，判斷數組 arr 中是否所有的數字都只出現過一次。約束時間復雜度為 O(n)。例如，arr = {1, 2, 3}，輸出 YES。又如，arr = {1, 2, 1}，輸出 NO。 【解析】 這個題目相當于一道開胃菜，也是一道送分題。我們還是嚴格圍繞解題方法論，去拆解這個問題。 我們先來看一下復雜度。判斷是否所有數字都只出現一次，很顯然我們需要對每個數字進行遍歷，因此時間復雜度為 O(n)。而每次的遍歷，都要判斷當前元素在先前已經掃描過的區間內是否出現過。由于此時并沒有額外信息（例如數組有序）輸入，因此，還需要 O(n) 的時間進行判斷。綜合起來看就是 O(n2) 的時間復雜度。這顯然與題目的要求不符合。 然后我們來定位問題。根據題目來看，你可以理解這是一個數據去重的問題。但是由于我們并沒有學過太多解決這類問題的算法思維，因此我們不妨再從數據操作的視角看一下。 按照解題步驟，接下來我們需要做數據操作分析。 每輪迭代需要去判斷當前元素在先前已經掃描過的區間內是否出現過，這就是一個查找的動作。也就是說，每次迭代需要對數據進行數值特征方面的查找。這個題目只需要判斷是否有重復，并不需要新增、刪除的動作。 在優化數值特性的查找時，我們應該立馬想到哈希表。因為它能在 O(1) 的時間內完成查找動作。這樣，整體的時間復雜度就可以被降低為 O(n) 了。與此同時，空間復雜度也提高到了 O(n)。 根據上面的思路進行編碼開發，具體代碼如下： ``` public static void main(String[] args) { int[] arr = { 1, 2, 3 }; boolean isUniquel = isUniquel(arr); if (isUniquel) { System.out.println("YES"); } else { System.out.println("NO"); } } public static boolean isUniquel(int[] arr) { Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < arr.length; i++) { if (d.containsKey(arr[i])) { return false; } d.put(arr[i], 1); } return true; } ``` 我們對代碼進行解讀。在主函數第 1～9 行中，調用 isUniquel() 函數進行判斷，并根據結果打印 YES 或者 NO。在函數 isUniquel() 內，第 12 行定義了一個 k-v 結構的 map。 接著 13 行開始，對 arr 的每個元素進行循環。如果 d 中已經存在 arr[i] 了，那么就返回 false（第 14～16 行）；否則就把 arr[i],1 的 k,v 關系放進 d 中（第 17 行）。 這道題目比較簡單，屬于數據結構的應用范疇。 **例題 2：找出數組中出現次數超過數組長度一半的元素** 【題目】 假設在一個數組中，有一個數字出現的次數超過數組長度的一半，現在要求你找出這個數字。 你可以假設一定存在這個出現次數超過數組長度的一半的數字，即不用考慮輸入不合法的情況。要求時間復雜度是 O(n)，空間復雜度是 O(1)。例如，輸入 a = {1,2,1,1,2,4,1,5,1}，輸出 1。 【解析】先來看一下時間復雜度的分析。一個直觀想法是，一邊掃描一邊記錄每個元素出現的次數，并利用 k-v 結構的哈希表存儲。例如，一次掃描后，得到元素-次數（1-5，2-2，4-1，5-1）的字典。接著再在這個字典里去找到次數最多的元素。這樣的時間復雜度和空間復雜度都是 O(n)。不過可惜，這并不滿足題目的要求。 接著，我們需要定位問題。 從問題出發，這并不是某個特定類型的問題。而且既然空間復雜度限定是 O(1)，也就意味著不允許使用任何復雜的數據結構。也就是說，數據結構的優化不可以用，算法思維的優化也不可以用。 面對這類問題，我們只能從問題出發，看還有哪些信息我們沒有使用上。題目中有一個重要的信息是，這個出現超過半數的數字一定存在。回想我們上邊的解法，它可以找到出現次數最多的數字，但沒有使用到“必然超過半數”這個重要的信息。 分析到這里，我們不妨想一下這個場景。假設現在三國交戰，其中 A 國的兵力比 B 國和 C 國的總和還多。那么人們就常常會說，哪怕是 A 國士兵“一個碰一個”地和另外兩國打消耗戰，都能取得最后的勝利。 說到這里，不知道你有沒有一些發現。“一個碰一個”的思想，那就是如果相等則加 1，如果不等則減 1。這樣，只需要記錄一個當前的緩存元素變量和一個次數統計變量就可以了。 根據上面的思路進行編碼開發，具體代碼為： ``` public static void main(String[] args) { int[] a = {1,2,2,1,1,4,1,5,1}; int result = a[0]; int times = 1; for (int i = 1; i < a.length; i++) { if (a[i] != result) { times--; } else { times++; } if (times == -1) { times = 1; result = a[i]; } } System.out.println(result); } ``` 我們對代碼進行解讀。第 3～4 行，初始化變量，結果 result 賦值為 a[0]，次數 times 為 1。 接著進入循環體，執行“一個碰一個”，即第 6～11 行： * 如果當前元素與 a[i] 不相等，次數減 1； * 如果當前元素與 a[i] 相等，次數加 1。 當次數降低為 -1 時，則發生了結果跳轉。此時，result 更新為 a[i]，次數重新置為 1。最終我們就在 O(n) 的時間復雜度下、O(1 )的空間復雜度下，找到了結果。 **例題 3：給定一個方格棋盤，從左上角出發到右下角有多少種方法** 【題目】 在一個方格棋盤里，左上角是起點，右下角是終點。每次只能向右或向下，移向相鄰的格子。同時，棋盤中有若干個格子是陷阱，不可經過，必須繞開行走。 要求用動態規劃的方法，求出從起點到終點總共有多少種不同的路徑。例如，輸入二維矩陣 m 代表棋盤，其中，1 表示格子可達，-1 表示陷阱。輸出可行的路徑數量為 2。  【解析】 題目要求使用動態規劃的方法，這是我們解題的一個難點，也正是因為這一點限制才讓這道題目區別于常見的題目。 對于 O2O 領域的公司，尤其對于經常要遇到有限資源下，去最優化某個目標的崗位時，動態規劃應該是高頻考察的內容。我們依然是圍繞動態規劃的解題方法，從尋找最優子結構的視角去解決問題。 **千萬別忘了，動態規劃的解題方法是，分階段、找狀態、做決策、狀態轉移方程、定目標、尋找終止條件**。 我們先看一下這個問題的階段。很顯然，從起點開始，每一個移動動作就是一個階段的決策動作，移動后到達的新的格子就是一個狀態。 狀態的轉移和先前的最短路徑問題非常相似。假定棋盤的維度是例子中的 3 x 6，那么起點標記為 m[0,0]，終點標記為 m[2,5]。利用 V(m[i,j]) 表示從起點到 m[i,j] 的可行路徑總數。那么則有， V(m[i,j]) = V(m[i-1,j]) + V(m[i,j-1])。 也就是說，到達某個格子的路徑數，等于到達它左邊格子的路徑數，加上到達它上邊格子的路徑數。我們的目標也就是根據 m 矩陣，求解出 V(m[2,5])。 最后再來看一下終止條件。起點到起點只有一種走法，因此，V(m[0,0]) = 1。同時，所有棋盤外的區域也是不可抵達的，因此 V(m[-, ]) = 0，V(m[ , - ]) = 0。需要注意的是，根據題目的信息，標記為 -1 的格子是不得到達的。也就是說，如果 m[i,j] 為 -1，則 V(m[i,j]) = 0。 分析到了這里，我們可以得出了一個可行的解決方案。根據狀態轉移方程，就能尋找到最優子結構。即 V(m[i,j]) = V(m[i-1,j]) + V(m[i,j-1])。 很顯然，我們可以用遞歸來實現。其他需要注意的地方，例如終止條件、棋盤外區域以及棋盤內不可抵達的格子，我們都已經定義好。接下來就可以進入開發階段了。具體代碼如下： ``` public static void main(String[] args) { int[][] m = {{1,1, 1, 1, 1,1}, {1,1,-1,-1,1,1}, {1,1,-1, 1,-1,1}}; int path = getpath(m,2,5); System.out.println(path); } public static int getpath(int[][] m, int i, int j) { if (m[i][j] == -1) { return 0; } if ((i > 0) && (j > 0)) { return getpath(m, i-1, j) + getpath(m, i, j-1); } else if ((i == 0) && (j > 0)) { return getpath(m, i, j-1); } else if ((i > 0) && (j == 0)){ return getpath(m, i-1, j); } else { return 1; } } ``` 我們對代碼進行解讀。第 1～5 行為主函數。在主函數中，定義了 m 數組，就是輸入的棋盤。在其中，數值為 -1 表示不可抵達。隨后第 3 行代碼調用 getpath 函數來計算從頂點到 m[2,5] 位置的路徑數量。 接著進入第 7～23 行的getpath()函數，用來計算到達 m[i,j] 的路徑數。在第 8～10 行進行判斷：如果 m[i][j ]== -1，也就是當前格子不可抵達，則無須任何計算，直接返回 0 即可。如果 m[i][j] 不等于 -1，則繼續往下判斷。 如果 i 和 j 都是正數，也就是說，它們不在邊界上。那么根據狀態轉移方程，就能得到第 12 行的遞歸執行動作，即到達 m[i,j] 的路徑數，等于到達 m[i-1,j] 的路徑數，加上到 達 m[i,j-1] 的路徑數。 如果 i 為 0，而 j 還是大于 0 的，也就是說此時已經到了最左邊的格子了，則直接返回 getpath(m, i, j-1) 就可以了。 如果 i 為正，而 j 已經變為 0 了，同理直接返回 getpath(m, i-1, j) 就可以了。 剩下的 else 判斷是，如果 i 和 j 都變成了 0，則說明在起點。此時起點到起點的路徑數是 1，這就是終止條件。 根據這個例子不難發現，動態規劃的代碼往往并不復雜。關鍵在于你能否把階段、狀態、決策、狀態轉移方程和終止條件定義清楚。 #### 總結 在備戰大廠面試時，一定要加強問題解決方法論的沉淀。絕大多數一線的互聯網公司講究的是解決問題的規范性，這就決定了其更關注的是問題解決過程的步驟、方法或體系，而不僅僅是解決后的結果。 #### 練習題 下面我們給出一個練習題，幫助你鞏固本課時講解的解題思路和方法。 【題目】 小明從小就喜歡數學，喜歡在筆記里記錄很多表達式。他覺得現在的表達式寫法很麻煩，為了提高運算符優先級，不得不添加很多括號。如果不小心漏了一個右括號的話，就差之毫厘，謬之千里了。因此他改用前綴表達式，例如把 (2 + 3) * 4寫成* + 2 3 4，這樣就能避免使用括號了。這樣的表達式雖然書寫簡單，但計算卻不夠直觀。請你寫一個程序幫他計算這些前綴表達式。 在這個題目中，輸入就是前綴表達式，輸出就是計算的結果。你可以假設除法為整除，即“5/3=1”。例如，輸入字符串為 +?2?3，輸出 5；輸入字符串為 *?+?2?2?3，輸出為 12；輸入字符串為 *?2?+?2?3，輸出為 10。 我們給出一些提示。假設輸入字符串為 *?2?+?2?3，即 2*(2+3)。第一個字符為運算符號 *，它將對兩個數字進行乘法。如果后面緊接著的字符不全是數字字符，那就需要暫存下來，先計算后面的算式。一旦后面的計算完成，就需要接著從后往前去繼續計算。 因為從后往前是一種逆序動作，我們能夠很自然地想到可以用棧的數據結構進行存儲。你可以嘗試利用棧，去解決這個問題。