【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词

 904. 水果成篮

904. 水果成篮

题目描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

解题思路： 

本题可以转化为最长的连续子数组（最多只能有两种种类的水果），可以用滑动窗口来解决

我们从左往右right一直走，当找到了一段符合条件的子序列，我们需要继续向右验证最长的这个特性，该如何操作呢？我们来看一下，以下【left，right】是寻找过程中符合题目条件的一个子序列

 此时right需要向右++，这个时候可能会出现两种情况：

• right++后，kind（水果的种类）不变
• right++后，kind减小，

这里值得注意的是当水果的种类减少后需要进行一下处理

 解题代码：

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

---

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

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述： 

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 解题思路：

我们先通过暴力解法来分析一下题目：

我们可以遍历s中每个位置，让他们跟p进行判断是否为异位词

我们发现这是一个滑动区间【left，right】的解法，我们来想办法实现其优化

首先我们可以利用哈希表hash1来存储p中每个字符和其个数 ，并且可以在滑动期间中利用hash2来记录s中的字符和个数

我们这里还需要一个变量length=p.size(），以及一个变量count来记录有效字符的个数

1.进窗口——hash2[s[right]]++

if(hash2[s[right]]<=hash1[s[right]]) count++;

2.当right-left+1>length进行判断

3.出窗口——hash2[s[left]]--

if(hash2[s[left]]<=hash1[s[left]]) count--;//在出窗口前更新count

4.更新结果——count==length

!这里的哈希表可以用大小为26的数组代替，并且速度更快

解题代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int>ret;
        int length=p.size();
        unordered_map<char,int>hash1;
        for(int i=0;i<p.size();i++) hash1[p[i]]++;
        unordered_map<char,int>hash2;
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            char ch=s[right];
            //进窗口
            hash2[ch]++;
            if(hash2[ch]<=hash1[ch]) count++;
            //判断
            if(right-left+1>length)
            {
                char out=s[left];
                if(hash2[out]<=hash1[out]) count--;//在出窗口前更新count
                hash2[out]--;//出窗口
                left++;
            }
            //更新结果
            if(count==length)
                ret.push_back(left);
        }
        return  ret;
    }
};