[Algorithm][滑动窗口][水果成篮][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解

本文主要是介绍[Algorithm][滑动窗口][水果成篮][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.水果成篮
    • 1.题目链接
    • 2.算法原理讲解
    • 3.代码讲解
  • 2.找到字符串中所有字母异位词
    • 1.题目链接
    • 2.算法原理讲解
    • 3.代码实现
  • 3.串联所有单词的字串
    • 1.题目链接
    • 2.算法原理讲解
    • 3.代码实现
  • 3.最小覆盖字串
    • 1.题目链接
    • 2.算法原理讲解


1.水果成篮

1.题目链接

  • 水果成篮

2.算法原理讲解

  • 研究的对象是⼀段连续的区间,可以使⽤**「滑动窗⼝」**思想来解决问题
    • 将问题转化为:找出一个最长的子数组长度,子数组中不超过两种类型的水果
  • 让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种
  • 做法
    • 右端⽔果进⼊窗⼝的时候,⽤哈希表统计这个⽔果的频次
    • 这个⽔果进来后,判断哈希表的⼤⼩
      • 如果⼤⼩超过2:说明窗⼝内⽔果种类超过了两种
        • 那么就从左侧开始依次将⽔果划出窗⼝,直到哈希表的⼤⼩⼩于等于2,然后更新结果
      • 如果没有超过2:说明当前窗⼝内⽔果的种类不超过两种,直接更新结果ret
  • 优化
    • v1.0中,哈希表有大量的插入删除
    • v2.0中,由于水果类型最大值是一个定值,所以可以把hash数组写死,这样以空间换时间,不会存在哈希冲突
      • 此时不用STL容器,无法 O ( 1 ) O(1) O(1)判断水果种类数量,此时添加一个变量kinds即可
        请添加图片描述

3.代码讲解

// v1.0
// 模型转化为:数组只有两个元素的最大子数组
int TotalFruit(vector<int>& fruits) 
{int ret = 0;unordered_map<int, int> basket; // <水果种类 数量>for(int left = 0, right = 0; right < fruits.size(); right++){basket[fruits[right]]++; // 入窗口while(basket.size() > 2) // 判断{// 出窗口basket[fruits[left]]--;if(basket[fruits[left]] == 0){basket.erase(fruits[left]);}left++;}ret = max(ret, right - left + 1); // 更新数据}return ret;
}
---------------------------------------------------------------
// v2.0 优化
// 改造哈希表,以改善时间复杂度
int TotalFruit(vector<int>& fruits) 
{int ret = 0, kinds = 0;// 水果类型小于一个定值// 以空间换时间int basket[100001] = { 0 };for(int left = 0, right = 0; right < fruits.size(); right++){if(basket[fruits[right]] == 0){kinds++;}basket[fruits[right]]++; // 入窗口while(kinds > 2) // 判断{// 出窗口basket[fruits[left]]--;if(basket[fruits[left]] == 0){kinds--;}left++;}ret = max(ret, right - left + 1); // 更新数据}return ret;
}

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

1.题目链接

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

2.算法原理讲解

  • 思路:「滑动窗⼝」 + 「哈希表」
  • 做法
    • 因为字符串p的异位词的⻓度⼀定与字符串p的⻓度相同
      • 所以可以在字符串s中构造⼀个⻓度为与字符串p的⻓度相同的滑动窗⼝,并在滑动中维护窗⼝中每种字⺟的数量
    • 当窗⼝中每种字⺟的数量与字符串p中每种字⺟的数量相同时,则说明当前窗⼝为字符串 p的异位词
    • 因此可以⽤两个⼤⼩为26的数组来模拟哈希表
      • ⼀个来保存s中的⼦串每个字符出现的个数
      • 另⼀个来保存p中每⼀个字符出现的个数
      • 这样就能判断两个串是否是异位词
        ![[Pasted image 20240326190744.png]]
  • 优化:更新结果的判断条件 -> 利用count来统计窗口中"有效字符"的个数
    • 进窗口:进入后 -> if (hashS[in] <= hashP[in]) -> count++
    • 出窗口:出去前 -> if (hashS[out] <= hashP[out]) -> count--
    • 更新结果:count == len

3.代码实现

// 将问题转化为:p中的字母出现的次数与s中某个字串中出现的次数相同
// v1.0
vector<int> FindAnagrams(string s, string p) 
{vector<int> ret;int hashS[26] = { 0 };int hashP[26] = { 0 };// 将p如hashfor(auto& ch : p){hashP[ch - 'a']++;}// 处理sint len = p.size();for(int left = 0, right = 0; right < s.size(); right++){hashS[s[right] - 'a']++; // 入窗口if(right - left + 1 > len) // 判断窗口是否大了{hashS[s[left++] - 'a']--; // 出窗口}if(right - left + 1 == len) // 尝试更新数据{bool flag = true;for(int i = 0; i < 26; i++){if(hashP[i] != hashS[i]){flag = false;break;}}if(flag){ret.push_back(left);}}}return ret;
}
-----------------------------------------------------------------
// v2.0 优化更新结果的判断条件,不用每次都遍历hash了
vector<int> findAnagrams(string s, string p) 
{vector<int> ret;int hashS[26] = { 0 };int hashP[26] = { 0 };// 将p如hashfor(auto& ch : p){hashP[ch - 'a']++;}// 处理sint count = 0, len = p.size();for(int left = 0, right = 0; right < s.size(); right++){// 入窗口 + 维护countif(++hashS[s[right] - 'a'] <= hashP[s[right] - 'a']){count++; // 入窗口的字符是一个有效字符}if(right - left + 1 > len) // 判断窗口是否大了{// 维护countif(hashS[s[left] - 'a']-- <= hashP[s[left] - 'a']){count--; // 出窗口的元素是一个有效字符}left++; // 出窗口}if(count == len) // 更新结果{ret.push_back(left);}}return ret;
}

3.串联所有单词的字串

1.题目链接

  • 串联所有单词的字串

2.算法原理讲解

  • 如果把每⼀个单词看成⼀个字⺟,问题就变成了找到**「字符串中所有的字⺟异位词」**
    • ⽆⾮就是之前处理的对象是⼀个⼀个的字符,这⾥处理的对象是⼀个⼀个的单词
  • 注意的点 && 区别
    • 哈希表:hash<string, int>
    • left指针与right指针的移动
      • 移动的步长,是单词的长度len -> 一次跨过一个单词
    • 滑动窗口执行的次数:len
      • 因为无法确定起点是在哪儿,所以要执行len
      • 大于len次则没必要,因为第一次与第len+1次是重复的情况…
        请添加图片描述

3.代码实现

vector<int> findSubstring(string s, vector<string>& words) 
{int len = words[0].size();unordered_map<string, int> mapS;unordered_map<string, int> mapV;vector<int> ret;for(auto& str : words){mapV[str]++;}for(int i = 0; i < len; i++) // 滑动窗口的执行次数{int count = 0;for(int left = i, right = i; right + len <= s.size(); right += len){// 入窗口,截取子串,维护countstring str = s.substr(right, len);mapS[str]++;// 看看mapV中是否存在str,以避免插入不需要的值if(mapV.count(str) && mapS[str] <= mapV[str]) {count++;}// 判断窗口是否大了if(((right - left + len) / len) > words.size()){// 维护countstring tmp = s.substr(left, len);if(mapV.count(tmp) && mapS[tmp]-- <= mapV[tmp]){count--;}left += len; // 出窗口}if(count == words.size()) // 更新结果{ret.push_back(left);}}mapS.clear();}return ret;
}

3.最小覆盖字串

1.题目链接

  • 最小覆盖字串

2.算法原理讲解

  • 研究对象是连续区间,因此可以尝试使⽤「滑动窗⼝」的思想来解决

  • 如何判断当前窗⼝内的所有字符是符合要求的呢?

    • 可以使⽤两个哈希表,其中⼀个将⽬标串的信息统计起来,另⼀个哈希表动态的维护窗⼝ 内字符串的信息

    • 当动态哈希表中包含⽬标串中所有的字符,并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数,那么当前的窗⼝就是⼀种可⾏的⽅案

      请添加图片描述

  • 优化:判断条件 -> 使用变量count标记有效字符的种类
    请添加图片描述

string MinWindow(string s, string t) 
{// 仅用数组可以避免STL的开销,提高效率int hashS[128] = { 0 };int hashT[128] = { 0 };int kinds = 0;for(auto& ch : t){if(hashT[ch]++ == 0){kinds++;}}int begin = -1, minLen = INT_MAX;for(int left = 0, right = 0, count = 0; right < s.size(); right++){// 入窗口char in = s[right];// 维护count,仅统计t中有效字符的种类if(++hashS[in] == hashT[in]){count++;}while(count == kinds) // 判断{   // 更新if(right - left + 1 < minLen){begin = left;    minLen = right - left + 1;}// 出窗口 && 维护countchar out = s[left++];if(hashS[out]-- == hashT[out]){count--;}}}string ret = "";if(begin != -1){ret = s.substr(begin, minLen);    }return ret;
}

这篇关于[Algorithm][滑动窗口][水果成篮][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/920173

相关文章

Java操作PDF文件实现签订电子合同详细教程

《Java操作PDF文件实现签订电子合同详细教程》:本文主要介绍如何在PDF中加入电子签章与电子签名的过程,包括编写Word文件、生成PDF、为PDF格式做表单、为表单赋值、生成文档以及上传到OB... 目录前言:先看效果:1.编写word文件1.2然后生成PDF格式进行保存1.3我这里是将文件保存到本地后

windows系统下shutdown重启关机命令超详细教程

《windows系统下shutdown重启关机命令超详细教程》shutdown命令是一个强大的工具,允许你通过命令行快速完成关机、重启或注销操作,本文将为你详细解析shutdown命令的使用方法,并提... 目录一、shutdown 命令简介二、shutdown 命令的基本用法三、远程关机与重启四、实际应用

使用SpringBoot创建一个RESTful API的详细步骤

《使用SpringBoot创建一个RESTfulAPI的详细步骤》使用Java的SpringBoot创建RESTfulAPI可以满足多种开发场景,它提供了快速开发、易于配置、可扩展、可维护的优点,尤... 目录一、创建 Spring Boot 项目二、创建控制器类(Controller Class)三、运行

springboot整合gateway的详细过程

《springboot整合gateway的详细过程》本文介绍了如何配置和使用SpringCloudGateway构建一个API网关,通过实例代码介绍了springboot整合gateway的过程,需要... 目录1. 添加依赖2. 配置网关路由3. 启用Eureka客户端(可选)4. 创建主应用类5. 自定

最新版IDEA配置 Tomcat的详细过程

《最新版IDEA配置Tomcat的详细过程》本文介绍如何在IDEA中配置Tomcat服务器,并创建Web项目,首先检查Tomcat是否安装完成,然后在IDEA中创建Web项目并添加Web结构,接着,... 目录配置tomcat第一步,先给项目添加Web结构查看端口号配置tomcat    先检查自己的to

使用Nginx来共享文件的详细教程

《使用Nginx来共享文件的详细教程》有时我们想共享电脑上的某些文件,一个比较方便的做法是,开一个HTTP服务,指向文件所在的目录,这次我们用nginx来实现这个需求,本文将通过代码示例一步步教你使用... 在本教程中,我们将向您展示如何使用开源 Web 服务器 Nginx 设置文件共享服务器步骤 0 —

SpringBoot集成SOL链的详细过程

《SpringBoot集成SOL链的详细过程》Solanaj是一个用于与Solana区块链交互的Java库,它为Java开发者提供了一套功能丰富的API,使得在Java环境中可以轻松构建与Solana... 目录一、什么是solanaj?二、Pom依赖三、主要类3.1 RpcClient3.2 Public

手把手教你idea中创建一个javaweb(webapp)项目详细图文教程

《手把手教你idea中创建一个javaweb(webapp)项目详细图文教程》:本文主要介绍如何使用IntelliJIDEA创建一个Maven项目,并配置Tomcat服务器进行运行,过程包括创建... 1.启动idea2.创建项目模板点击项目-新建项目-选择maven,显示如下页面输入项目名称,选择

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》:本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode(VSCode)中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境:详细教程1. 什么是 VSCode?2. 安装 VSCo