[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

相关文章

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若