算法专题：滑动窗口

参考练习习题总集

文章目录

3. 无重复字符的最长子串
30. 串联所有单词的子串
76. 最小覆盖子串
187. 重复的DNA序列
219. 存在重复元素 II
220. 存在重复元素 III
396. 旋转函数
424. 替换后的最长重复字符
438. 找到字符串中所有字母异位词

滑动窗口太简单了，没啥说的自己做吧。

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size()==0) return 0;
        unordered_map<char,int> zd;zd[s[0]]=0;int max_len=1;
        for (int i=1;i<s.size();i++)
            if (zd.find(s[i])==zd.end()) zd[s[i]]=i;
            else
            {
                int x=my_min(zd);if (i-x>max_len) max_len=i-x;
                dlt(zd,zd[s[i]]);zd[s[i]]=i;
            }
        if (zd.size()>max_len) max_len=zd.size();
        return max_len;
    }
    int my_min(unordered_map<char,int> & zd)
    {
        int x=5*pow(10,4)+1;
        for (unordered_map<char,int>::iterator zz=zd.begin();zz!=zd.end();zz++)
            if (zz->second<x) x=zz->second;
        return x;
    }
    void dlt(unordered_map<char,int> & zd,int x)
    {
        vector<char> lt;
        for (unordered_map<char,int>::iterator zz=zd.begin();zz!=zd.end();zz++)
            if (zz->second<x) lt.push_back(zz->first);
        for (vector<char>::iterator zz=lt.begin();zz!=lt.end();zz++)
            zd.erase(*zz);
    }
};

30. 串联所有单词的子串

class Solution {
public:
    int word_len;unordered_map<string,int> zd;
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        int length=words.size()*words[0].size();
        if (s.size()<length) return result;
        unordered_map<char,int> zd1,zd2;
        for (int i=0;i<words.size();i++)
            for (int j=0;j<words[i].size();j++)
            {
                if (zd1.find(words[i][j])==zd1.end()) zd1[words[i][j]]=0;
                zd1[words[i][j]]+=1;
            }
        for (int i=0;i<length;i++)
        {
            if (zd2.find(s[i])==zd2.end()) zd2[s[i]]=0;
            zd2[s[i]]+=1;
        }
        word_len=words[0].size();
        for (int i=0;i<words.size();i++)
        {
            if (zd.find(words[i])==zd.end()) zd[words[i]]=0;
            zd[words[i]]+=1; 
        }
        string temp;
        temp=s.substr(0,length);
        if (zd1==zd2 and func(temp,zd)) result.push_back(0);
        for (int i=1;i<s.size()-length+1;i++)
        {
            zd2[s[i-1]]-=1;if (zd2[s[i-1]]==0) zd2.erase(s[i-1]);
            if (zd2.find(s[i+length-1])==zd2.end()) zd2[s[i+length-1]]=0;zd2[s[i+length-1]]+=1;
            temp=s.substr(i,length);
            if (zd1==zd2 and func(temp,zd)) result.push_back(i);
        }
        return result;
    }
    bool func(const string & s,unordered_map<string,int> zd)
    {
        for (int i=0;i<s.size();i+=word_len)
        {
            string temp=s.substr(i,word_len);
            if (zd.find(temp)==zd.end()) return false;
            zd[temp]-=1;if (zd[temp]==0) zd.erase(temp);
        }
        return true;
    }
};

76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        string result;
        unordered_map<char,int> zd;
        for (int i=0;i<t.size();i++)
        {
            if (zd.find(t[i])==zd.end()) zd[t[i]]=0;
            zd[t[i]]+=1;
        }
        vector<pair<char,int>> lb;
        for (int i=0;i<s.size();i++)
            if (zd.find(s[i])!=zd.end())
                lb.push_back({s[i],i});
        if (lb.size()<t.size()) return result;
        for (int i=0;i<t.size();i++)
            zd[lb[i].first]-=1;
        int l=0,r=t.size();
        while (!check(zd))
        {
            if (r>=lb.size()) return result;
            zd[lb[r].first]-=1;r+=1;
        }
        while (zd[lb[l].first]+1<=0)
        {
            zd[lb[l].first]+=1;l+=1;
        }
        result=s.substr(lb[l].second,lb[r-1].second-lb[l].second+1);
        while (1)
        {
            zd[lb[l].first]+=1;l+=1;
            while (zd[lb[l-1].first]>0)
            {
                if (r>=lb.size()) return result;
                zd[lb[r].first]-=1;r+=1;
            }
            if (lb[r-1].second-lb[l].second+1<result.size())
                result=s.substr(lb[l].second,lb[r-1].second-lb[l].second+1);
        }
        return result;
    }
    bool check(const unordered_map<char,int> & zd)
    {
        for (auto zz=zd.begin();zz!=zd.end();zz++)
            if (zz->second>0) return false;
        return true;
    }
};

187. 重复的DNA序列

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> lb;
        if (s.size()<=10) return lb;
        unordered_map<string,int> zd;
        string s_new=s.substr(0,10);
        zd[s_new]=1;
        for (int i=10;i<s.size();i++)
        {
            s_new.erase(0,1);s_new+=s[i];
            if (zd.find(s_new)==zd.end()) zd[s_new]=1;
            else
            {
                if (zd[s_new]==1) lb.push_back(s_new);
                zd[s_new]+=1;
            }
        }
        return lb;
    }
};

219. 存在重复元素 II

直接暴力

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for (int i=0;i<nums.size();i++)
            for (int j=i+1;j<=i+k and j<nums.size();j++)
                if (nums[i]==nums[j]) return 1;
        return 0;
    }
};

220. 存在重复元素 III

首次碰见这种思想，我就直接抄的题解
又学到了一种思想

class Solution {
public:
    int size;
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        size=valueDiff+1;unordered_map<int,int> zd;
        for (int i=0;i<nums.size();i++) {
            int u=nums[i],idx=getIdx(u);
            if (zd.find(idx)!=zd.end()) return true;
            int l=idx-1,r=idx+1;
            if (zd.find(l)!=zd.end() and abs(u-zd[l])<=valueDiff) return true;
            if (zd.find(r)!=zd.end() and abs(u-zd[r])<=valueDiff) return true;
            zd[idx]=u;
            if (i>=indexDiff) zd.erase(getIdx(nums[i-indexDiff]));
        }
        return false;
    }
    int getIdx(int u) {
        return u>=0?u/size:(u+1)/size-1;
    }
};

396. 旋转函数

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int count=0;
        for (int x:nums) count+=x;
        int f0=0;
        for (int i=0;i<nums.size();i++)
            f0+=i*nums[i];
        int result=f0;
        for (int i=1;i<nums.size();i++)
        {
            f0=f0+count-nums[nums.size()-i]*nums.size();
            if (f0>result) result=f0;
        }
        return result;
    }
};

424. 替换后的最长重复字符

我好菜啊

class Solution {
public:
    int characterReplacement(string s, int k) {
        int l=0,r=0,result=-1,result_temp;
        unordered_map<char,int> zd;
        while (r!=s.size())
        {
            while (1)
            {
                if (r-l<k+1) break;
                char temp=find_max_char(zd);
                if (r-l-zd[temp]<k) break;
                if (s[r]==temp) break;
                l+=1;zd[s[l-1]]-=1;
                if (zd[s[l-1]]==0) zd.erase(s[l-1]);
            }
            if (zd.find(s[r])==zd.end()) zd[s[r]]=0;
            zd[s[r]]+=1;
            r+=1;
            result_temp=r-l;
            if (result_temp>result) result=result_temp;
        }
        return result;
    }
    char find_max_char(unordered_map<char,int> & zd)
    {
        char result=zd.begin()->first;
        for (auto zz=++zd.begin();zz!=zd.end();zz++)
            if (zz->second>zd[result])
                result=zz->first;
        return result;
    }
};

438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> lb;
        if (s.size()<p.size()) return lb;
        unordered_map<char,int> zd1,zd2;
        for (int i=0;i<p.size();i++)
        {
            if (zd1.find(p[i])==zd1.end()) zd1[p[i]]=0;
            zd1[p[i]]+=1;
            if (zd2.find(s[i])==zd2.end()) zd2[s[i]]=0;
            zd2[s[i]]+=1;
        }
        if (zd1==zd2) lb.push_back(0);
        for (int i=1;i<s.size()-p.size()+1;i++)
        {
            zd2[s[i-1]]-=1;
            if (zd2[s[i-1]]==0) zd2.erase(s[i-1]);
            if (zd2.find(s[i-1+p.size()])==zd2.end()) zd2[s[i-1+p.size()]]=0;
            zd2[s[i-1+p.size()]]+=1;
            if (zd1==zd2) lb.push_back(i);
        }
        return lb;
    }
};