第09講：高頻真題解析 II · 300分鐘搞定數據結構與算法

這節課繼續學習另外三種高頻題： * 合并區間和無重疊區間 * 火星字典 * 基本計算器 #### 例題分析一 LeetCode 第 56 題：給出一個區間的集合，請合并所有重疊的區間。 * 示例 1 ``` 輸入: [[1,3], [2,6], [8,10], [15,18]] 輸出: [[1,6], [8,10], [15,18]] 解釋: 區間 [1,3] 和 [2,6] 重疊，將它們合并為 [1,6]。 ``` * 示例 2 ``` 輸入: [[1,4], [4,5]] 輸出: [[1,5]] 解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。 ``` * [ ] 解題思路：貪婪法在分析一些比較復雜的問題時，可以從比較簡單的情況著手來尋找突破口，先來看看兩個區間會出現多少種情況。假設有區間 a 和 b，區間 a 的起始時間要早于 b 的起始時間。那么它們之間有如下 3 種可能會出現的情況。 * 情況一：兩個區間沒有任何重疊的部分，因此區間不會發生融合。 * 情況二和三：區間有重疊。 * 新區間的起始時間是 a 的起始時間，這個不變； * 新區間的終止時間是 a 的終止時間和 b 的終止時間的最大值，這個就是融合兩個區間的最基本的思想。給定了 n 個區間，如何有效地融合它們呢？以下是一種很直觀也是非常有效的做法。? ? ? ? 1. 先將所有的區間按照起始時間的先后順序排序，從頭到尾掃描一遍 2. 定義兩個變量 previous 和 current，分別表示前一個區間和當前的區間如果沒有融合，那么當前區間就變成了新的前一個區間，下一個區間成為新的當前區間如果發生了融合，更新前一個區間的結束時間。這個就是貪婪算法。代碼實現 ``` int[][]?merge(int[][]?intervals)?{ ????//?將所有的區間按照起始時間的先后順序排序 ????Arrays.sort(intervals,?(i1,?i2)?->?Integer.compare(i1[0],?i2[0])); ? ????//?定義一個?previous?變量，初始化為?null?? ????int[]?previous?=?null; ????//?定義一個?result?變量，用來保存最終的區間結果 ????List<int[]>?result?=?new?ArrayList<>(); ?? ????//?從頭開始遍歷給定的所有區間 ????for?(int[]?current?:?intervals)?{ ????????//?如果這是第一個區間，或者當前區間和前一個區間沒有重疊，那么將當前區間加入到結果中 ????????if?(previous?==?null?||?current[0]?>?previous[1])?{ ????????????result.add(previous?=?current); ????????}?else?{?//?否則，兩個區間發生了重疊，更新前一個區間的結束時間 ????????????prev[1]?=?Math.max(previous[1],?current[1]); ????????} ????} ???? ????return?result.toArray(new?int[result.size()][]);? ?} ``` * [ ] 算法分析時間復雜度 O(nlog(n))，因為一開始要對數組進行排序。空間復雜度為 O(n)，因為用了一個額外的 result 數組來保存結果。 > 注意：和區間相關的問題，有非常多的變化，融合區間可以說是最基本也是最常考的一個。 #### 例題分析二 LeetCode 第 435 題：給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊。 > 注意: > 1. 可以認為區間的終點總是大于它的起點。 > 2. 區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。示例 1 ``` 輸入: [ [1,2], [2,3], [3,4], [1,3] ] 輸出: 1 解釋: 移除 [1,3] 后，剩下的區間沒有重疊。 ``` 示例 2 ``` 輸入: [ [1,2], [1,2], [1,2] ] 輸出: 2 解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。 ``` 示例 3 ``` 輸入: [ [1,2], [2,3] ] 輸出: 0 解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。 ``` * [ ] 解題思路一：暴力法這道題是上一道題的一種變形，暴力法就是將各個區間按照起始時間的先后順序排序，然后找出所有的組合，最后對每種組合分別判斷各個區間有沒有互相重疊。 * [ ] 算法分析 1. 排序需要 O(nlog(n)) 的時間復雜度。 2. 找出所有組合，按照前一節課里提到的從一個字符串里找出所有子序列的組合個數的方法，取出 n 個區間，有 Cnn 種，算上空的集合，那么一共有?Cn0 + Cn1 + Cn2 + … Cnn = 2n。 3. 對每種組合進行判斷是否重疊，k 個區間，需要 O(k) 的時間復雜度。 4. 總體時間復雜度為?Cn0 x 0 + Cn1×1 + Cn2×2 + … + Cnk * k + … + Cnn×n = n×2n-1。由于 n×2n-1 已經遠大于 nlog(n)，所以排序的時間復雜度就可以忽略不計，整體的時間復雜度就是 O(n×2n)。建議：一定要記一些常見的時間復雜度計算公式，對于在面試中能準確快速地分析復雜度是非常有幫助的。 * [ ] 解題思路二：另一種暴力法對于暴力法，還有另外的分析方法。用兩個變量 prev 和 curr 分別表示前一個區間和當前區間。 1. 如果當前區間和前一個區間沒有發生重疊，則嘗試保留當前區間，表明此處不需要刪除操作。 2. 題目要求最少的刪除個數，只有在這樣的情況下，才不需要做任何刪除操作。 3. 在這種情況下，雖然兩個區間沒有重疊，但是也要考慮嘗試刪除當前區間的情況。 4. 對比哪種情況所需要刪除的區間最少。舉例：有如下的幾個區間 A、B、C，其中 A 是前一個區間，B 是當前區間，A 和 B 沒有重疊。 1. 如果只考慮保留 B 的情況，而不考慮把 B 刪除的情況，那么就會錯過一個答案，因為在這個情況下，把 B 刪除，只剩下 A 和 C，它們互不重疊，也能得到最優的解。 2. 遇到 A 和 B 相互重疊的情況時，必須要考慮把 B 刪除掉。為什么不把 A 刪除呢？因為如果把 A 刪了，B 和 C 還是可能會重疊，則需要刪除掉更多的區間，不滿足題目要求。代碼實現 ``` //?在主體函數里，先將區間按照起始時間的先后順序排序，然后調用遞歸函數 int?eraseOverlapIntervals(int[][]?intervals)?{ ????Arrays.sort(intervals,?(i1,?i2)?->?Integer.compare(i1[0],?i2[0])); ????return?eraseOverlapIntervals(-1,?0,?intervals); } //?遞歸函數里，先檢查是否已經處理完所有的區間，是，表明不需要刪除操作，直接返回 int?eraseOverlapIntervals(int?prev,?int?curr,?int[][]?intervals)?{ ????if?(curr?==?intervals.length)?{ ????????return?0; ????} ????int?taken?=?Integer.MAX_VALUE,?nottaken; ????if?(prev?==?-1?||?intervals[prev][1]?<=?intervals[curr][0])?{ ????????//?只有當prev,?curr沒有發生重疊的時候，才可以選擇保留當前的區間curr ????????taken?=?eraseOverlapIntervals(curr,?curr?+?1,?intervals); ????} ????//?其他情況，可以考慮刪除掉curr區間，看看刪除了它之后會不會產生最好的結果 ????nottaken?=?eraseOverlapIntervals(prev,?curr?+?1,?intervals)?+?1; ?? ????return?Math.min(taken,?nottaken); } ``` * [ ] 解題思路二：貪婪法 * 按照起始時間排序舉例：有四個區間 A，B，C，D，A 跨度很大，B 和 C 重疊，C 和 D 重疊，而 B 和 D 不重疊。解法：要盡可能少得刪除區間，那么當遇到了重疊的時候，應該把區間跨度大，即結束比較晚的那個區間刪除。因為如果不刪除它，它會和剩下的其他區間發生重疊的可能性非常大。當發現 A 和 B 重疊，如果不刪除 A，就得犧牲 B，C，D，而正確的答案是只需要刪除 A 和 C 即可。按照上述思想求解，實現過程如下。 1. A 和 B 重疊，由于 A 結束得比較晚，此時刪除區間 A，保留區間 B。 2. B 和 C 重疊，由于 C 結束得晚，把區間 C 刪除，保留區間 B。 3. B 和 D 不重疊，結束，一共只刪除了 2 個區間。代碼實現 ``` int?eraseOverlapIntervals(int[][]?intervals)?{ ????if?(intervals.length?==?0)?return?0;? ?? ????//?將所有區間按照起始時間排序 ????Arrays.sort(intervals,?(i1,?i2)?->?Integer.compare(i1[0],?i2[0])); ????//?用一個變量?end?記錄當前的最小結束時間點，以及一個?count?變量記錄到目前為止刪除掉了多少區間 ????int?end?=?intervals[0][1],?count?=?0; ????//?從第二個區間開始，判斷一下當前區間和前一個區間的結束時間 ????for?(int?i?=?1;?i?<?intervals.length;?i++)?{ ????????//?當前區間和前一個區間有重疊，即當前區間的起始時間小于上一個區間的結束時間，end記錄下兩個結束時間的最小值，把結束時間晚的區間刪除，計數加1。 ????????if?(intervals[i][0]?<?end)?{ ????????????end?=?Math.min(end,?intervals[i][1]); ????????????count++; ????????}?else?{ ????????????end?=?intervals[i][1]; ????????} ????} ????//?如果沒有發生重疊，根據貪婪法，更新?end?變量為當前區間的結束時間 ????return?count; ?? } ``` * 按照結束時間排序題目演變：在給定的區間中，最多有多少個區間相互之間是沒有重疊的？思路：假如求出了最多有 m 個區間是互相之間沒有重疊的，則最少需要將 n?m 個區間刪除才行。即，刪掉“害群之馬”，則剩下的就不會互相沖突了。為什么按照結束時間排序會有助于我們統計出沒有重疊的區間最大個數呢？舉例說明如下。假設今天有很多活動要舉行，每個活動都有固定的時間，選擇哪些活動，才能使參加的活動最多，然后在時間上不會互相重疊呢？如果我們按照活動的起始時間去挑選，某個活動雖然開始得早，但是很有可能會持續一整天，就沒有時間去參加其他活動了。如果按照活動的結束時間選，先挑那些最早結束的，就會盡可能節省出更多的時間來參加更多的活動。根據這個思路，這道題也可以按照結束時間排序處理，于是，區間的順序就是 {B, C, D, A}。實現：目標就是統計有多少個沒有重疊的情況發生。若當前的區間和前一個區間沒有重疊的時候，計數器加 1，同時，用當前的區間去和下一個區間比較。代碼實現 ``` int?eraseOverlapIntervals(int[][]?intervals)?{ ????if?(intervals.length?==?0)?return?0; ?? ????//?按照結束時間將所有區間進行排序 ????Arrays.sort(intervals,?(i1,?i2)?->?Integer.compare(i1[1],?i2[1])); ? ????//?定義一個變量?end?用來記錄當前的結束時間，count?變量用來記錄有多少個沒有重疊的區間? ????int?end?=?intervals[0][1],?count?=?1; ? ????//?從第二個區間開始遍歷剩下的區間?? ????for?(int?i?=?1;?i?<?intervals.length;?i++)?{ ????????//?當前區間和前一個結束時間沒有重疊，那么計數加?1，同時更新一下新的結束時間 ????????if?(intervals[i][0]?>=?end)?{ ????????????end?=?intervals[i][1]; ????????????count++; ????????} ????} ?? ????//?用總區間的個數減去沒有重疊的區間個數，即為最少要刪除掉的區間個數 ????return?intervals.length?-?count;? } ``` 關于區間的問題，LeetCode 上還有很多類似的題目，大家一定要去做做。 #### 例題分析三 LeetCode ?第 269 題，火星字典：現有一種使用字母的全新語言，這門語言的字母順序與英語順序不同。假設，您并不知道其中字母之間的先后順序。但是，會收到詞典中獲得一個不為空的單詞列表。因為是從詞典中獲得的，所以該單詞列表內的單詞已經按這門新語言的字母順序進行了排序。您需要根據這個輸入的列表，還原出此語言中已知的字母順序。示例 1 ``` 輸入: [?"wrt",?"wrf","er","ett",?"rftt"] 輸出: "wertf" ``` 示例 2 ``` 輸入: [?"z",?"x"] 輸出: "zx" ``` 示例 3 ``` 輸入: [?"z",??"x","z"]? 輸出: ""? ``` 解釋: 此順序是非法的，因此返回 ""。 * [ ] 解題思路首先，確定字符串排序方法。理解題意，關鍵是搞清楚給定的輸入字符串是怎么排序的？舉例：假如我們有這些單詞 bar，bat，algorithm，cook，cog，那么按照字符順序，應該怎么排呢？正確的排序應該是：algorithm bat bar cog cook。解法： * 逐位地比較兩個相鄰的字符串 * 第一個字母出現的順序越早，排位越靠前 * 第一個字母相同時，比較第二字母，以此類推注意：兩個字符串某個相同的位置出現了不同，就立即能得出它們的順序，無需繼續比較字符串剩余字母。求解示例 1 輸入是： ``` wrt wrf er ett rftt ``` 解法： 1. 比較以 w 開頭的字符串，它們是 wrt 和 wrf，之所以 wrt 會排在 wrf 之前，是因為 t 比 f 在火星字典里出現的順序要早。此時將這兩個字母的關系表達為 t -> f。 2. 比較 wrf 和 er，第一個字母開始不同，因此，得出 w 排在 e 之前，記為 w -> e。 3. 比較 er 和 ett，從第二個字母開始不一樣，因此，得出 r 排在 t 之前，記為 r -> t。 4. 比較 ett 和 rftt，從第一個字母開始不一樣，得出 e 排在 r 之前，記為 e -> r。梳理上述關系，得 t -> f，w -> e，r -> t，e -> r 拓撲排序得到正確順序：將每個字母看成是圖里的頂點，它們之間的關系就好比是連接頂點與頂點的變，而且是有向邊，所以這個圖是一個有向圖。最后對這個有向圖進行拓撲排序，就可以得出最終的結果。??? ? ? ? * [ ] 代碼實現包括兩大步驟，第一步是根據輸入構建一個有向圖；第二步是對這個有向圖進行拓撲排序。 ``` //?基本情況處理，比如輸入為空，或者輸入的字符串只有一個 String?alienOrder(String[]?words)?{ ????if?(words?==?null?||?words.length?==?0) ????????return?null; ????if?(words.length?==?1)?{ ????????return?words[0]; ????} ?? ????//?構建有向圖：定義一個鄰接鏈表?adjList，也可以用鄰接矩陣 ????Map<Character,?List<Character>>?adjList?=?new?HashMap<>(); ????for?(int?i?=?0;?i?<?words.length?-?1;?i++)?{ ????????String?w1?=?words[i],?w2?=?words[i?+?1]; ????????int?n1?=?w1.length(),?n2?=?w2.length(); ????????boolean?found?=?false; ???? ????????for?(int?j?=?0;?j?<?Math.max(w1.length(),?w2.length());?j++)?{ ????????????Character?c1?=?j?<?n1???w1.charAt(j)?:?null; ????????????Character?c2?=?j?<?n2???w2.charAt(j)?:?null; ????????????if?(c1?!=?null?&&?!adjList.containsKey(c1))?{ ????????????????adjList.put(c1,?new?ArrayList<Character>()); ????????????} ????????????if?(c2?!=?null?&&?!adjList.containsKey(c2))?{ ????????????????adjList.put(c2,?new?ArrayList<Character>()); ????????????} ????????????if?(c1?!=?null?&&?c2?!=?null?&&?c1?!=?c2?&&?!found)?{ ????????????????adjList.get(c1).add(c2); ????????????????found?=?true; ????????????} ????????} ????} ????Set<Character>?visited?=?new?HashSet<>(); ????Set<Character>?loop?=?new?HashSet<>(); ????Stack<Character>?stack?=?new?Stack<Character>(); ?? ????for?(Character?key?:?adjList.keySet())?{ ????????if?(!visited.contains(key))?{ ????????????if?(!topologicalSort(adjList,?key,?visited,?loop,?stack))?{ ????????????????return?""; ????????????} ????????} ????} ????StringBuilder?sb?=?new?StringBuilder(); ????while?(!stack.isEmpty())?{ ????????sb.append(stack.pop()); ????} ????return?sb.toString（）； ?? } //?將當前節點?u?加入到?visited?集合以及?loop?集合中。 boolean?topologicalSort(Map<Character,?List<Character>>?adjList,?char?u,? ????????????????????????Set<Character>?visited,?Set<Character>?loop,?Stack<Character>?stack)?{ ????visited.add(u); ????loop.add(u); ????if?(adjList.containsKey(u))?{ ????????for?(int?i?=?0;?i?<?adjList.get(u).size();?i++)?{ ????????????char?v?=?adjList.get(u).get(i); ? ????????????if?(loop.contains(v)) ????????????????return?false; ???????? ????????????if?(!visited.contains(v))?{ ????????????????if?(!topologicalSort(adjList,?v,?visited,?loop,?stack))?{ ????????????????????return?false; ????????????????} ????????????} ????????} ????} ????loop.remove(u); ?? ????stack.push(u); ????return?true; } ``` 用深度優先的方法進行拓撲排序，一定要借用下面三者。 1. visited 集合，用來記錄哪些頂點已經被訪問過。 2. stack 堆棧，從某個頂點出發，訪問完了所有其他頂點，最后才把當前的這個頂點加入到堆棧里。即，若要該點加入到 stack 里，必須先把跟它有聯系的頂點都處理完。舉例說明，如果我要學習課程 A，得先把課程 B，C 以及 D 都看完。 3. loop 集合，為了有效防止有向圖里出現環的情況。舉例說明如下。假如我們有這么一個有向圖。 ? ? * 從 A 開始對這個圖進行深度優先的遍歷，那么當訪問到頂點 D 的時候，visited 集合以及 loop 集合都是 {A, B, C, D}。 * 當從 D 繼續遍歷到 B 的時候，發現 B 已經在 loop 集合里。 * 因此得出結論，在這一輪遍歷中，出現了環。為什么不能單單用 visited 集合來幫助判斷呢？例如下面情況。 ? * 從 D 訪問 B 的時候，如果判斷因為 B 已經被訪問過了，于是得出這里就有一個環，顯然判斷錯誤。 * 當每一輪訪問結束后，都必須要把 loop 集合清空，才能把其他頂點也加入到堆棧里。 * 否則，當 D 遇到 B 的時候，也會認為這里有環出現，而提前終止程序，無法將它加入到堆棧中。 #### 例題分析四 LeetCode 第 772 題，基本計算器：實現一個基本的計算器來計算簡單的表達式字符串。說明： * 表達式字符串可以包含左括號 ( 和右括號 )，加號 + 和減號 -，非負整數和空格。 * 表達式字符串只包含非負整數， + ?- ?* ?/ 操作符，左括號 ( ，右括號 ) 和空格。整數除法需要向下截斷。示例 1： ``` "1 + 1" = 2 " 6-4 / 2 " = 4 "2×(5+5×2)/3+(6/2+8)" = 21 "(2+6×3+5- (3×14/7+2)×5)+3" = -12 ``` * [ ] 解題思路一：只有加號例題：若表達式里只有數字和加法符號，沒有減法，也沒有空格，并且輸入的表達式一定合法，那么應該如何處理？例如：1+2+10。解法：一旦遇到了數字就不斷地相加。代碼實現 ``` //?轉換，將字符串的字符放入到一個優先隊列中 int?calculate(String?s)?{ ????Queue<Character>?queue?=?new?LinkedList<>(); ????for?(char?c?:?s.toCharArray())?{ ????????queue.offer(c); ????} ? ????//?定義兩個變量，num?用來表示當前的數字，sum?用來記錄最后的和? ????int?num?=?0,?sum?=?0; ? ????//?遍歷優先隊列，從隊列中一個一個取出字符? ????while?(!queue.isEmpty())?{ ????????char?c?=?queue.poll(); ????????//?如果當前字符是數字，那么就更新?num?變量，如果遇到了加號，就把當前的?num?加入到?sum?里，num?清零 ????????if?(Character.isDigit(c))?{ ????????????num?=?10?*?num?+?c?-?'0'; ????????}?else?{ ????????????sum?+=?num; ????????????num?=?0; ????????} ????} ?? ????sum?+=?num;?//?最后沒有加號，再加一次 ????return?sum; ?? } ``` * [ ] 代碼擴展一如上，在返回 sum 之前，我們還進行了一次額外的操作：sum += num，就是為了要處理結束時的特殊情況。若在表達式的最后添加上一個”+”，也能實現同樣的效果，代碼實現如下。 ``` int?calculate(String?s)?{ ????Queue<Character>?queue?=?new?LinkedList<>(); ????for?(char?c?:?s.toCharArray())?{ ????????queue.offer(c); ????} ????queue.add('+');?//?在末尾添加一個加號 ?? ????while?(!queue.isEmpty())?{ ????????... ????} ????return?sum; } ``` 如上，在優先隊列的最后添加一個加號。 * [ ] 代碼擴展二若輸入的時候允許空格，如何處理？代碼實現如下。 ``` int?calculate(String?s)?{ ????... ????for?(char?c?:?s.toCharArray())?{ ????????if?(c?!=?'?')?queue.offer(c); ????} ????... } ``` 如上，在添加到優先隊列的時候，過濾到那些空格就好了。 * [ ] 解題思路二：引入減號例題：若表達式支持減法，應該怎么處理？例如：1 + 2 - 10。解法 1：借助兩個 stack，一個 stack 專門用來放數字；一個 stack 專門用來放符號。解法 2：將表達式看作 1 + 2 + (-10)，把 -10 看成一個整體，同時，利用一個變量 sign 來表示該數字前的符號，這樣即可沿用解法。解法 2 的具體操作如下。? ? ? ?? ? ? ? 代碼實現 ``` int?calculate(String?s)?{??? ????Queue<Character>?queue?=?new?LinkedList<>(); ????for?(char?c?:?s.toCharArray())?{ ????????if?(c?!=?'?')?queue.offer(c); ????} ????queue.add('+'); ?? ????char?sign?=?'+';?//?添加一個符號標志變量 ????int?num?=?0,?sum?=?0; ?? ????while?(!queue.isEmpty())?{ ????????char?c?=?queue.poll(); ????????if?(Character.isDigit(c))?{ ????????????num?=?10?*?num?+?c?-?'0'; ????????}?else?{ ????????????//?遇到了符號，表明我們要開始統計一下當前的結果了 ????????????if?(sign?==?'+')?{?//數字的符號是?+ ????????????????sum?+=?num; ????????????}?else?if?(sign?==?'-')?{?//?數字的符號是?- ????????????????sum?-=?num; ????????????} ?????? ????????????num?=?0; ????????????sign?=?c; ????????} ????} ????return?sum; } ``` * [ ] 解題思路三：引入乘除例題：若引入乘法和除法，如何處理？舉個例子：1 + 2 x 10。解法：要考慮符號的優先級問題，不能再簡單得對 sum 進行單向的操作。當遇到乘號的時候：sum = 1，num = 2，而乘法的優先級比較高，得先處理 2 x 10 才能加 1。對此，就把它們暫時記錄下來，具體操作如下。? ? ? ?? ? ? ? 代碼實現 ``` int?calculate(String?s)?{??? ????Queue<Character>?queue?=?new?LinkedList<>(); ????for?(char?c?:?s.toCharArray())?{ ????????if?(c?!=?'?')?queue.offer(c); ????} ????queue.add('+'); ?? ????char?sign?=?'+'; ????int?num?=?0; ?? ????//?定義一個新的變量?stack，用來記錄要被處理的數 ????Stack<Integer>?stack?=?new?Stack<>(); ?? ????while?(!queue.isEmpty())?{ ????????char?c?=?queue.poll(); ????????if?(Character.isDigit(c))?{ ????????????num?=?10?*?num?+?c?-?'0'; ????????}?else?{ ????????????if?(sign?==?'+')?{ ????????????????stack.push(num);?//?遇到加號，把當前的數壓入到堆棧中 ????????????}?else?if?(sign?==?'-')?{ ????????????????stack.push(-num);?//?減號，把當前數的相反數壓入到堆棧中 ????????????}?else?if?(sign?==?'*')?{ ????????????????stack.push(stack.pop()?*?num);?//?乘號，把前一個數從堆棧中取出，然后和當前的數相乘，再放回堆棧 ????????????}?else?if?(sign?==?'/')?{ ????????????????stack.push(stack.pop()?/?num);?//?除號，把前一個數從堆棧中取出，然后除以當前的數，再把結果放回堆棧 ????????????} ?????? ????????????num?=?0; ????????????sign?=?c; ????????} ????} ????int?sum?=?0; ???? ????//?堆棧里存儲的都是各個需要相加起來的結果，把它們加起來，返回總和即可 ????while?(!stack.isEmpty())?{ ????????sum?+=?stack.pop(); ????} ????return?sum; ?? } ``` * [ ] 解題思路四：引入小括號例題：如何支持小括號？解法：小括號里的表達式優先計算。先利用上面的方法計算小括號里面的表達式。當遇到一個左括號的時候，可以遞歸地處理；當遇到了右括號，表明小括號里面的處理完畢，遞歸應該返回。代碼實現 ``` //?在主函數里調用一個遞歸函數 int?calculate(String?s)?{??? ????Queue<Character>?queue?=?new?LinkedList<>(); ????for?(char?c?:?s.toCharArray())?{ ????????if?(c?!=?'?')?queue.offer(c); ????} ????queue.offer('+'); ?? ????return?calculate(queue); } int?calculate(Queue<Character>?queue)?{ ????char?sign?=?'+'; ????int?num?=?0; ????Stack<Integer>?stack?=?new?Stack<>(); ?? ????while?(!queue.isEmpty())?{ ????????char?c?=?queue.poll(); ????????if?(Character.isDigit(c))?{ ????????????num?=?10?*?num?+?c?-?'0'; ????????}? ????????//?遇到一個左括號，開始遞歸調用，求得括號里的計算結果，將它賦給當前的?num?? ????????else?if?(c?==?'(')?{ ????????????num?=?calculate(queue); ????????} ????????else?{ ????????????if?(sign?==?'+')?{ ????????????????stack.push(num); ????????????}?else?if?(sign?==?'-')?{ ????????????????stack.push(-num); ????????????}?else?if?(sign?==?'*')?{ ????????????????stack.push(stack.pop()?*?num); ????????????}?else?if?(sign?==?'/')?{ ????????????????stack.push(stack.pop()?/?num); ????????????} ?????? ????????????num?=?0; ????????????sign?=?c; ? ????????????//?遇到右括號，就可以結束循環，直接返回當前的總和????? ????????????if?(c?==?')')?{ ????????????????break; ????????????} ????????} ????} ?? ????int?sum?=?0; ????while?(!stack.isEmpty())?{ ????????sum?+=?stack.pop(); ????} ????return?sum; ?? } ``` #### 結語這節課講解了一些解決區間問題的方法，以及拓撲排序算法，最后實現了一個基本的計算器。注意：這些問題都是面試高頻題，但不要死記硬背，要通過理解其思想來達到融會貫通。