【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)

简介: 【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)

题目1:30. 串联所有单词的子串(困难)

思路分析:

整体思路和异位词那题一样,只是把一个字母,变成了string,算法一样的。但需要错位跑几次,才能跑全

思路1:滑动窗口+哈希map

代码实现:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;
        for (auto s : words) hash1[s]++;
        vector<int> ret;
        int n = s.size(), len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) 
        {
            unordered_map<string, int> hash2;
            for (int left = i , right =i, count = 0; right+len <= n;right += len)
            {
                //进窗口+维护count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in)&&hash2[in] <= hash1[in]) count++;
                //判断
                if (right-left+1>len*m) 
                {
                    //出窗口+维护count
                    string out = s.substr(left, len);
                    if (hash1.count(out)&&hash2[out] <= hash1[out])  count--;
                    hash2[out]--;
                    left += len;
                }
                //更新结果
                if (count == m)  ret.push_back(left);
            }
        }
        return ret;
    }
};

LeetCode链接:30. 串联所有单词的子串


题目2:LCR 017.最小覆盖子串

思路分析

思路1:滑动窗口+哈希表

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[60]={0};    //统计t中字母个数
        for(auto ch:t) hash1[ch-'A']++;
        int hash2[60]={0};
        int n=s.size(),m=t.size();
        int minlen=INT_MAX,begin=-1;  //返回值
        for(int left=0,right=0,count=0;right<n;right++)
        {
          //进窗口,没条件都进
            char in=s[right];
            hash2[in-'A']++;
            //维护count 记录有效字母个数
            if(hash2[in-'A']<=hash1[in-'A']) count++;
            while(count==m) //判断
            { //出窗口+维护count
                char out=s[left];
                if(hash2[out-'A']<=hash1[out-'A']) 
                {
                    if(right-left+1<minlen)
                    {
                        minlen=right-left+1;
                        begin=left;
                    }
                    count--;
                } 
                hash2[out - 'A']--;
                left++;
            }
        }
        if(begin==-1) return "";
        else return s.substr(begin,minlen);
    }
};

LeetCode链接:LCR 017.最小覆盖子串

相关文章
|
24天前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
12 1
|
24天前
|
存储 算法 测试技术
力扣经典150题第三十三题:最小覆盖子串
力扣经典150题第三十三题:最小覆盖子串
11 1
|
12天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
24天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
16 0
|
24天前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
10 0
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词