2012搭建wordpress網(wǎng)站seo專員招聘
題目
?????????”最小覆蓋子串“問題,難度為Hard,題目如下:
????????給你兩個字符串 S 和 T,請你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中沒有這樣一個子串,則算法返回空串,如果存在這樣一個子串,則可以認為答案是唯一的。
? ? ? ? 比如輸入 S = "ADBECFEBANC",T = "ABC",算法應(yīng)該返回 "BANC"。
? ? ? ? 如果我們使用暴力解法,代碼大概是這樣的:
? ? ? ? for (int i = 0; i < s.size; i++) {
? ? ? ? ? ? ? ? for (int j = i + 1; j < s.size; j++) {
? ? ? ? ? ? ? ? ? ? ? ? if [i : j] 包含 t 的所有字母:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 更新答案
????????????????}
????????}
? ? ? ? 思路很簡單,但顯然不是我們想要的。
滑動窗口思路分析
? ? ? ? 1.我們在字符串 S 中使用雙指針中的左、右指針技巧,初始化 left = right = 0,把索引左閉右開區(qū)間 [left, right) 稱為一個”窗口“。
? ? ? ? 2.先不斷地增加 right 指針擴大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
? ? ? ? 3.此時,停止增加 right,轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中所有字符了)。同時,每次增加 left,都要更新一輪結(jié)果。
? ? ? ? 4.重復第2和第3步,直到 right 到達字符 S 的盡頭。
? ? ? ? 第2步相當于在尋找一個”可行解“,然后第3步在優(yōu)化這個”可行解“,最終找到最優(yōu)解,也就是最短的覆蓋子串。左、右指針輪流前進 ,窗口大小增增減減,窗口不斷向右滑動,這就是”滑動窗口“這個名字的來歷。
? ? ? ? 下面畫圖理解一下這個思路。needs 和 window 相當于計數(shù)器,分別記錄 T 中字符出現(xiàn)次數(shù)和”窗口“中的相應(yīng)字符的出現(xiàn)次數(shù)。
? ? ? ? 初始狀態(tài):
? ? ? ? 增加 right,直到窗口 [left, right)?包含了 T 中所有字符:
? ? ? ? 現(xiàn)在開始增加 left,縮小窗口 [left, right):
? ? ? ? 直到窗口中的字符串不再符合要求,left 不再繼續(xù)移動:
? ? ? ? 之后重復上述過程,先移動 right,再移動 left······直到 right 指針到達字符串 S 的末端,算法結(jié)束?,F(xiàn)在來看看滑動窗口代碼框架怎么用。
? ? ? ? 首先,初始化 window 和 need 兩個哈希表,記錄窗口中的字符和需要湊齊的字符:
????????Map<Character, Integer> need = new HashMap<>();
? ? ? ? Map<Character, Integer> window = new HashMap<>();
? ? ? ? for (int i = 0; i < t.length(); i++) {
? ? ? ? ? ? char key = t.charAt(i);
? ? ? ? ? ? need.put(key, need.getOrDefault(key, 0) + 1);
? ? ? ? }
? ? ? ? 然后,使用 left 和 right 變量初始化窗口的兩端,不要忘了,區(qū)間 [left, right) 是左閉右開的,所以初始情況下窗口沒有包含任何元素:
????????int left = 0, right = 0, valid = 0;
? ? ? ? while (right < s.length()) { // 開始滑動 }
? ? ? ? 其中,valid 變量表示窗口中滿足 need 條件的字符個數(shù),如果 valid 和 need.size 的大小相同,則說明窗口已滿足條件,已經(jīng)完全覆蓋了串 T。
? ? ? ? 現(xiàn)在開始套模板,只需要思考以下4個問題:
? ? ? ? 1.當移動 right 擴大窗口,即加入字符時,應(yīng)該更新哪些數(shù)據(jù)?
????????2.什么條件下,窗口應(yīng)該暫停擴大,開始移動 left 縮小窗口?
? ? ? ? 3.當移動 left 縮小窗口,即移出字符時,應(yīng)該更新哪些數(shù)據(jù)?
? ? ? ? 4.我們要的結(jié)果應(yīng)該在擴大窗口時還是縮小窗口時進行更新?
? ? ? ? 一般來說,如果一個字符進入窗口,應(yīng)該增加 window 計數(shù)器;如果一個字符移出窗口,應(yīng)該減少 window 計數(shù)器;當 valid 滿足 need 時應(yīng)該收縮窗口;收縮窗口的時候應(yīng)該更新最終結(jié)果。
? ? ? ? 下面是完整代碼:
package SlidingWindow;import java.util.HashMap;
import java.util.Map;// leetcode 017 最小覆蓋子串
public class MCS {public String slidingWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for (int i = 0; i < t.length(); i++) {char key = t.charAt(i);need.put(key, need.getOrDefault(key, 0) + 1);}int left = 0, right = 0, valid = 0; // valid 表示窗口中滿足 need 條件的字符個數(shù)// 記錄最小覆蓋子串的啟始索引及長度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是將要移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 進行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))) { // window[c] == need[c]valid++;}}/*** debug 輸出的位置***/System.out.println("window:(" + left + ", " + right + ")");/*********************/// 判斷左側(cè)窗口是否要收縮while (valid == need.size()) { // window need shrink —窗口需要收縮// 在這里更新最小覆蓋子串if (right - left < len) {start = left;len = right - left;}// d 是將要移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 進行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.containsKey(d)) {if (window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))) {valid--;}window.put(d, window.getOrDefault(d, 0) - 1);}}}// 返回最小覆蓋子串return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); // s.substring(start, start + len) == C++ 中的 s.substr(start, len)}public static void main(String[] args) {MCS mcs = new MCS();String str = mcs.slidingWindow("ADOBECODEBANC", "ABC");System.out.println(str);}}