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

一时失言乱红尘 2024-03-02 08:40 6阅读 0赞

## ![e7f21e0bdcbf4df89b8fd894ec23e149.png][] ##

## 904. 水果成篮 ##

[904. 水果成篮][904.]

### 题目描述： ###

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

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

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

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

![9b7e15995080434bbe12dc734c5fcbd7.png][]

### 解题思路： ###

> 本题可以转化为最长的连续子数组（最多只能有两种种类的水果），可以用滑动窗口来解决
> 
> 我们从左往右right一直走，当找到了一段符合条件的子序列，我们需要继续向右验证最长的这个特性，该如何操作呢？我们来看一下，以下【left，right】是寻找过程中符合题目条件的一个子序列
> 
> ![002d0cc57fd3414685c34f007af35a19.png][] 此时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）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

### 题目描述： ###

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

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

### ![bd7178161415410d85580dd1da04d27c.png][] 解题思路： ###

> 我们先通过暴力解法来分析一下题目：
> 
> 我们可以遍历s中每个位置，让他们跟p进行判断是否为异位词
> 
> ![bdf4d37779c94c1095ddd918348045e7.png][]
> 
> 我们发现这是一个滑动区间【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;
        }
    };

![dd8227fa0b024a59a766bd0b2d30b0f2.gif][]

[e7f21e0bdcbf4df89b8fd894ec23e149.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/7cb7ae460f2344e6b49362d1498ae50a.png
[904.]: https://leetcode.cn/problems/fruit-into-baskets/
[9b7e15995080434bbe12dc734c5fcbd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/1ea6fbe414dd4b8aaa1a18a11978c63c.png
[002d0cc57fd3414685c34f007af35a19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/6ac05f7ec0464b709a4958f866a5e103.png
[LeetCode_ -]: https://leetcode.cn/problems/find-all-anagrams-in-a-string/
[bd7178161415410d85580dd1da04d27c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/8f7229995aa643f8878aa41ff5d270bf.png
[bdf4d37779c94c1095ddd918348045e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/306cbac79f6643c79ee54679567a3ae9.png
[dd8227fa0b024a59a766bd0b2d30b0f2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/df98a1975a3f4cbfa332e899aace1d5b.png