算法专题二：滑动窗口

算法专题二：滑动窗口

  • 一.长度最小的子数组：
    • 1.思路一：暴力解法
    • 2.思路二：滑动窗口+双指针
    • 3.GIF题目解析：
      • 思路一：
      • 思路二：
  • 二.无重复字符的最长子串：
    • 1.思路一：滑动窗口
    • 2.GIF题目解析：
      • 思路一：
  • 三.最大连续1的个数：
    • 1.思路一：滑动窗口
    • 2.GIF题目解析：
  • 四：将x减小到0的最小操作数：
    • 1.思路一：滑动窗口
    • 2.GIF题目解析：
  • 五.水果成篮
    • 1.思路一：滑动窗口
    • 2.GIF题目解析：
  • 六. 找到字符串中的所有字母的异位词
    • 1.思路一：滑动窗口
    • 2.思路二：滑动窗口（比较优化）
    • 2.GIF题目解析：
  • 七.串联所有单词的子串
    • 1.思路一：滑动窗口 + 哈希映射：
    • 2.GIF题目解析：
  • 八.最小覆盖子串
    • 1.思路一：暴力解法+哈希表
    • 2.思路二：滑动窗口+哈希表
    • 2.GIF题目解析：

一.长度最小的子数组：

在这里插入图片描述
长度最小的子数组

1.思路一：暴力解法

在这里插入图片描述

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.思路二：滑动窗口+双指针

在这里插入图片描述

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题目解析：

思路一：

在这里插入图片描述

思路二：

在这里插入图片描述

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

在这里插入图片描述

无重复字符的最长子串

1.思路一：滑动窗口

在这里插入图片描述

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题目解析：

思路一：

在这里插入图片描述

三.最大连续1的个数：

在这里插入图片描述

最大连续1的个数

1.思路一：滑动窗口

在这里插入图片描述

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的个数出问题！

在这里插入图片描述

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

在这里插入图片描述

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

1.思路一：滑动窗口

在这里插入图片描述

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题目解析：

在这里插入图片描述

五.水果成篮

在这里插入图片描述

水果成篮

1.思路一：滑动窗口

在这里插入图片描述

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题目解析：

在这里插入图片描述

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

在这里插入图片描述

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

1.思路一：滑动窗口

在这里插入图片描述

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题目解析：

请添加图片描述

七.串联所有单词的子串

在这里插入图片描述

串联所有单词的子串

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

在这里插入图片描述

在这里插入图片描述

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题目解析：

请添加图片描述

八.最小覆盖子串

在这里插入图片描述

最小覆盖子串

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

在这里插入图片描述

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;
    }
};

在这里插入图片描述

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

在这里插入图片描述

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题目解析：

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/255898.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

制作一个多行时正确宽度的Textview,Android Textview 换行时宽度过长 右侧空白区域挤掉页面元素的解决方案

制作一个多行时正确宽度的Textview,Android Textview 换行时宽度过长 右侧空白区域挤掉页面元素的解决方案

优化 Android 布局&#xff1a;创建自适应宽度的 TextView 引言 在Android应用开发中&#xff0c;布局优化是提升应用性能和用户体验的关键环节之一。特别是对于那些内容密集型的应用&#xff0c;如何高效地展示和管理文本内容成为了一个挑战。最近&#xff0c;在处理一个布局…
阅读更多...
【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现

【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现

​&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a;《数据结构奇遇记》&#x1f516;墨香寄清辞&#xff1a;墨痕寄壮志&#xff0c;星辰梦未满。 通幽径心凝意&#xff0c;剑指苍穹势如山。 目录 &#x1f31e;1. 模式匹配的基本概念…
阅读更多...
Scala多线程爬虫程序的数据可视化与分析实践

Scala多线程爬虫程序的数据可视化与分析实践

一、Scala简介 Scala是一种多种类型的编程语言&#xff0c;结合了针对对象编程和函数式编程的功能。它运行在Java虚拟机上&#xff0c;具有强大的运算能力和丰富的库支持。Scala常用于大数据处理、并发编程和Web应用程序开发。其灵活性和高效性编程成为编写多线程爬虫程序的理…
阅读更多...
科技云报道：至简至强，新一代服务器的算力美学

科技云报道：至简至强，新一代服务器的算力美学

科技云报道原创。 在这个时代&#xff0c;数据和计算的边界正在迅速扩张。 随着云计算、物联网和人工智能的日益成熟&#xff0c;对算力的需求已经突破了传统的限制&#xff0c;进入了一个全新的阶段。在这个阶段&#xff0c;不仅是算力的量级发生了变化&#xff0c;其性质和…
阅读更多...
Mysql之约束上篇

Mysql之约束上篇

Mysql之约束上篇 约束的概述为什么需要约束什么是约束约束的分类 非空约束作用关键字特点添加非空约束删除非空约束 唯一性约束关键字特点添加唯一约束关于复合唯一约束删除唯一约束查看索引 主键约束(非空唯一性约束)作用关键字特点添加主键约束关于复合主键删除主 约束的概述…
阅读更多...
【MYSQL】-库的操作

【MYSQL】-库的操作

&#x1f496;作者&#xff1a;小树苗渴望变成参天大树&#x1f388; &#x1f389;作者宣言&#xff1a;认真写好每一篇博客&#x1f4a4; &#x1f38a;作者gitee:gitee✨ &#x1f49e;作者专栏&#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法&#x1f384; 如 果 你 …
阅读更多...
[单片机软件]1.keil调整Group中的位置挪动

[单片机软件]1.keil调整Group中的位置挪动

1.找到并选择箭头所指图标&#xff1a; 2.选中箭头所指进行你想要的Group进行移动 以上均为实测有效。
阅读更多...
百度云IOCR自定义模版分类器进行文字识别（非通用文字识别）

百度云IOCR自定义模版分类器进行文字识别（非通用文字识别）

模版管理 云账号登录 访问模版管理地址&#xff1a;点击下面地址新建模版 百度智能云-登录https://ai.baidu.com/iocr?castk4819agr76c7d09971d248#/templatelist/1 添加模版 如果有模版&#xff0c;识别效果不理想可以编辑上述模版&#xff0c;如果新的报表格式可以新建模…
阅读更多...
如何访问AWS私有网络中的RDS (Mysql)

如何访问AWS私有网络中的RDS (Mysql)

文章目录 小结问题及解决连接问题如何使用本地的Mysql Workbench对RDS进行访问 参考 小结 在AWS私有网络中部署了RDS (Mysql), 尝试通过外网成功地进行了访问. 问题及解决 连接问题 在AWS私有网络中部署了RDS (Mysql), 进行外网进行访问碰到了各种问题. 以下连接超时&…
阅读更多...
【05】GeoScene海图或者电子航道图批量出图

【05】GeoScene海图或者电子航道图批量出图

出单张000数据参考上一篇博客&#xff0c;如果想同时出多张海图000数据&#xff0c;也是可以实现的。思路如下&#xff1a; 1 批量创建产品 GeoScene海事模块通过ProductDefinitions表和ProductCoverage要素类定义产品和AOI覆盖区&#xff0c;可支持批量导入产品信息和AOI覆盖…
阅读更多...
@RequestMapping注解与其派生注解接收参数详解

@RequestMapping注解与其派生注解接收参数详解

一、前言 根据 HTTP 标准&#xff0c;HTTP 请求可以使用多种请求方法。 HTTP1.0 定义了三种请求方法&#xff1a; GET, POST 和 HEAD 方法。 HTTP1.1 新增了六种请求方法&#xff1a;OPTIONS、PUT、PATCH、DELETE、TRACE 和 CONNECT 方法。 RequestMapping注解与其派生注解 在…
阅读更多...
网络环境搭建及uboot配置

网络环境搭建及uboot配置

网络环境搭建 搭建网络环境可以搭建公网的也可以搭建局域网的&#xff0c;这里搭建的是局域网的。 详细看实验手册第一个实验 系统移植实验手册 linux内核的安装与加载 这一章节主要分为两大块&#xff1a;一个为产品阶段即&#xff1a;Linux内核、根文件系统、uboot全部存储到…
阅读更多...
董宇辉“小作文事件”：东方甄选的危机与挑战

董宇辉“小作文事件”：东方甄选的危机与挑战

导言 近期&#xff0c;东方甄选公司的创始人董宇辉因涉及“小作文事件”而引起轩然大波。东方甄选作为一家在招聘领域崭露头角的公司&#xff0c;经历了充满曲折的发展历程。本文将深入探讨这一事件对东方甄选公司的发展带来的危机和挑战&#xff0c;以及公司可能采取的解决策略…
阅读更多...
AI绘画中UNet用于预测噪声

AI绘画中UNet用于预测噪声

介绍 在AI绘画领域中&#xff0c;UNet是一种常见的神经网络架构&#xff0c;广泛用于图像相关的任务&#xff0c;尤其是在图像分割领域中表现突出。UNet最初是为了解决医学图像分割问题而设计的&#xff0c;但其应用已经扩展到了多种图像处理任务。 特点 对称结构&#xff1a…
阅读更多...
详细教程 - 从零开发 鸿蒙harmonyOS应用 第九节-——鸿蒙操作系统中的自定义视图封装：一次奇妙的旅程

详细教程 - 从零开发 鸿蒙harmonyOS应用 第九节-——鸿蒙操作系统中的自定义视图封装：一次奇妙的旅程

一、简介 自定义视图是开发鸿蒙应用时的一个重要功能。在这篇文章中&#xff0c;我们将详细探讨如何在鸿蒙系统中实现自定义视图的封装&#xff0c;并提供一些代码示例作为你的地图。 二、自定义视图的实现 在鸿蒙操作系统中&#xff0c;我们可以通过继承ohos.agp.components.…
阅读更多...
【Hadoop】HDFS的体系架构

【Hadoop】HDFS的体系架构

整体上说HDFS框架结构一HDFS框架结构二&#xff08;HDFS High Availability&#xff09; 整体上说 HDFS 采用 Master/Slave 架构。一个 HDFS 集群是由一个 NameNode 和一定数目的 DataNodes组成。其中 NameNode 是一个中心服务器&#xff0c;负责文件系统的名字空间(namespace…
阅读更多...
【Docker】Docker安装部署maven私服

【Docker】Docker安装部署maven私服

文章目录 镜像拉取构建nexus实例登录maven私服如何查看实例初始化的admin密码呢&#xff1f;1.查看容器挂载卷2.找到nexus_nexus_data查看挂载卷详情3.查看admin账号密码4.登录并重置密码 使用nexus私服1.设置settings.xml2.设置idea pom 出现的问题小插曲 镜像拉取 docker pu…
阅读更多...
DVWA靶场的设置

DVWA靶场的设置

1).在win 10系统安phpstudy2016&#xff0c;如图所示 2&#xff09;创建DVWA的靶场&#xff0c;解压DVWA-master.zip到C:\phpStudy\WWW\DWA-master 3&#xff09;配置DVWA链接数据库 右键选择记事本打开configlconfig.inc.php.dist【也可以使⽤其他编辑⼯具打开】&#xff0c;…
阅读更多...
react基于antd二次封装spin组件

react基于antd二次封装spin组件

目录 react基于antd二次封装spin组件组件使用组件效果 react基于antd二次封装spin组件 组件 import { Spin } from antd; import propTypes from "prop-types"; import React from react; import styleId from "styled-components"; // 使用 父div必须加…
阅读更多...
【vtkWidgetRepresentation】第十四期 二维标注

【vtkWidgetRepresentation】第十四期 二维标注

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 前言 本文分享vtk中的二维标注，主要用于医学领域，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动力(＾Ｕ＾)ノ~ＹＯ 目录 前言 1. vtkBiDimension…
阅读更多...
最新文章

Copyright @ 2022~2023