day1_slidingWindow

news/2024/5/20 16:05:11

一、滑动窗口模板

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。import java.util.HashMap;
import java.util.Map;public class Main {/* 滑动窗口算法框架 */public static void slidingWindow(String s) {// 用合适的数据结构记录窗口中的数据，根据具体场景变通// 比如说，我想记录窗口中元素出现的次数，就用 map// 我想记录窗口中的元素和，就用 intMap<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 进行窗口内数据的一系列更新// .../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时，可能导致超时System.out.printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (left < right && window needs shrink) {// d 是将移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 缩小窗口left++;// 进行窗口内数据的一系列更新// ...}}}public static void main(String[] args) {slidingWindow("your string here");}
}

在这里插入图片描述

背完模板后，还需要考虑什么？

1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？

2、什么时候窗口应该暂停扩大(满足了条件)，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？

3、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

1.最小覆盖子串

s是长字符串，t是短字符串
need.size() 是 t中不同字符的种类数，同样的valid 每加1表示的是一个字符被满足，而不是某个字符的数量匹配上了一次

/*** 求字符串 s 中包含字符串 t 所有字符的最小子串* @param s 源字符串* @param t 给定字符串* @return 满足条件的最小子串*/
public String minWindow(String s, String t) {// 用于记录需要的字符和窗口中的字符及其出现的次数Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();// 统计 t 中各字符出现次数for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);int left = 0, right = 0;int valid = 0; // 窗口中满足需要的字符个数// 记录最小覆盖子串的起始索引及长度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 扩大窗口right++;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c)))valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1}// 判断左侧窗口是否要收缩while (valid == need.size()) {// 更新最小覆盖子串if (right - left < len) {start = left;len = right - left;}// d 是将移出窗口的字符char d = s.charAt(left);// 缩小窗口left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d)))valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串return len == Integer.MAX_VALUE ?"" : s.substring(start, start + len);
}

在这里插入图片描述

在Java中，对于对象类型（如Integer、String等），我们通常使用equals()方法来判断它们的值是否相等，而不是使用等号==。

原因是，等号 == 在比较对象类型时，比较的是对象的引用（内存地址），而不是对象的实际值。也就是说，使用 == 来比较两个对象，只有当它们引用同一个对象时，才会返回true。

然而，equals()方法被设计用来比较对象的值是否相等。对于String类型，equals()方法已经被重写，用于比较两个字符串的内容是否相等。对于Integer类型，equals()方法也被重写，用于比较两个整数值是否相等。

因此，如果我们想要比较两个对象的值是否相等，应该使用equals()方法。例如，使用s1.equals(s2)来比较两个字符串s1和s2的内容是否相等。

需要注意的是，有些对象类型（如Integer、Character等）具有自动拆装箱的功能，可以直接使用等号==进行比较。这是因为Java会自动将基本类型转换为对应的包装类型，以便进行比较。但是，对于其他对象类型，我们仍然应该使用equals()方法来确保正确的比较

2.字符串的排列

class Solution {public boolean checkInclusion(String s1, String s2) {HashMap<Character, Integer> need = new HashMap<>();HashMap<Character, Integer> window = new HashMap<>();for(int i = 0; i < s1.length(); i++){char c = s1.charAt(i);need.put(c, need.getOrDefault(c, 0) + 1);}int left = 0,right = 0;int valid = 0;while(right < s2.length()){char c = s2.charAt(right);right++;if(need.containsKey(c)){window.put(c, window.getOrDefault(c, 0) + 1);if(window.get(c).equals(need.get(c)))valid++;}//判断左窗口是否要收缩while(right - left >= s1.length()){//在这里判断是否找到了合法的子串if(valid == need.size())return true;char d = s2.charAt(left);left++;if(need.containsKey(d)){if(window.get(d).equals(need.get(d)))valid--;window.put(d, window.getOrDefault(d, 0) - 1);}}}//未找到符合条件的子串return false;}
}

在这里插入图片描述

3.找出所有的字母异位词438

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。public List<Integer> findAnagrams(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 c = t.charAt(i);need.put(c, need.getOrDefault(c, 0) + 1);}int left = 0, right = 0;int valid = 0;List<Integer> res = new ArrayList<>(); // 记录结果while (right < s.length()) {char c = s.charAt(right);right++;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c))) {valid++;}}// 判断左侧窗口是否要收缩while (right - left >= t.length()) {// 当窗口符合条件时，把起始索引加入 resif (valid == need.size()) {res.add(left);}char d = s.charAt(left);left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d))) {valid--;}window.put(d, window.get(d) - 1);}}}return res;
}

4.最长无重复子串

int lengthOfLongestSubstring(String s) {Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0;int res = 0; // 记录结果while (right < s.length()) {char c = s.charAt(right);right++;// 进行窗口内数据的一系列更新window.put(c, window.getOrDefault(c, 0) + 1);// 判断左侧窗口是否要收缩while (window.get(c) > 1) {char d = s.charAt(left);left++;// 进行窗口内数据的一系列更新window.put(d, window.get(d) - 1);}// 在这里更新答案res = Math.max(res, right - left);}return res;
}