机试日志

Posted on

滑动窗口

滑动窗口属于双指针算法中的一种。

重要的问题

  1. 窗口内是什么？
  2. 如何移动窗口的起始位置?
  3. 如何移动窗口的结束位置？

模板题

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

​ 窗口：　满足其和大于target

​

​ 起始位置前移的条件：　如果当前窗口的和大于target时，需要往移(缩小窗口)

​ 结束位置前移的条件： 用于遍历数组，扩大窗口

1
2
3
4
5
6
7
while( sum > s ){//如果是满足要求的窗口
	int temp_len = right-left+1;
	if(ans_len>temp_len){  //即使更新长度，保存最小的符合要求的长度
			ans_len = temp_len;
	}
	sum-=num[left++];　//缩小窗口
}

76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

​ 示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

示例 2：

输入：s = “a”, t = “a”
输出：”a”

思路完全同上面相同。 不过这里窗口的要求是要能够覆盖字符串 t,如何判断呢？

方法１：暴力查询，失败，超时，因为会存在多个相同的字母

方法２： 使用unordered_map<>统计每个字符串的长度(==不得不说自己真的是弱ji，关于string的stl函数不是很熟练)

此次debug：

  • String的使用substr(pos,len)　得到 str[pos,pos+len) 子串
    • str.find(ch)得到的是ch在str的下标，否则返回
    • str.erase(pos,len)，删除str[pos,pos+len)
  • 关于边界问题,第一个判断ss.empty() ,　还有一个就是right边界判断(我之前是用while写，改了好久，还是要固定思路，风格规范）
  • 还有无解情况的处理，就是如果此时不存在解，此时ans_left=ans_right =0;需要用flag标记一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
private:
    bool isTrue(unordered_map<char,int>& ss,unordered_map<char,int>& tt){
        if(ss.empty()){
            return false;
        }
        for(auto ptr=tt.begin();ptr!=tt.end();ptr++){
            if(ss[ptr->first]<ptr->second){ //存在一个不能覆盖，map的使用也不是很熟，判断mymap[mykey]，如果此时mykey不存在，mymap[mykey]访问得到的是默认值
                return false;
            }
        }
        return true;
    }
public:
       string minWindow(string s, string t) {
        int flag = false;
        unordered_map<char,int>ss;
        unordered_map<char,int>tt;
        for(auto jj : t){
            tt[jj]++;
        }
        int res_len=INT32_MAX;
        int res_left=0;
        int res_right=0;
        int left =0;
        int right =0;
        while(left<s.size() && right<s.size()){
            ss[s[right++]]++; //
            while(isTrue(ss,tt)){
                flag=true;
                int len = right-left+1;
                if(res_len>len){
                    res_len=len;
                    res_left=left;
                    res_right=right;
                }
                ss[s[left++]]--; //
            }
        }
        if(flag)
            return s.substr(res_left,res_right-res_left+1);
        else
            return "";
    }
};