算法Day06-算法研習指導之滑動視窗

滑動視窗

基本概念
最小覆寫子串
字母異位詞
無重複字元的最長子串
滑動視窗技巧總結

滑動視窗: 是進階雙指針技巧的算法架構,涉及字元串比對問題
滑動視窗使用的資料結構:
- unordered_map : 哈希表
  - 包含一個方法count(key), 相當于containsKey(key). 可以判斷key是否存在
- map[key] :
  - 可以使用方括号通路鍵對應的值map[key]. 需要注意,如果該key不存在,會自動建立這個key, 并且将map[key] 指派為0
  - map[key]++ 相當于Java的map.put(key, map.getOrDefault(key, 0) + 1)

題目: 要在S(source) 中找到包含T(target) 中全部字母的一個子串,這個子串一定要是所有子串中最短的
直接法求解的代碼:

for (int i = 0; i < s.size(); i++):
	for (int j = i + 1; j < s.size(); j++):
		if s[i : j] 包含 t 的所有字母:
			更新結果

思路簡單直接,但是這個算法的時間複雜度肯定大于O(N2) 了
滑動視窗算法思路: 尋找一個可行解,然後優化這個可行解,最終找到最優解.左右指針輪流前進,視窗大小增增減減,不斷向右滑動
- 在字元串S中使用雙指針中的左右指針技巧,初始化left = right = 0, 将索引閉區間[left,right]作為一個 [視窗]
- 首先不斷增加right指針來擴大視窗 [left, right], 直到視窗中的字元串符合包含T中的所有字元的要求
- 然後,停止增加right, 通過不斷增加left指針縮小視窗 [left,right], 直到視窗中的字元串不再符合包含T中的所有字元的要求.同時,每次增加left, 都要更新一輪結果
- 重複以上兩個步驟,直到right到達S的盡頭
滑動視窗算法僞碼架構:

String s, t;
int left = 0, right = 0;
// res是符合要求的最小覆寫子串
String res = s

/*
 * 在s中尋找t的最小覆寫子串
 */
 while (right < s.size()) {
 	// window是對應的滑動視窗,即子串s[left,right]
 	window.add(s[right]);
 	right++;
 	while (window 符合要求) {
 		// 如果這個視窗的子串更短,則更新res
 		res = minLen(res, window);
 		window.remove(s[left]);
 	}
 }
 return res;

如何判斷window中,也就是子串s[left,right]是否符合要求,是否包含t的所有字段:
- 可以使用兩個哈希表當作計數器解決
  - 使用一個哈希表needs記錄字元串t中包含的字元及出現次數
  - 使用另一個哈希表window記錄目前 [視窗] 中包含的字元及出現的次數
- 如果window包含所有needs中的鍵,并且這些鍵對應的值都大于等于needs中的值,那麼目前視窗就符合要求,就可以開始移動left指針
滑動視窗算法架構優化:

String s, t;
int left = 0, right = 0
String res = s;

/*
 * 建立兩個hash表作為字元的計數器
 */
 unordered_map<char, int> window;
 unordered_map<char, int> needs;
 for (Char c : t) needs[c]++;

// 記錄window中符合要求的字元的個數
int match = 0;

/*
 * 在s中尋找t的最小覆寫子串
 */
 while (right < s.size()) {
 	char r = s[right]
 	if (needs.count(r)) {
 		// 如果r在needs中,則将r加入window
 		window[r]++;
 		if (window[r] == needs[r]) {
 			// 字元串r出現的次數符合要求
 			match++;
 		}
	}
	right++;
	
	// window中的字元串是符合要求的最小覆寫子串
	while(match == needs.size()) {
		res = minLen(res, window);
		char l = s[left];
		if (needs.count(l)) {
			// 如果l在needs中,則将l移出window
			window[l]--;
			if (window[l] < needs[l]) {
				// 字元串l出現的次數不符合要求
				match--;
			}
		}
		left++
	}
 }
 return res;

完整代碼:

String minWindow(String s, String t) {
	// 記錄最短子串的開始位置和長度
	int start = 0, min_len = INIT_MAX;
	int left = 0, right = 0;

	// 建立兩個Hash表作為字元的計數器
	unordered_map<char, int> window;
	unordered_map<char, int> needs;
	for (char c : t) need[c]++;  

	// 記錄符合要求的字元個數
	int match = 0;
	
	// 在s中尋找t的最小覆寫子串
	while (right < s.size()) {
		char r = s[right];
		if (needs.count(r)) {
			window[r]++;
			if (window[r] == needs[r]) {
				match++;
			}
		}
		right++;
		
		while (match == s.size()) {
			if (right - left < minLen) {
				// 如果滑動視窗的長度小于最小長度,則更新最小長度
				start = left;
				minLen = right - left;
			}
			char l = s[left];
			if (needs.count(l)) {
				window[l]--;
				if (window[l] < needs[l]) {
					match--
				}
			}
			left++;	
		}
	}
	return minLen == INIT_MAX ? "" : s.substr(start, minLen);	
}

算法的時間複雜度為O(M + N),M和N分别是字元串S和T的長度
- 因為首先用for循環周遊了字元串T來初始化needs. 時間為O(N)
- 之後的兩個循環最多執行2M次,時間複雜度為O(M). 因為while循環的次數就是雙指針left和right走過的總路程

題目: 尋找字母相同,長度相同的子串

vector<int> findAnagrams(String s, String t) {
	// 使用數組記錄答案
	vector<int> res;
	int left = 0, right = 0;
	 
	// 建立兩個Hash表作為字元的計數器
	unordered_map<char, int> needs;
	unordered_map<char, int> window;
	 
	// 記錄要求比對的字元的個數
	int match = 0;

	while (right < s.size()) {
		char r = s[right];
		if (needs.count(r)) {
			window[r]++;
			if (window[r] == needs[r]) {
				match++;
			}
		}
		right++;

		while (match == s.size()) {
			// 如果比對的字元串和要求的長度相同則加入結果
			if (right - left = t.size) {
				res.push_back(left)
			}
			char l = s[left];
			if (needs.count(left)) {
				window[l]--;
				if (window[l] < needs[l]) {
					match--;
				}
			}
			left++
		}
	}
	return res;
}

子串相關問題,首先想到使用滑動視窗技巧
使用window作為計數器記錄視窗中字元出現次數,然後向右移動right, 當window中出現重複字元時,開始移動left縮小視窗.重複執行:

int lengthOfLongestSubstring(String s) {
	int left = 0, right = 0;
	
	// 建立一個Hash表作為字元計數器
	unordered_map<char, int> window;

	// 記錄字元串的長度
	int res = 0;

	while (right < s.size()) {
		char r = s[right];
		window[r]++;
		right++;
		// 如果window中出現重複字元,則開始縮小window視窗
		while (window[r] > 1) {
			char l = s[left];
			window[l]--;
			left++;
		}
		// 每次移動right時,更新res值
		res = max(res, right - left);
	}
	return res;
}

因為要求的是最長子串,是以需要在每次移動right增大視窗時更新res

滑動視窗解題架構:

int left = 0, right = 0;
while (righ < s.size()) {
	window.add(s[right]);
	right++;

	while (valid) {
		window.remove(s[left]);
		left++;
	}
}

def minWindow(self, s : str, t : str) -> str:
	# 字元串開始位置和長度
	start, min_len = 0, float('Inf')
	left, right = 0, 0
	res = s
 
	# 兩個計數器
	needs = Counter(t)
	# defaultdict在通路的key不存在的時候會傳回預設值0
	window = collections.defaultdict(int)
	 
	# 記錄比對要求的字元的個數
	match = 0
	
	while right < len(s):
		r = s[right]
		if needs[r] > 1:
			window[r] += 1
			if window[r] == needs[r]:
				match += 1
		right += 1
		
		while match = len(needs):
			if right - left < min_len:
				start = left
				min_len = right - left
			l = s[left]
			if needs[l] > 0:
				window[l] -= 1
				if window[l] < needs[l]:
					match -= 1
			left -= 1
	return s[start : start + min_len] if min_len != float("Inf") else ""

算法Day06-算法研習指導之滑動視窗

滑動視窗

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器