labuladong算法学习进展

学习目标：

• labuladong的算法秘籍学习
• csdn记录学习进展
• 76.最小覆盖子串

---

学习内容：

1. 数组
2. 链表
3. 前缀和
4. 差分数组
5. 双指针

---

学习时间：

• 周一至周五早上 9 点—10点

---

学习进展：

• [] 最小覆盖子串

2022年4月24日

• 11点04分。数组、矩阵的前缀和
• 11点17分。差分数组。公交车载客问题。

双指针分为左右指针、快慢指针两类

• 双指针，有序链表排序。
• 二叉堆，k个有序链表排序
• 快慢指针，环判断，环起点查找，链表中点查找
• 双指针判断两个链表是否相交，p1 遍历链表AB，p2遍历链表 BA，p1和p2最后会同时达到相交节点c1。
• 快慢指针原地修改数组，删除有序数组重复元素。
• 双指针寻找字符串中的最长回文子字符串

labuladong滑动窗口算法框架

/* 滑动窗⼝算法框架 */
void slidingWindow(string s, string t) {
	unordered_map<char, int> need, window;
 	for (char c : t) need[c]++;
 
 	int left = 0, right = 0;
 	int valid = 0; 
 	while (right < s.size()) {
 		// c 是将移⼊窗⼝的字符
 		char c = s[right];
 		// 增⼤窗⼝
 		right++;
 		// 进⾏窗⼝内数据的⼀系列更新
 		...
 		/*** debug 输出的位置 ***/
 		printf("window: [%d, %d)\n", left, right);
 		/********************/
 
 		// 判断左侧窗⼝是否要收缩
 		while (window needs shrink) {
 			// d 是将移出窗⼝的字符
 			char d = s[left];
 			// 缩⼩窗⼝
 			left++;
 			// 进⾏窗⼝内数据的⼀系列更新
 			...
 		}
 	}
}