【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词

简介: 【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词

题目1:904. 水果成篮

思路分析:

对于滑动窗口来说,我们会慢慢感觉滑动窗口并不难,就拿这道题来说,难的不是算法,而是怎么记录 果篮中已经装了多少种和 每种种类已经选择了多少棵树以及 果篮所选种类是什么。这三个点如果用 unordered_map来处理也是很简单,但频繁的删除,效率很低。

果篮中已经装了多少种: 主要是判断种类是否超过两种,出窗口判断时需要;

每种种类已经选择了多少棵树: 出窗口时,需要判断是否已经将该种树出完,种类数量才知道是否减少。

果篮所选种类是什么: 我们要支持果篮中种类的树进入窗口,就需要比对是否是果篮中记录的两种种类的树。


如何替换?根据题目给出的提示我们知道这个fruits[i]<=105 ,所以只用数组hash[100001]就可以记录所选种类以及已经选择种类的棵数。再用int kinds来记录种类数量就可以了


思路1:暴力枚举+哈希表

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


本题的滑动窗口分析:

进窗口:记录 right位置的种类数量,数据维护:果篮中的种类数量 kinds。

判断:当种类数量 kinds超过两种,就需要执行出窗口操作。出窗口:去除一个种类的树,让该类树在果篮的棵数变为0,种类数量 kinds减小。

更新结果:每进一次符合要求就更新一次。

代码实现:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001]={0};
        int left=0,right=0,kinds=0,n=fruits.size();
        int ret=0;
        while(right<n)
        {
            if(hash[fruits[right]]==0) kinds++;
            hash[fruits[right]]++;
            while(kinds>2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0) kinds--;
                left++;
            }
            ret=max(ret,right-left+1);
            right++;
        }
        return ret;
    }
};


LeetCode链接:904. 水果成篮


题目2:438. 找到字符串中所有字母异位词

思路分析:

我们先讨论如何判断两个字符串是异位词:无关顺序,但字母相同且各字母的数量也相同。所以我们只需要判断每个字母的数量就可以。


提示这里也说只有小写字母,总数有限,可以用哈希表;


初步思想: 两张哈希表分别统计s子串中各字母数量和p中各字母数量。如果两个表完全相同就是异位词。


思路1:暴力枚举+哈希表

列出所有长度为p.size()的子串,在比对两张哈希表,相同则push_back子串左端点下标进vector<int>容器。


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

对比哈希表来判断是否更新结果,这个过程需要同时遍历对比,太过于复杂,可以优化下。


用count来记录窗口中的有效字母的数量,当有效字母等于p.size()就可以更新数据。


本题的滑动窗口分析:

进窗口: hash2[in-'a']++; 维护数据: count。

判断:长度是固定的为 p.size(),超过就要出窗口。出窗口也要维护数据: count。

更新结果:当 count==p.size()就表明是异或词,更新结果。

代码实现:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> v;
        int hash1[26]={0};      //记录p中每个字符的个数
        for(int i=0;i<m;i++) hash1[p[i]-97]++;

        int hash2[26]={0};      //统计窗口中每一个字符出现的个数
        int count=0;            //记录有效字符的个数
        int left=0,right=0,n=s.size(),m=p.size();                
        while(right<n)
        {
            char in=s[right];
            hash2[in-'a']++;  //进窗口
            if(hash2[in-'a']<=hash1[in-'a']) count++; //维护数据
            while(right-left+1>m) //判断
            {
                char out=s[left];
                if(hash2[out-'a']<=hash1[out-'a']) count--; //维护数据
                hash2[out-'a']--; //出窗口
                left++;
            }
            if(count==m) v.push_back(left); //更新结果
            right++;
        }
        return v;
    }
};

LeetCode链接:438. 找到字符串中所有字母异位词


收获满满✨:

  • 滑动窗口思想,什么时候用和怎么用都在操作中熟悉了,目前最主要的是对题目的理解以及一些操作处理。比如上述题中:hash哈希表的运用就需要积累。
  • 有效数据个数count 代替 两张哈希表的对比。
相关文章
|
22天前
|
算法
力扣每日一题 6/23 字符串/模拟
力扣每日一题 6/23 字符串/模拟
11 1
|
22天前
|
索引
力扣每日一题 6/27 字符串 贪心
力扣每日一题 6/27 字符串 贪心
9 0
|
22天前
|
Python
力扣随机一题 模拟+字符串
力扣随机一题 模拟+字符串
9 0
|
22天前
力扣每日一题 6/22 字符串/贪心
力扣每日一题 6/22 字符串/贪心
8 0
|
22天前
力扣每日一题 6/18 字符串/模拟
力扣每日一题 6/18 字符串/模拟
10 0
|
22天前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
14 0
|
22天前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
11 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值