前文算法笔记
滑动窗口解决字串问题
首先滑动窗口是有模块的，在套模版之前需要明白以下四点
- 1.right指针扩大窗口，即加入字符时，应该更新哪些数据
- 什么条件下，窗口应该暂停扩大，开始移动left缩小窗口
- 当移动left缩小窗口，移除字符时更新哪些数据
- 我们需要的结果时在扩大窗口还是缩小窗口时进行更新
76.最小覆盖字串
- 我们有一个windows的滑动窗口，通过控制left和right指针的移动，最开始我们用一个need集合存放t字串中的每个字符，valid代表字串个数
- 具体操作就是right往右走，然后呢直到遇到valid满足，这个时候需要缩减窗口了，缩减窗口的时候要记录其结果
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer>need = new HashMap<>();
Map<Character,Integer>windows = new HashMap<>();
int left = 0;
int right = 0;
int start = 0;
int valid = 0;
int len = 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)){
windows.put(c,windows.getOrDefault(c,0)+1);
if(windows.get(c).equals(need.get(c))){
valid++;//代表字符串中有和字串一样的字符
}
}
//判断左侧窗口是否要进行收缩
while(valid==need.size()){
if(right-left < len){//更新长度，只记录最短的
start = left;
len = right-left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(need.get(d).equals(windows.get(d))){
valid--;
}
windows.put(d,windows.getOrDefault(d,0)-1);//代表windows中含字串的字符多一些
}
}
}
len = len==Integer.MAX_VALUE? 0:len;
return s.substring(start,start+len);
}
}
567.字符串的排列
- 这题同样也是字串问题，一看就是利用滑动窗口，与上一题不一样的在于这里是排列的字串，也就是我们要判断的就是windows中是否含有need，且它两长度要一致，代表着我们的这题的范围更小了
- 所谓的窗口伸长或者缩短，都是根据need.containsKey(d)，只有包含了才进行窗口的改变
class Solution {
public boolean checkInclusion(String s1, String s2) {
int sz = s2.length();
Map<Character,Integer>need = new HashMap<>();
Map<Character,Integer>window = new HashMap<>();
for(char c : s1.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
int left =0;
int right = 0;
int valid = 0;
while(right<sz){
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(valid==need.size()){
//字串包含s1的全部字符 且长度相等 即满足了题意
if(right-left == s1.length()){
return true;
}
//要移除的字符
char d = s2.charAt(left);
left++;
//此时也要更新window的值
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.getOrDefault(d,0)-1);
}
}
}
return false;
}
}
458.找到字符串中的字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character,Integer>windows = new HashMap<>();
HashMap<Character,Integer>need = new HashMap<>();
int left = 0;
int right = 0;
int valid = 0;
List<Integer>list = new ArrayList<>();
for(char c : p.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
while(right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
windows.put(c,windows.getOrDefault(c,0)+1);
if(windows.get(c).equals(need.get(c))){
valid++;
}
}
while(valid==need.size()){
if(right - left == p.length()){
list.add(left);//和判断不一样的是，我们只需要将其left加到List即可
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(windows.get(d).equals(need.get(d))){
valid--;
}
windows.put(d,windows.getOrDefault(d,0)-1);
}
}
}
return list;
}
}
3.无重复字符的最长字串
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer>windows = new HashMap<>();
int left = 0;
int right = 0;
int res = 0;
while(right<s.length()){
char c = s.charAt(right);
right++;
windows.put(c,windows.getOrDefault(c,0)+1);
//如果windows含当前的代表重复了，需要缩减窗口
if(windows.containsKey(c)){
while(windows.get(c)>1){
char a = s.charAt(left);
left++;
windows.put(a,windows.getOrDefault(a,0)-1);
}
res = Math.max(res,right-left);
}
}
return res;
}
}