LeetCode刷题笔记8.19-8.24
76.最小覆盖子串(8.19)
算法常见技巧——滑动窗口
- 滑动窗口即维护一个窗口(特定数据结构)，来替代暴力遍历子结构这种“笨办法”
- 窗口所涉及到的元素由left和right两个指针选定，选定范围从(left,right]开始，随着right指针向后遍历，寻找符合题意的某个可行解（指针遍历过程中来更新标记变量，进而判断是否达到可行性）left向后遍历则是在达到可行条件后优化该解，前提是将当前可行解记录下来。
- 该技巧涉及到的几个coder需要考虑的点：
- 什么时候应该移动 right 扩大窗口？
- 窗口加入字符时，应该更新哪些标记变量？（目的是接近题意可行解）
- 什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？
（该问题一般回答是 当寻找到一个可行解后） - 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
（在收缩窗口时更新最终结果）
- 滑动窗口大致框架：
void slidingWindow(String s) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 如果我想记录窗口中的元素和，就可以只用一个 int
Object window = ...
int left = 0, right = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c)
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
// *** debug 输出的位置 ***
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
printf("window: [%d, %d)\n", left, right);
// ***********************
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d)
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...(与扩大窗口时的操作对称）
}
}
}
【针对这道题】：
- 关于hashMap：
1)HashMap 中的元素实际上是对象，一些常见的基本类型可以使用它的包装类，基本类型对应的包装类表如下：
| 基本类型 | 引用类型 |
| boolean | Boolean |
| byte | Byte |
| short | Short |
| int | Integer |
| long | Long |
| char | Character |
2）向hashmap中插入一条记录put(key,value);
// 创建 HashMap 对象 Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");
3）从hashmap中取出一条记录 get(key);
System.out.println(Sites.get(3));
4）删除hashmap中的某一条记录 remove(key)
Sites.remove(4);
System.out.println(Sites);
5）计算 HashMap 中的元素数量可以使用 size() 方法
6) 如果只想获取 key，可以使用 keySet() 方法，返回所有key，相同的类型可以使用for-each来遍历；可以通过 get(key) 获取对应的 value，如果你只想获取 value，可以使用 values()
5. getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值hashmap.getOrDefault(Object key, V defaultValue);
567. 字符串的排列(8.21)
- 经过这两道题总结出了滑动窗口应用的规律：
- 题目中要求在大部分中遍历搜索小部分的情况
- 题目中对小部分的长度/元素限制（隐含的词语修饰例如：“子串”、“排列”、“最长最短子串”、“元素和最大最小”）
- 题目中的要求对应上面所提到的模板应用中需要考虑的几个边界条件
3.无重复字符的最长子串(8.22)
- 这道题与上面两道题有一个判断条件存在差别：
- 移动left指针的时机并非在刚好满足题意时，而是在子串中一旦存在重复字符时将字符清除
- 相应地在更新统计变量时应该是在left移动过后，产生暂时的可行解时更新