刷题训练之滑动窗口

简介: 本文介绍了如何运用滑动窗口算法解决LeetCode上的多个编程问题,包括查找和数组和满足条件的子数组长度、最长无重复字符子串、连续1的最大长度、调整0的个数以最大化连续1的长度、水果成篮和字母异位词等问题。

> 作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等

> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:熟练掌握滑动窗口算法,并且能把下面的题目做出

> 毒鸡汤:人生就像一场马拉松比赛,不是看谁跑得最快,而是看谁坚持到最后。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕



🌟前言分析

       最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题。


而今天我们的板块是双指针问题。


⭐知识讲解

滑动窗口本质上是两个指针所固定一个窗口而这个窗口可以移动。


⭐经典题型

🌙topic-->1

题目原型:.



题目分析:

在数组中中找出最短的距离,而这个区间的数字之和要大于等于target

讲解算法原理:




编写代码:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int n = nums.size();
        int sum = 0;
        int len = INT_MAX;
        for(int left = 0,right = 0; right < n; right++)
        {
            // 进窗口
            sum = sum + nums[right];
            // 判断
            while(sum >= target)
            {
                // 更新结果
                len = min(len,right- left + 1);
                // 出窗口
                sum = sum - nums[left++];
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};


细节注意:

1.有可能数组没有我们的值,这里我们len就最开始定义成最大值

2.如果没有最大值我们返回0


🌙topic-->2

题目原型:



题目分析:

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

讲解算法原理:



编写代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        // 使用数组来模拟哈希表
        int hash[128] = {0};
        // 定义窗口左右端
        int left = 0;
        int right = 0;
        // 计算字符串长度
        int n = s.size();
        int ret = 0;
        // 循环
        while(right < n)
        {
            // 存入hash表中,进入窗口
            hash[s[right]]++;
            // 判断
            while(hash[s[right]] > 1)
            {
                // 出窗口
                hash[s[left++]]--;
            }
            // 计算结果
            ret = max(ret,right - left + 1);
            // 让下一个元素进入
            right++;
        }
        // 返回
        return ret;
    }
};


🌙topic-->3

题目原型:


题目分析:

在一个数组中,元素只有 1 和 0 ,给定一个K值,这个K值是可以在数组中改变 0 的个数的多少,在改变数组时,需要求出连续 1 的最长值


讲解算法原理:



编写代码:

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> P(n + 1);
        for (int i = 1; i <= n; ++i) {
            P[i] = P[i - 1] + (1 - nums[i - 1]);
        }
 
        int ans = 0;
        for (int right = 0; right < n; ++right) {
            int left = lower_bound(P.begin(), P.end(), P[right + 1] - k) - P.begin();
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};


🌙topic-->4

题目原型:



题目分析:

可以减去左右数组的元素值,找出满足最小值的减的次数

讲解算法原理:



编写代码:

class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {
        // 先计算数组和的大小
        int sum = 0;
        for(int a : nums)
            sum = sum + a;
        int target = sum - x;
        // 细节处理
        if(target < 0)
            return -1;
        int ret = -1;
        for(int left = 0,right = 0,tmp = 0;right < nums.size();right++)
        {
            // 进窗口
            tmp = tmp + nums[right];
            // 判断
            while(tmp > target)
            {
                // 出窗口
                tmp = tmp - nums[left++];
            }
            // 更新结果
            if(tmp == target)
                ret = max(ret,right - left + 1);
        }
        if(ret == -1)
            return ret;
        else
            return nums.size() - ret;
    }
};


🌙topic-->5

题目原型:



题目分析:

可以采摘最多棵水果树,保证最多两种水果种类(必须是连续的)

讲解算法原理:



编写代码:

class Solution {
public:
    int totalFruit(vector<int>& f) 
    {
        int hash[100001] = {0}; // 统计每种水果的个数
        int ret = 0; // 计算最多水果个数
        for(int left = 0,right = 0,kinds = 0;right < f.size();right++)
        {
            // 维护水果种类
            if(hash[f[right]] == 0)
                kinds++;
            // 进窗口
            hash[f[right]]++;
 
            while(kinds > 2) // 判断
            {
                // 出窗口
                hash[f[left]]--;
                if(hash[f[left]] == 0)
                    kinds--;
                left++;
            }
            // 更新结果
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};


🌙topic-->6

题目原型:



题目分析:

在 s 中返回跟 p 异位词的索引,不可缺少。

讲解算法原理:



编写代码:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret; // 用数组来存储结果
        
        // 第一个hash桶来存储 p 字符串
        int hash1[26] = { 0 };
        int m = p.size();
        for(auto e: p) // 存入
            hash1[e - 'a']++;
 
        // 第二个hash桶来存储每个字符出现的次数
        int hash2[26] = { 0 };
        int count = 0; // 计算字符种类次数
        for(int left = 0,right = 0;right < s.size();right++)
        {
            char in = s[right];
            // 进窗口
            hash2[in - 'a']++;
            // 维护字符种类
            if(hash2[in - 'a'] <= hash1[in - 'a'])
                count++;
            // 判断
            if(right -left + 1 > m)
            {
                char out = s[left++];
                // 维护字符种类
                if(hash2[out - 'a'] <= hash1[out - 'a'])
                    count--;
                // 出窗口
                hash2[out - 'a']--;
            }
            // 更新结果
            if(count == m)
                ret.push_back(left);// 尾插
        }
        return ret;
    }
};


topic-->7

题目原型:



题目分析:

在 s 中找区间,这个区间必须是连续的,s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

讲解算法原理:



编写代码:

class Solution
{
public:
  vector<int> findSubstring(string s, vector<string>& words)
  {
    vector<int> ret; // 用来保存结果
    unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
    for (auto& s : words) 
            hash1[s]++;
    
        int len = words[0].size(), m = words.size();
    for (int i = 0; i < len; i++) // 执⾏ len 次
    {
      unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
      for (int left = i, right = i, count = 0; right + len <= s.size();
        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;
  }


🌙topic-->8

题目原型:



题目分析:

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


讲解算法原理:



编写代码:

class Solution
{
public:
  string minWindow(string s, string t)
  {
    int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
    int kinds = 0; // 统计有效字符有多少种
    for (auto ch : t)
      if (hash1[ch]++ == 0) kinds++;
    int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
    int minlen = INT_MAX, begin = -1;
    for (int left = 0, right = 0, count = 0; right < s.size(); right++)
    {
      char in = s[right];
      if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
      while (count == kinds) // 判断条件
      {
        if (right - left + 1 < minlen) // 更新结果
        {
          minlen = right - left + 1;
          begin = left;
        }
        char out = s[left++];
        if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
      }
    }
    if (begin == -1) return "";
    else return s.substr(begin, minlen);
  }
};


🌟结束语

      今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。


目录
相关文章
|
5月前
|
存储 算法 Java
【算法系列篇】滑动窗口-1
【算法系列篇】滑动窗口-1
|
3月前
|
算法 C语言 C++
刷题训练之前缀和(上)
本文围绕前缀和算法展开,介绍了C++实现的多种经典题型,包括一维和二维前缀和,以及中心下标和子数组和等问题,强调实战学习的重要性,鼓励读者通过刷题提升技能。
30 0
刷题训练之前缀和(上)
|
3月前
|
算法 C语言 C++
刷题训练之二分查找
本文详细介绍了二分查找算法,包括其时间复杂度、适用场景(如有序/无序数组),并提供了针对LeetCode上常见题型的解析,包括查找、范围搜索和插入位置等,强调理解和记忆关键模板。
18 0
|
3月前
|
机器学习/深度学习 算法 C++
刷题训练之前缀和(下)
本文围绕前缀和算法展开,介绍了C++实现的多种经典题型,包括一维和二维前缀和,以及中心下标和子数组和等问题,强调实战学习的重要性,鼓励读者通过刷题提升技能。
32 0
|
3月前
|
算法 Java C语言
刷题训练之双指针问题
刷题训练之双指针问题
24 0
|
12月前
|
算法 C++
【LeetCode 算法专题突破】滑动窗口(⭐)
【LeetCode 算法专题突破】滑动窗口(⭐)
45 0
|
5月前
|
算法
算法思想总结:滑动窗口算法
算法思想总结:滑动窗口算法
|
算法
第 6 天_滑动窗口【算法入门】
第 6 天_滑动窗口【算法入门】
67 0
|
算法 索引
LeetCode 双周赛 107(2023/06/24)滑动窗口与离散化
> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 \[彭旭锐] 和 \[BaguTree Pro] 知识星球提问。**
68 0
LeetCode 双周赛 107(2023/06/24)滑动窗口与离散化
|
算法 索引
【滑动窗口】算法实战
滑动窗口算法的原理和leetcode中的相关题目题解。