高端大气的企业网站模板,安徽安庆,自我介绍html网页模板,广州投标平台力扣labuladong一刷day9滑动窗口共4题 文章目录 力扣labuladong一刷day9滑动窗口共4题一、76. 最小覆盖子串二、567. 字符串的排列三、438. 找到字符串中所有字母异位词四、3. 无重复字符的最长子串 一、76. 最小覆盖子串
题目链接#xff1a;https://leetcode.cn/problems/m…力扣labuladong一刷day9滑动窗口共4题 文章目录 力扣labuladong一刷day9滑动窗口共4题一、76. 最小覆盖子串二、567. 字符串的排列三、438. 找到字符串中所有字母异位词四、3. 无重复字符的最长子串 一、76. 最小覆盖子串
题目链接https://leetcode.cn/problems/minimum-window-substring/ 思路典型的滑动窗口题目使用一个map记录所必须的字符个数使用另外一个map去记录滑动窗口内部的need字符一旦need所需的个数都满足以后就开始缩小滑动窗口在缩小滑动窗口的过程中不断记录最小的窗口长度以及窗口的起始点并且在map不满足need时结束缩小窗口继续扩大窗口。
class Solution {public String minWindow(String s, String t) {MapCharacter, Integer need new HashMap();MapCharacter, Integer window new HashMap();int left 0, right 0, valid 0;int start 0, max Integer.MAX_VALUE;for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0)1);}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 (valid need.size()) {if (right - left max) {start left;max right-start;}char cl s.charAt(left);left;if (need.containsKey(cl)) {if (window.get(cl).equals(need.get(cl))) valid--;window.put(cl, window.get(cl)-1);}}}return max Integer.MAX_VALUE ? : s.substring(start, startmax);}
}二、567. 字符串的排列
题目链接https://leetcode.cn/problems/permutation-in-string/ 思路本题要求s1是s2子串的排列那就是要求s1与s2的子串长度要相等那就是我们只需要控制滑动窗口的长度等于子串长度即可长度相等时只要s1中的字符都出现了即可返回然后就是正常缩小窗口再扩大窗口。
class Solution {public boolean checkInclusion(String s1, String s2) {MapCharacter, Integer need new HashMap();MapCharacter, Integer window new HashMap();int left 0, right 0, valid 0;for (char c : s1.toCharArray()) {need.put(c, need.getOrDefault(c, 0) 1);}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 cl s2.charAt(left);left;if (need.containsKey(cl)) {if (window.get(cl).equals(need.get(cl))) valid--;window.put(cl, window.get(cl)-1);}}}return false;}
}三、438. 找到字符串中所有字母异位词
题目链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/ 思路和上一题基本差不多也是要求p与s的子串长度相等我们只需要控制窗口等于p的长度即可然后在其中判断。
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger list new ArrayList();MapCharacter, Integer need new HashMap();MapCharacter, Integer window new HashMap();int left 0, right 0, valid 0;for (char c : p.toCharArray()) {need.put(c, need.getOrDefault(c, 0)1);}while (right s.length()) {char cr s.charAt(right);right;if (need.containsKey(cr)) {window.put(cr, window.getOrDefault(cr, 0)1);if (window.get(cr).equals(need.get(cr))) valid;}if (right - left p.length()) {if (valid need.size()) {list.add(left);}char cl s.charAt(left);left;if (need.containsKey(cl)) {if (window.get(cl).equals(need.get(cl))) valid--;window.put(cl, window.get(cl)-1);}}}return list;}
}四、3. 无重复字符的最长子串
题目链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/ 思路求无重复字符串的最长子串只需要用map收集字符即可只要当前字符个数大于1即可开始缩小滑动窗口直到当前字符的个数不再大于1. 最大长度max的记录放在最后。
class Solution {public int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap();int left 0, right 0, max 0;while (right s.length()) {char c s.charAt(right);right;map.put(c, map.getOrDefault(c, 0)1);while (map.get(c) 1) {char cl s.charAt(left);left;map.put(cl, map.get(cl)-1);}max Math.max(max, right - left);}return max;}
}
