刷题训练之滑动窗口

简介: 本文介绍了如何运用滑动窗口算法解决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);
  }
};


🌟结束语

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


目录
相关文章
|
17天前
|
机器学习/深度学习 算法 搜索推荐
《探秘Adagrad算法:自适应学习率的奥秘与适用场景》
Adagrad算法通过自适应调整学习率,根据参数梯度的累积平方动态改变每个参数的学习率。初始时设置学习率η,每次迭代计算梯度并累积其平方,更新后的学习率为η/√(r_t+ε),使频繁更新的参数学习率减小,稀疏参数学习率增大。适用于稀疏数据、特征重要性差异大、前期快速探索及简单模型场景。然而,学习率单调递减可能影响后期训练效果。
|
8月前
|
算法 Java C语言
刷题训练之双指针问题
刷题训练之双指针问题
49 0
|
算法 C++
【LeetCode 算法专题突破】滑动窗口(⭐)
【LeetCode 算法专题突破】滑动窗口(⭐)
67 0
|
算法
第 6 天_滑动窗口【算法入门】
第 6 天_滑动窗口【算法入门】
83 0
|
10月前
|
算法
算法思想总结:滑动窗口算法
算法思想总结:滑动窗口算法
|
存储 算法 Java
趣味算法:滑动窗口算法的理解与应用
前言 在编程和数据结构中,滑动窗口算法是一种常见的解决问题的方法。它主要用于处理涉及连续或固定长度子数组、子序列或子字符串的问题。本文将深入探讨滑动窗口算法,包括其基本概念、应用场景、基本步骤以及具体的Java代码实践。
647 0
|
算法
【算法小课堂】滑动窗口
基本概念: 滑动窗口本质是双指针算法的一种演变 本质上就是同向双指针,窗口的范围就是[left,right)
396 0
|
算法 Python
算法创作|随机出10道题并计算正确率问题解决方法
算法创作|随机出10道题并计算正确率问题解决方法
157 2
|
算法 网络协议 索引
经典算法之——滑动窗口
经典算法之——滑动窗口
124 0
|
算法
刷题算法:滑动窗口法
滑动窗口法就是在不断地调整子序列地起始位置与终止位置,从而得出我们想要的结果。滑动窗口法的起始与终止节点的移动的目的即为求解子序列的最优化处理,其基本的思路如下: 定义双指针,初始值一致,双指针之间的内容为所谓的窗口,包括双指针所指的元素。 确定指针之间的最佳窗口内容的判断条件,即窗口内容扩大、缩小的条件。 优先移动终止节点,扩大窗口直至恰好满足判断条件,再移动起始节点一次缩小窗口 再次判断是否符合条件,符合,此时为一次所求解的子序列,记录所需参数,继续移动起始节点,不符合,起始节点不动,移动终止节点至恰
108 0