算法专题二:滑动窗口

这篇具有很好参考价值的文章主要介绍了算法专题二:滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.长度最小的子数组:

算法专题二:滑动窗口,算法,c++
长度最小的子数组

1.思路一:暴力解法

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int num = 100000;
        int value = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += nums[j];
                if (sum >= target)
                {
                    value = sum;
                    if (value >= target && num >= (j - i + 1))
                    {
                        num = (j - i + 1);
                    }
                }
            }
        }

        if (num != 100000)
            return num;

        return 0;
    }
};

2.思路二:滑动窗口+双指针

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int len = INT_MAX;

        for(int left=0,right=0;right<nums.size();right++)
        {
            sum+=nums[right];
            while(sum>=target)
            {
                int len_1 = right-left+1;
                if(len_1 < len)
                    len = len_1;

                sum-=nums[left++];
            }
        }

        return (len==INT_MAX? 0 : len);
    }
};

3.GIF题目解析:

思路一:

算法专题二:滑动窗口,算法,c++

思路二:

算法专题二:滑动窗口,算法,c++

二.无重复字符的最长子串:

算法专题二:滑动窗口,算法,c++

无重复字符的最长子串

1.思路一:滑动窗口

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int len = 0;
        int hash[128]={0};

        for(int left=0,right=0;right<s.size();right++)
        { 
            hash[s[right]]++;
            while(hash[s[right]]>1)
            {
                hash[s[left]]--;
                left++;  
            }
            len = max(len,(right-left+1));
        }

        return len;
    }
};

2.GIF题目解析:

思路一:

算法专题二:滑动窗口,算法,c++

三.最大连续1的个数:

算法专题二:滑动窗口,算法,c++

最大连续1的个数

1.思路一:滑动窗口

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int len = 0;
        for(int left=0,right=0,zero=0;right<nums.size();right++)
        {
            if(nums[right]==0)
                zero++;
            while(zero > k)
                if(nums[left++]==0)zero--;
            len = max(len,(right-left)+1);
        }
        return len;
    }
};

2.GIF题目解析:

开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1,走不到这些1数据导致记录连续1的个数出问题!

算法专题二:滑动窗口,算法,c++

四:将x减小到0的最小操作数:

算法专题二:滑动窗口,算法,c++

将x减小到0的最小操作数

1.思路一:滑动窗口

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum_1 = 0;
        vector<int>::iterator it_1 = nums.begin();
        while (it_1 != nums.end())
        {
            sum_1 += (*it_1);
            it_1++;
        }
        
        int n = nums.size();
        int target = sum_1 - x;
        if(target <= 0)
        {
            if(target<0)
                return -1;
            else
                return n;
        }

        //1.滑动窗口:

        int sum_2 = 0;
        int ret = 0;

        for (int left = 0, right = 0; right < n; right++)
        {
            sum_2 += nums[right];
            while (sum_2 >= target)
            {
                if(sum_2 == target)
                    ret = max(ret, (right - left) + 1);

                sum_2 -= nums[left];
                left++;
            }
            if(sum_2 == target)
                ret = max(ret, (right - left) + 1);
        }
        return (ret==0? -1:n-ret);
    }
};

2.GIF题目解析:

算法专题二:滑动窗口,算法,c++

五.水果成篮

算法专题二:滑动窗口,算法,c++

水果成篮

1.思路一:滑动窗口

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    int totalFruit(vector<int>& fruits) {

        int Hash[100001]={0};
        int n = fruits.size();
        int len = 0;

        for(int left=0,right=0,zero=0;right<n;right++)
        {
            if(Hash[fruits[right]]==0)
            {
                Hash[fruits[right]]++;
                zero++;
            }
            else
            {
                Hash[fruits[right]]++;
            }

            while(zero > 2)
            {
                Hash[fruits[left]]--;

                if(Hash[fruits[left++]]==0)
                    zero--;
            }
            len = max(len , (right-left)+1);
        }

        return len;
    }
};

2.GIF题目解析:

算法专题二:滑动窗口,算法,c++

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

算法专题二:滑动窗口,算法,c++

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

1.思路一:滑动窗口

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26]={0};
        int len = p.size();
        for(auto ch:p)
        {
            hash1[ch -'a']++;
        }

        int hash2[26]={0};
        vector<int> vv;
        
        for(int left=0,right=0;right<s.size();right++)
        {
            hash2[s[right] - 'a']++;

            if((right-left+1) == len)
            {
                //1.判断是否相等
                int flag = 0;
                for(int i=0;i<26;i++)
                {
                    if(hash1[i] != hash2[i])
                    {
                        flag = -1;
                        break;
                    }
                }
                if(flag!=-1)
                    vv.push_back(left);
                
                hash2[s[left] - 'a']--;
                left++;
            }
        }
        return vv;
    }
};

2.思路二:滑动窗口(比较优化)

1.我们有注意到一个问题在比较相等确定left可不可以push的时候去优化一下26次循环比较的过程。
2.可以给一个变量去控制数量的变化。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26]={0};
        int len = p.size();
        for(auto ch:p)
        {
            hash1[ch -'a']++;
        }

        int hash2[26]={0};
        vector<int> vv;
        
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            //hash2[s[right] - 'a']++;
            if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
                count++;

            if((right-left+1) > len)
            {
                char out = s[left++];
                //出去窗口:
                if(hash2[out-'a']-- <= hash1[out-'a'])
                    count--;
            }
            if(count == len) vv.push_back(left);
        }
        return vv;
    }
};

2.GIF题目解析:

算法专题二:滑动窗口,算法,c++

七.串联所有单词的子串

算法专题二:滑动窗口,算法,c++

串联所有单词的子串

1.思路一:滑动窗口 + 哈希映射:

算法专题二:滑动窗口,算法,c++

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;

        unordered_map<string,int> hash1;
        for(auto& s:words)hash1[s]++;

        int len = words[0].size();
        int 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<=s.size();right+=len)
            {
                string in = s.substr(right,len);
                hash2[in]++;

                //1,进入窗口 + 维护count
                if(hash1.count(in) && hash2[in] <= hash1[in])
                    count++;
                
                if((right-left+1) > (len*m))
                {
                    //2.出去窗口 + 维护count
                    string out = s.substr(left,len);

                    if(hash1.count(out) && hash2[out] <= hash1[out])count--;
                    hash2[out]--;
                    left+=len;
                }

                //3.数据更新:
                if(count == m) ret.push_back(left);
            }
        }

        return ret;
    }
};

2.GIF题目解析:

算法专题二:滑动窗口,算法,c++

八.最小覆盖子串

算法专题二:滑动窗口,算法,c++

最小覆盖子串

1.思路一:暴力解法+哈希表

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for (char ch : t)
        {
            hash1[ch]++;
        }

        int kind = t.size();
        int len = INT_MAX;
        int begin = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int hash2[128] = { 0 };
            int count = 0;

            for (int j = i; j < s.size(); j++)
            {
                if (hash2[s[j]]++ < hash1[s[j]] && hash1[s[j]]!=0)
                    count++;

                if (kind == count)
                {
                    //更新数据:
                    if (j - i + 1 <= len)
                    {
                        len = j - i + 1;
                        begin = i;
                    }
                }
            }
        }

        string vv("");
        if (kind > s.size() || len == INT_MAX)
            return vv;

        vv = s.substr(begin, len);
        return vv;
    }
};

算法专题二:滑动窗口,算法,c++

2.思路二:滑动窗口+哈希表

算法专题二:滑动窗口,算法,c++

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        int kind = 0;
        for (char ch : t)
        {
            if(hash1[ch]++ == 0)
                kind++;
        }
        int len = INT_MAX;
        int begin = -1;
        int hash2[128] = { 0 };

        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            //1.进入窗口+维护count
            char in = s[right];
            if(++hash2[in] == hash1[in])
                count++;
            //2.判断出窗口+维护count
            while(count == kind)
            {
                if(right-left+1 < len)
                {
                    len = right-left+1;
                    begin = left;
                }

                char out = s[left++];
                if(hash2[out]-- == hash1[out])
                    count--;
            }
            
        }
        if(begin == -1)
            return "";
        else
            return s.substr(begin,len);
    }
};

2.GIF题目解析:

算法专题二:滑动窗口,算法,c++文章来源地址https://www.toymoban.com/news/detail-787941.html

到了这里,关于算法专题二:滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode 算法专题突破】滑动窗口(⭐)

    学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接:209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算

    2024年02月07日
    浏览(52)
  • 力扣精选算法100题——水果成篮(滑动窗口专题)

    本题链接👉水果成篮 我就按照实例1来进行对这题的理解。 1代表种类类型,这个数组里面有2个种类类型 ps:种类1和种类2 ,只不过种类1是有2个水果,种类2有一个水果,共计3个水果。 本题需要解答:收集水果的最大数目. 但是前提条件: 我们只有2个篮子,每个篮子里只能装

    2024年01月17日
    浏览(40)
  • 【算法专题突破】滑动窗口 - 长度最小的子数组(9)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:209. 长度最小的子数组 - 力扣(Leetcode)  要注意的是,题目给的是正整数, 而题目要求并不难理解,就是找最短的子数组。 如果使用暴力的话,就是一个O(N3)的算法,复杂度很高, 我们可以用滑动窗口来做,

    2024年02月09日
    浏览(31)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(66)
  • 【LeetCode滑动窗口专题#2】无重复字符的最长子串

    #1传送门 滑动窗口最大值 长度最小的子数组 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = \\\"abcabcbb\\\" 输出: 3 解释: 因为无重复字符的最长子串是 \\\"abc\\\",所以其长度为 3。 示例 2: 输入: s = \\\"bbbbb\\\" 输出: 1 解释: 因为无重复字符的最长子串

    2024年02月08日
    浏览(40)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 【算法】基础算法002之滑动窗口(二)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言  5.水果成篮(medium)  6.找到字符串中所有字母异位词 7.串联所有单词的

    2024年02月20日
    浏览(46)
  • 【算法】基础算法002之滑动窗口(一)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.长度最小的子数组 滑动窗口类问题解题思路大纲: 2.无重复字符的最长

    2024年02月19日
    浏览(43)
  • 算法——滑动窗口

    滑动窗口大致分为两类:一类是窗口长度固定的,即left和right可以一起移动;另一种是窗口的长度变化(例如前五道题),即right疯狂移动,left没怎么动,这类题需要观察单调性(即指针)等各方面因素综合思考 长度最小的子数组 子数组需要为连续的区间 需要在满足条件的前

    2024年04月10日
    浏览(36)
  • 【滑动窗口】算法实战

    滑动窗口 ,顾名思义,就是有一个大小可变的窗口,左右两端方向一致的向前滑动 ( 右端固定,左端滑动;左端固定,右端滑动 )。 滑动窗口的本质其实也是一种双指针算法,它是根据 单调性 的思想,使用” 同向双指针 “,索引字符串或者列表中的一个区间 [left,rig

    2024年02月15日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包