定长滑动窗口--灵神题单（一刷进阶）

“αβ”

1418人浏览 · 2024-12-01 22:25:19

“αβ” · 2024-12-01 22:25:19 发布

第一题：2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）

第二题：567. 字符串的排列 - 力扣（LeetCode）

第三题：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

第四题：2156. 查找给定哈希值的子串 - 力扣（LeetCode）

第五题：1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（LeetCode）

第六题：2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）

第七题： 1984. 学生分数的最小差值 - 力扣（LeetCode）

第一题：2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）

按照力扣的滑动窗口标签刷到这题，知道是滑窗，但想了半天没想到怎么滑。
再看了下灵神给的滑动窗口题单【题单】滑动窗口（定长/不定长/多指针）里面把这题归类为定长滑动窗口。
说是定长滑窗。那只能是 1的总数或 0的总数当作固定的窗口长度吧。
那就两种情况都写一下，反正都是O(n)。

窗口长度固定为0的总数，那窗口内要被替换成0的个数，即窗口内1的个数就是结果，求最小
窗口长度固定为1的总数，那窗口内要被替换成1的个数，即窗口内0的个数就是结果，求最小

上述两个结果都求出来，然后再求个最小，然后就通过了。
定长滑窗的具体写法是初始窗口处理好，然后右端进一个，左端出一个。

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int count_1 = 0;// 统计一的个数
        for (auto& num : nums) count_1 += num;
        int count_0 = n - count_1;
        int ret = n;
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {
            // 进窗口
            count += nums[right];
            // 判断
            if (right - left + 1 >= count_1)
            {
                ret = min(ret, count_1 - count);
                count -= nums[left++];
            }
        }
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {
            // 进窗口
            if (nums[right] == 0)
            {
                count += 1;
            }
            // 判断
            if (right - left + 1 >= count_0)
            {
                ret = min(ret, count_0 - count);
                if (nums[left++] == 0) count -= 1;
            }
        }
        return ret;
    }
};

第二题：567. 字符串的排列 - 力扣（LeetCode）

这一道题如果想到要去使用哈希表，其实是非常的简单的，最主要的是如何想办法去优化。

检查字符串s2是否包含s1的排列。你通过hash1记录s1中每个字符的频率，并通过hash2跟踪当前窗口内字符的频率。每次滑动窗口时，更新字符的计数并检查是否满足s1的字符频率。优化点在于：1. 通过滑动窗口避免重复遍历，

2. 只对s1中出现的字符进行操作，减少不必要的计算。通过count变量追踪窗口中字符的匹配数量，避免了每次都重新计算。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1 = s1.size();
        int n2 = s2.size();
        if (n1 > n2)
            return false; // 如果s1的长度大于s2，直接返回false
        unordered_map<char, int> hash1;
        for (auto& e : s1)
            hash1[e]++;
        unordered_map<char, int> hash2;
        for (int left = 0, right = 0, count = 0; right < n2; right++) {
            // 进窗口
            char in = s2[right];
            if (hash1.find(in) != hash1.end()) {
                hash2[in]++;
                if (hash2[in] <= hash1[in])
                    count++;
            }
            // 判断 出
            if (right - left + 1 >= n1) 
            {
                if (count == n1) 
                {
                    return true;
                }
                char ou = s2[left++];
                if (hash1.find(ou) != hash1.end()) 
                {
                    // 如果移出的字符在 s1 中出现过，更新 hash2 和 count
                    if (hash2[ou] <= hash1[ou]) 
                    {
                        count--;
                    }
                    hash2[ou]--;
                }
            }
        }
        return false;
    }
};

第三题：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

这一道题其实也是非常简单的定长滑动窗口。没什么难度。就不解释了，直接给代码吧。

但是还是要给出疑问：

使用哈希表好？还是数组好？给出为什么？

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26]={0};
        int m=p.size();
        for(auto& e:p) hash1[e-'a']++;
        int hash2[26]={0};
        int n=s.size();
        vector<int> ret;
        for(int left=0,right=0,count=0;right<n;right++)
        {
            char in=s[right];
            //进窗口
            hash2[in-'a']++;
            if(hash2[in-'a']<=hash1[in-'a']) count++;
            //出窗口
            char ou=s[left];
            if(right-left+1>m )
            {
                if(hash2[ou-'a']--<=hash1[ou-'a']) count--;
                left++;
            }
            //更新结果
            if(count==m)
            {
                ret.push_back(left);
            }
        }
        return ret;
    }
};

第四题：2156. 查找给定哈希值的子串 - 力扣（LeetCode）

这一道题其实也是不是很难，虽然力扣给出是困难题，但是只要了解一些数学知识，把题目的过程简化，难度连中等题都谈不上。

但这一切前提都是你对该部分数学知识了解，如果不了解，根本无思路。

代码：

class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int n=s.size();
        string ret;
        int h = 0;   // 子串哈希值
        for(int left=0,right=0;right<n;right++)
        {
            // 进窗口
            h=(long long)h+(s[right] - 'a' + 1) * power % modulo;
            if(right-left+1>=k)
            {
                if(h==hashValue)
                {
                    ret=s.substr(left,k);
                }
                // 出
                if(h==0) h=modulo;
                h=(long long)h-(s[left++]-'a'+1)* power % modulo;
            }
        }
        return ret;
    }
};

第五题：1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（LeetCode）

看到这一题的时候我也是一头雾水，但是看过灵神写的题解，才慢慢反应过来。

灵神首先给出的是暴力求解

对于方法一，其实我开始也看不明白代码什么意思

class Solution {
public:
    bool queryString(string s, int n) {
        for(int i=1;i<=n;i++)
        {
            auto bin = bitset<32>(i).to_string();
            bin = bin.substr(bin.find('1'));
            if(s.find(bin) == -1) return false;
        }
        return true;
    }
};

这里使用gtp解释一下

对于方法二：

直接截图看灵神的解释吧，人家写的太详细了，想的太妙了，尤其是其中的(x << 1) | (c - '0')。

但是妙归妙，还是要看完思路，自己尝试首先一下代码。

class Solution {
public:
    bool queryString(string s, int n) {
        unordered_set<int> ans;
        for(int i=0,m=s.size();i<m;i++)
        {
            int x=s[i]-'0';
            if(x==0) continue;// 二进制为，继续
            for(int j=i+1;x<=n;j++)
            {
                ans.insert(x);
                if(j==m) break;
                x=(x<<1) | (s[j]-'0');
            }
        }
        return ans.size()==n;
    }
};

第六题：2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）

这道题要说它简答吧，直接暴力硬写也可以写出来，但是要说它简单，但要使用滑动窗口来写，又比较麻烦。

思路好想，没什么难度，直接给代码

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        vector<int> v; //存放num这个数串每个位的值
        int n;  //代表数串每个位数的值
        int num1 = num; //将num赋给num1
        int res = 0;//美丽值-返回的结果
        while(num1 != 0){//从个位 十位 百位...依次压入v容器中
            n = num1%10;//余数
            num1 = num1/10;//自除更新num1
            v.push_back(n);
        }
        reverse(v.begin(),v.end());//逆序v容器的元素
        int left = 0;//左边界
        int right = k-1;//右边界 //0到k-1正好k个数
        for(left,right;right<v.size();right++,left++){//滑动窗口方式模拟验证
            int tmp = v[left];//初始化tmp  滑动窗口左边界代表 窗口内数串的最高位
            for(int i=left+1;i<=right;i++){
                tmp = tmp*10+v[i]; //模拟滑动窗口中元素组成一个数
            }
            if(tmp == 0)//如果为0，直接下一次循环
                continue;
            if(num%tmp == 0 ) {//如果可整除，美丽值结果+1
                res++;
            }
        }
        return res;//返回结果
    }
};

第七题： 1984. 学生分数的最小差值 - 力扣（LeetCode）

如果是在没有思路，那不妨先让其有序。

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ret=INT_MAX;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int left=0,right=0;right<n;right++)
        {
            if(right-left+1==k)
            {
                ret=min(ret,(nums[right]-nums[left++]));
            }
        }
        return ret;
    }
};

没有解决的题目：

会员题除外

2953. 统计完全子字符串 - 力扣（LeetCode）

1888. 使二进制字符串字符交替的最少反转次数 - 力扣（LeetCode）

220. 存在重复元素 III - 力扣（LeetCode）

乐奇 Rokid 开放社区

更多推荐

智慧矿山人员定位AR巡检品牌推荐

乐奇 Rokid 开放社区

水务集团AR巡检系统选哪家公司好

乐奇 Rokid 开放社区

极刻觅镜 | AI眼镜周报｜智能眼镜声学性能测试规范10月2日起实施

本周智能眼镜领域出现多项进展：国内《智能眼镜声学性能测试规范》自10月2日起实施，高通发布Snapdragon Sound Elite Gen 2平台，Meta与Naver合作推进免手持步行导航，依视路陆逊梯卡与Meta扩充产品线，影目INMO就海外版发热问题发布声明，荷兰零售商停售Meta眼镜并引发监管关注。