這節課繼續來看幾道面試中的難題:
* 回文對
* 至多包含 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 題,太平洋大西洋水流問題,建議大家課后去試試。
#### 結語
這節課講了三道比較難想的題目,至此已經把所有關于數據結構、算法、以及相關的題目做了講解,掌握好我們課上講過的知識點,一定會對你的面試準備有很大的幫助。
當然,要能在面試中取得理想的發揮,還是要看平時的練習是否足夠,不光在數量上,更要在質量上嚴格要求自己。
下節課將會分享一些面試準備中的方法和技巧。