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

這節課繼續來看幾道面試中的難題： * 回文對 * 至多包含 K 個不同字符的最長子串 * 接雨水 II #### 例題分析一 LeetCode ?第 336 題，回文對：給定一組唯一的單詞，找出所有不同的索引對 (i, j)，使得列表中的兩個單詞， words[i] + words[j] ，可拼接成回文串。示例 1 ``` 輸入: ["abcd","dcba","lls","s","sssll"] 輸出: [[0,1],[1,0],[3,2],[2,4]]? ``` 解釋: 可拼接成的回文串為 ["dcbaabcd","abcddcba","slls","llssssll"] 示例 2 ``` 輸入: ["bat","tab","cat"] 輸出: [[0,1],[1,0]] ``` 解釋: 可拼接成的回文串為 ["battab","tabbat"] * [ ] 解題思路：暴力法所謂回文，就是正讀和反讀都一樣的字符串，例如"leetteel"。檢查一個字符串是否是回文，方法如下。將給定的字符串翻轉，然后跟原字符串對比，看是否相等。但空間復雜度為 O(n) 。定義兩個指針 i、j，一個指向字符串的頭，一個指向字符串的尾巴，同時從兩頭進行檢查，一旦發現不相等就表明不是回文，一直檢查到兩個指針相遇為止。將上述方法 2 用代碼實現如下。 ``` boolean?isPalindrome(String?word,?int?i,?int?j)?{ ????while?(i?<?j)?{ ????????if?(word.charAt(i++)?!=?word.charAt(j--))?return?false; ????} ????return?true; ?? } ``` 代碼非常簡單，因此不作過多講解。回到例題本身，用暴力法怎么解。實現方法： * 先找出所有的兩兩組合 * 對每種組合進行排查，看看哪種組合可以構成回文。時間復雜度： * 假設一共有 n 個單詞，每個單詞的平均長度為 k，兩兩組合，有 P(n, 2) = n×(n - 1) 種； * 對組合的字符串進行回文檢查，需要 2k 的時間復雜度； * 最終的時間復雜度是：O(n2×k)。 **暴力法優化** 暴力法需要檢查哪些情況？進行回文檢查的時候，根據兩個字符串的長度不同的程度，假設組合字符串的長度分別為 k1、k2，那么會出現以下三種情況。 * k1 = k2 舉例：字符串 s1 = "abcd"，字符串 s2 = "dcba" 實現：同時從兩邊進行檢查，看看它們能否構成回文，構成回文的條件就是兩個指針相遇，或者同時掃描完兩個字符串。 * k1 > k2 舉例：s1 = "abcdefe"，s2 = "dcba" 實現：同時從兩頭進行檢查，由于 s2 的長度短，那么 s2 首先會被遍歷完畢，此時 s1 還剩下的部分必須要滿足回文。 * k1 < k2 舉例：s1 = "abcd"，s2 = "efedcba" 實現：跟第二種情況類似，同時從兩頭進行檢查，由于 s1 的長度短，s1 首先會被遍歷完畢，此時 s2 還剩下的部分必須滿足回文。 **暴力法如何優化？** 暴力法之所以那么慢，是因為它要對所有情況進行檢查。而對于 s1 = "abcd" ，s1 + s2 的組合構成回文的一個條件就是，s2 的最后一個字符必須是 a，如果 k2>=2，它最后兩個字符一定是 ba。不滿足條件的字符串，不需要理會。那么，如何能快速地知道哪些字符串以 a 結尾，哪些字符串以 ba 結尾呢？如果反看 s2 ，這個問題相當于，怎么能快速地找出所有以 a 開頭或者以 ab 開頭的字符串？第 2 節課里介紹的 Trie，正是快速查找以某個字符串開頭的數據結構。注意：此處要對每個字符串反著構建 Trie。 **Trie** 一個 Trie 一般都是由很多個 TrieNode 節點構成的，最普通的 TrieNode 節點一般有以下的結構。 ``` class?TrieNode?{ ????boolean?isEnd; ????HashMap<Character,?TrieNode>?children; ????TrieNode()?{ ????????isEnd?=?false; ????????children?=?new?HashMap<>(); ????} } ``` 其中， * children：數組或者集合，羅列出每個分支當中包含的所有字符 * isEnd：布爾值，表示該節點是否為某字符串的結尾由上可知，Trie 是一種通過字符鏈接起來的樹狀結構，且 Trie 一定有一個根節點 root，它的 children 集合包含了所有字符串的開頭那個字符。舉例：給定一系列字符串："ab”, "abc”, “abde", “bcd"，用 Trie 表示的結構如下。其中， * 字符作為鏈接每個節點的邊，這些字符也是哈希表里的 key。 * 這些 key 對應的 value 是節點，綠色的節點表示節點里的 isEnd 布爾值為 true，也就是這個節點表示了一個字符串的結束。 * 要利用這個 Trie 來查找所有以 b 字符開頭的字符串時，可以避開左邊三個以 a 字母開頭的字符串。 **構建 Tire** 將給定的字符串變成 "ba”，"cba”，“edba"，“dcb"，它們其實就是之前的字符串的翻轉。對它們逆序進行 Trie 的構建，也得出了相同的結構。為了能讓給定的字符串能組合成回文，再添加兩個字符串：”a“，”abc“，同時，把”dcb” 刪除，Trie 變成了下面的結構。就之前提到的三種情況來分析如何利用 Trie 判斷合并兩個字符串能否構成回文。基本上是同時遍歷字符串和Trie。 * k1 = k2，即兩個字符串的長度相同并且能夠構成回文舉例：s1 = “abc”，s2 = “cba”，s1+s2 = “abccba”。 1. 從 s1 的第一個字符 a 開始，Trie 里有記錄以 a 結尾的字符串，其他那些不是以 a 結尾的字符串不予考慮。 2. 第二個字符 b，那么從 a 節點開始，看看有沒有以 b 作為鍵值 key 的節點，有，繼續。 3. 第三個字符 c，在 Trie 里，從 b 指向的節點開始，看看有沒有以 c 作為鍵值的節點，有，繼續。那些不是以 c 作為鍵值的分支可以不必考慮。 4. 字符串遍歷結束，在 Trie 里，當前節點是 c 指向的節點。由于該節點恰好表示字符串“cba”的結束，因此，得出兩個字符串合在一起可以構成回文串。 * k1 > k2 ? 舉例：s1 = “abc”，s2 = “ba” ，s1+s2 =“abcba“。 * 從 s1 的第一個字符 a 開始，能從 Trie 里找到 a，于是繼續。 * 字符 b，也能找到，并且 b 指向的節點是一個綠色節點，即從 Trie 里找到了字符”ba“。 * 要能使 s1 + s2 構成回文，條件就是 s1 里剩下的部分也是回文，此時 s1 剩下的是字符 c，而字符 c 是回文，因此，”abc” 和 “ba”能構成回文串。 * k1 < k2 舉例：s1 = “a”，s2 = “ba”，s1+s2 =”aba”。當 s1 遍歷完畢后，Trie 來到了 b 節點，由于 b 也是回文，因此它們兩個也能構成回文串。對于情況一、三： 1. s1 字符串一定會被遍歷完畢 2. 遍歷完畢后，在 Trie 里所對應的節點 * 是 s2 中的最后一個字符； * 是 s2 的剩余字符 * 只要該剩余字符本身是回文，就可以給這個節點添加一個數組，用來記錄從該節點向后所有剩余能構成回文的字符串的下標即可。 ? 對于情況二： 1. 在 Trie 里，當遇到某個綠色節點，而它表示了某個字符串的結束，只要 s1 剩下的字符能構成回文即可。 2. 修改 isEnd，用 index 替代，來得到 Trie 里 s2 的下標。 * 當 index 為 -1 時，表示不是字符串的結束位置。 * 當是字符串的結束時，用 index 來記錄輸入字符串的下標即可。代碼實現 ``` //?修改?TrieNode?結構，用?index?替換?isEnd class?TrieNode?{ ????int?index; ????List<Integer>?palindromes; ????HashMap<Character,?TrieNode>?children; ????//?添加一個?palindromes?列表，用來記錄從該節點往下的能構成回文的所有輸入字符串的下標 ????TrieNode()?{ ????????index?=?-1; ????????children?=?new?HashMap<>(); ????????palindromes?=?new?ArrayList<>(); ????} } ``` 主函數代碼如下。 ``` List<List<Integer>>?palindromePairs(String[]?words)?{ ????List<List<Integer>>?res?=?new?ArrayList<>();?//?定義一個空的列表，用來記錄找到的配對 ?? ????TrieNode?root?=?new?TrieNode();?//?定義一個?Trie?的根節點?root ?? ????for?(int?i?=?0;?i?<?words.length;?i++)?{ ????????addWord(root,?words[i],?i); ????}?//?創建?Trie ?? ????for?(int?i?=?0;?i?<?words.length;?i++)?{ ????????search(words,?i,?root,?res); ????}//?利用?Trie，找出所有的配對 ????return?res; } ``` 創建 Tire 如下。 ``` //?創建?Trie?的時候，從每個字符串的末尾開始遍歷 void?addWord(TrieNode?root,?String?word,?int?index)?{ ????for?(int?i?=?word.length()?-?1;?i?>=?0;?i--)?{ ????????char?ch?=?word.charAt(i); ????????//?對于每個當前字符，如果它還沒有被添加到?children?哈希表里，就創建一個新的節點?? ????????if?(!root.children.containsKey(ch))?{ ????????????root.children.put(ch,?new?TrieNode()); ????????} ????????//?若該字符串從頭開始到當前位置能成為回文的話，把這個字符串的下標添加到這個?Trie?節點的回文列表里? ????????if?(isPalindrome(word,?0,?i))?{ ????????????root.palindromes.add(index); ????????} ???? ????????root?=?root.children.get(ch); ????} ???? ????//?當對該字符串創建完?Trie?之后，將字符串的下標添加到回文列表里，并且將它賦給?index ????root.palindromes.add(index); ????root.index?=?index; ?? } ``` 若該字符串從頭開始到當前位置能成為回文的話，把這個字符串的下標添加到這個 Trie 節點的回文列表里。例如，如果字符串是“aaaba”，由于我們從后面往前面遍歷，當遍歷到字符 b 的時候，發現 aaa 是回文，于是更新 b 所指向的那個節點，說該節點往下有一個字符串能構成回文。處理查找如下。 ``` //?處理查找，從頭遍歷每個字符串，然后從?Trie?里尋找匹配的字符串 void?search(String[]?words,?int?i,?TrieNode?root,?List<List<Integer>>?res)?{ ???? ????//?k1?>?k2，且?s1?剩下的字符能構成回文，就把這對組合添加到結果中 ????//?k1=k2?或?k1<k2，只需要把回文列表里的字符串都和?s1?組合即可???? ????for?(int?j?=?0;?j?<?words[i].length();?j++)?{ ????????if?(root.index?>=?0?&&?root.index?!=?i?&&? ????????????isPalindrome(words[i],?j,?words[i].length()?-?1))? ????????{ ????????????res.add(Arrays.asList(i,?root.index)); ????????} ?? ????????root?=?root.children.get(words[i].charAt(j)); ????????????if?(root?==?null)?return; ????} ???? ????for?(int?j?:?root.palindromes)?{ ????????if?(i?==?j)?continue; ????????res.add(Arrays.asList(i,?j)); ????} } ``` **復雜度分析** 利用 Trie，在創建和查找的過程中，最多會遇到 n×k 個節點，而且會進行回文檢查，所以整體的時間復雜度是：O(n×k×k)。如果字符串的字符個數是在一定范圍之內的，那么這個問題就可以優化成一個近乎于線性問題了。 #### 例題分析二 LeetCode 第 340 題：給定一個字符串 s ，找出至多包含 k 個不同字符的最長子串 T。示例 1 ``` 輸入: s = "eceba", k = 2 輸出: 3 ``` 解釋: 則 T 為 "ece"，所以長度為 3。示例 2 ``` 輸入: s = "aa", k = 1 輸出: 2 ``` 解釋: 則 T 為 "aa"，所以長度為 2。 * [ ] 解題思路：暴力法思路：找出所有的子串，然后逐一檢查是否最多包含 k 個不同的字符。實現：用一個哈希表或者哈希集合去統計。復雜度：O(n^2)。第 8 課講解了一道 LeetCode 的題目，給定一個字符串，找出無重復字符的最長子串。當時提出了一種比較聰明的辦法，能夠在 O(n) 的時間里找到答案。上述例題其實是它的另外一種擴展，可以運用相似的策略來進行。舉例：s = “eceba”，k = 2。實現過程如下。用兩個快慢指針：i 和 j，i 是慢指針，j 是快指針。一開始，兩個指針都指向字符串的開頭。另外，還需要一個哈希表來統計每個字符出現的個數，同時用來統計不同字符的個數。 1. 每次將快指針指向的字符添加到哈希表中，統計它出現的次數。第一個字符是 e，加入到 map 中。 2. map 的大小為 1，表明到目前為止出現了一個字符。由于 map 的大小還沒有超過 k，快指針向前移動一步。 3.?j 指向的字符是 c，同樣統計到 map 中，此時 map 的大小為 2，也沒有超過 k，快指針繼續移動。 4. 當前 j 指向的字符是 e，現在 e 出現了 2 次，但是 map 的大小還是 2，表明到目前為止只看到兩個不同的字符，即 e 和 c。 ? ? ? ?? ? 5. 繼續移動 j 指針，出現了新的字符 b，加入到 map 中。 6. 此時 map 的大小為 3，已經超過了 2，于是慢指針開始刪除字符，目的是為了控制住 map 的大小不超過 2。 7. 當把第一個字符刪除的時候，在 map 里更新 e 字符的計數，但是整個 map 的大小還是等于 3，繼續相同的操作。 ? ? ? ?? ? ? 8. c 的個數只有一個，直接把它從 map 里刪除掉。現在 map 的大小恢復正常，繼續移動快指針。 9. 當把 a 添加到 map 里后，map 的大小又超過了 2，于是移動慢指針，把它指向的字符從 map 中刪除掉。 10. 結束循環。 **代碼實現** * 初始化一個哈希表 map，用來統計所出現了的不同字符。 * 用 max 變量記錄最長的子串，其中子串最多包含 k 個不同的字符。 * 用快慢指針遍歷字符串。 * 將快指針指向的字符加入到 map 中，統計字符出現的次數。 * 如果發現 map 的大小超過了 k，那么就得開始不斷地將慢指針所指向的字符從 map 里清除掉。 * 首先獲取當前慢指針指向的字符。 * 將它在map中的計數減一。 * 一旦它的統計次數變成了 0，就可以把它從 map 中刪掉了。 * 接下來，慢指針繼續往前走。 * 當 map 的大小恢復正常了，統計一下當前子串的長度。 * 最后返回最大的子串長度。 ``` int?lengthOfLongestSubstringKDistinct(String?s,?int?k)?{ ????HashMap<Character,?Integer>?map?=?new?HashMap<>(); ????int?max?=?0; ?? ????for?(int?i?=?0,?j?=?0;?j?<?s.length();?j++)?{ ????????char?cj?=?s.charAt(j); ???? ????????//?Step?1.?count?the?character ????????map.put(cj,?map.getOrDefault(cj,?0)?+?1); ???? ????????//?Step?2.?clean?up?the?map?if?condition?doesn't?match ????????while?(map.size()?>?k)?{ ????????????char?ci?=?s.charAt(i); ?????? ????????????map.put(ci,?map.get(ci)?-?1); ?????? ????????????if?(map.get(ci)?==?0)?{ ????????????????map.remove(ci);?//?that?character?count?has?become?0 ????????????} ????????????i++; ????} ????//?Step?3.?condition?matched,?now?update?the?result ????max?=?Math.max(max,?j?-?i?+?1); ????} ?? ????return?max; } ``` * [ ] 復雜度分析快慢指針遍歷字符串一遍，時間復雜度為 O(n)。運用了一個 map來作統計，空間復雜度為 O(n)。 #### 例題分析三 LeetCode 第 407 題：給定一個 m x n 的矩陣，其中的值均為正整數，代表二維高度圖每個單元的高度，請計算圖中形狀最多能接多少體積的雨水。說明：m 和 n 都是小于 110 的整數。每一個單位的高度都大于 0 且小于 20000。 ? 示例：給出如下 3x6 的高度圖: ``` [ ??[1,4,3,1,3,2], ??[3,2,1,3,2,4], ??[2,3,3,2,3,1] ] ``` 返回 4。下雨前的高度圖 [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]。下雨后，雨水將會被存儲在這些方塊中，總的接雨水量是 4。 * [ ] 解題思路一：從內向外基本情況舉例：假如有一個點高度是 0，而它四周的柱子的高度分別是 1，2，3，4。解法：中間的那個位置最多能接高度為 1 的水，因為它的四周最矮的柱子是 1。擴展情況舉例：假設現在 0 的周圍是如下情況，那么 0 那個位置能接水的高度還是 1 嗎？答案應該是 4。總結思路：對于每個點，都要不斷地往外去尋找那個高過自己的最矮的柱子。假設在平面上，一共有 n 個點，按照這樣的算法去計算所有的點的接水高度，復雜度是 O(n^3)。 * [ ] 解題思路二：從外向內為了提高效率，采用“農村包圍城市”的策略，從外面往里面進行計算。者是因為，每個點都必須找到最外圍的高度，否則無法確定它能接多少雨水。既然如此，為什么不從最外面開始呢？即，每一次我們都從外面最矮的開始，慢慢地往里面計算。以上述例子說明。 1. 最外圍開始，而最外圍的方塊無法承載雨水。 2. 從最外圍的高度中選擇最矮的柱子，先對它的鄰居進行處理。這是因為決定能夠接多少雨水并不是由周圍最高的柱子決定，而是由最矮的決定。 3. 高度 4 是最矮的，于是對其做 BFS，它的鄰居是高度為 2 的方塊。 4. 由于 2 小于 4，2 的位置能夠接納高度為 2 的雨水，于是這個位置上的高度就變成了 4。 5. 還是從最矮的點出發，還是 4，它的鄰居是 0，于是 0 所能接的雨水高度就是 4。 6. 還是 4 是最矮，可以更新它周圍的點在接了雨水后的高度。那么，如何快速知道接下來哪個高度最矮呢？可以用優先隊列來提高速度。 **代碼實現** 代碼實現如下，為了配合優先隊列的操作，定義一個 Cell 類，用來保存每個方塊的坐標以及接了雨水后的高度。 ``` class?Cell?{ ????int?row; ????int?col; ????int?height; ?? ????public?Cell(int?row,?int?col,?int?height)?{ ????????this.row?=?row; ????????this.col?=?col; ????????this.height?=?height; ????} } ``` 首先對輸入進行一些基本的判斷。用變量 m 和 n 分別表示輸入矩陣的行數和列數。定義一個優先隊列或者最小堆，按照每個方塊接雨水后的高度排列。初始化優先隊列的時候，把矩形的外圍四個邊上的方塊都加入到優先隊列中。進入 while 循環，開始進行 BFS。每次，從優先隊列中取出高度最矮的方塊。從四個方向擴散。該方向上的鄰居方塊能接多少雨水，取決于它是否低于當前的方塊了。同時，將新方塊加入到優先隊列中。最后返回承接雨水的總量。 ``` public?int?trapRainWater(int[][]?heights)?{ ????//?Sanity?check ????if?(heights?==?null?||?heights.length?==?0?||?heights[0].length?==?0)?{ ????????return?0; ????} ?? ????int?m?=?heights.length; ????int?n?=?heights[0].length; ?? ????PriorityQueue<Cell>?queue?=?new?PriorityQueue(new?Comparator<Cell>()?{ ????????public?int?compare(Cell?a,?Cell?b)?{?return?a.height?-?b.height;?} ????}); ?? ????boolean[][]?visited?=?new?boolean[m][n]; ?? ????//?Initially,?add?all?the?Cells?which?are?on?borders?to?the?queue. ????for?(int?i?=?0;?i?<?m;?i++)?{ ????????visited[i][0]?=?true; ????????visited[i][n?-?1]?=?true; ????????queue.offer(new?Cell(i,?0,?heights[i][0])); ????????queue.offer(new?Cell(i,?n?-?1,?heights[i][n?-?1])); ????} ?? ????for?(int?j?=?0;?j?<?n;?j++)?{ ????????visited[0][j]?=?true; ????????visited[m?-?1][j]?=?true; ????????queue.offer(new?Cell(0,?j,?heights[0][j])); ????????queue.offer(new?Cell(m?-?1,?j,?heights[m?-?1][j])); ????} ?? ????//?From?the?borders,?pick?the?shortest?cell?visited?and?check?its? ????//?neighbors: ????//?If?the?neighbor?is?shorter,?collect?the?water?it?can?trap?and?update? ????//?its?height?as?its?height?plus?the?water?trapped. ????//?Add?all?its?neighbors?to?the?queue. ????int[][]?dirs?=?{{-1,?0},?{1,?0},?{0,?-1},?{0,?1}}; ?? ????int?total?=?0; ????while?(!queue.isEmpty())?{ ????????Cell?cell?=?queue.poll(); ????????for?(int[]?dir?:?dirs)?{ ????????????int?row?=?cell.row?+?dir[0]; ????????????int?col?=?cell.col?+?dir[1]; ????????????if?(row?>=?0?&&?row?<?m?&&?col?>=?0?&&?col?<?n?&&?!visited[row][col]) ????????????{ ????????????????visited[row][col]?=?true; ????????????????total?+=?Math.max(0,?cell.height?-?heights[row][col]); ????????????????queue.offer( ????????????????????new?Cell(row,?col,?Math.max(heights[row][col],?cell.height)) ????????????????); ????????????} ????????} ????} ????return?total; ?? } ``` **復雜度分析** 假設一共有 m 行 n 列，那么一共有 m×n 個方塊。對于每個方塊，都有可能會進行優先隊列的操作，而優先隊列的大小為 m + n，加上初始化優先隊列的操作時間，因此，整體的時間復雜度為?O(m + n) + O(m×n×log(m + n)) = O(m×n×log(m + n))。由上可知，將復雜度下降了一個維度。建議：對于這種在 BFS 中運用“農村包圍城市”的策略，LeetCode 上還有一道題，第 417 題，太平洋大西洋水流問題，建議大家課后去試試。 #### 結語這節課講了三道比較難想的題目，至此已經把所有關于數據結構、算法、以及相關的題目做了講解，掌握好我們課上講過的知識點，一定會對你的面試準備有很大的幫助。當然，要能在面試中取得理想的發揮，還是要看平時的練習是否足夠，不光在數量上，更要在質量上嚴格要求自己。下節課將會分享一些面試準備中的方法和技巧。