当前位置:   article > 正文

LeetCode904. 水果成篮

904. 水果成篮
904. 水果成篮(学到新方法会更新)
一、题目

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

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

(1)你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
(2)你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
(3)一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
  • 1
  • 2
  • 3
  • 4
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
  • 1
  • 2
  • 3
  • 4
  • 5
示例 3:
输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
  • 1
  • 2
  • 3
  • 4
  • 5
示例 4:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。
  • 1
  • 2
  • 3
  • 4

提示:

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

来源:力扣(LeetCode
链接:https://leetcode.cn/problems/fruit-into-baskets
著作权归领扣网络所有。

二、解法
方法一:三指针+类似滑动窗口

一、读题

(1)看题目,找到一个不符合的就停下,比如1、2、3、2、2,比如前两个1和2类水果均放到篮子里,那么到3就必须停下,因此可以看出,我们找的就是一个子数组,这个子数组中只有两类水果,数组的长度越长越好。

二、思路

建立三个指针,left\middle\right(初始值均为0,代表数组下标);分工如下:left和middle代表相邻两种水果(有可能是同一种)(比如1、1、2、1、2、3,1和2就是相邻两种不同水果,1和1也可以算,后面就知道为什么了),right是去寻找新的一种,当寻找到的时候,left和middle各自往后移动一种(right遇到3,那么left和middle分别变成2、3)。
具体操作:
(1)right等于left或者是middle的时候,一直向右移动,如果不等于left和middle的话说明right遇到了left和middle外的第三类水果(如果left和middle相等就是第二类水果),就先停下。
(2)遇到第三类水果的时候,分为两种情况,第一种是1、1、2、1、2、2、3、3,遍历到2的时候right就相当于遇到了第二类水果(不同于left和middle),此时让left=middle=0,middle=right=2,记录下新水果的类别,然后right继续向后遍历;第二种情况是第一种情况发生以后right继续遍历,当到3的时候,遇到了1和2以外的不同的数字(遇到了第三种水果),如果这时候和前面一样,left=middle=2,right=middle=6,那么我们会发现left\middle\left~middle之间会有三种水果,就不符合我们的设定了(left和middle是相邻的两种不同水果),因此我们先将middle设置成为新水果3,然后将left设置成为新水果3的前面一位,也就是fruits[5],向前遍历到不等于fruit[5]为止,然后向后再加一位重新等于fruit[5],这样就记录下了符合要求的left。
(3)什么时候得到max?当right找到新的值以后,就记录下right-left,然后找到更大的,就记录下更大的(详情见代码)。

三、代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0, middle = 0;
        int max = 0;
        bool flag = 1;
        //移动right指针
        while (right < fruits.size()) {
            //right等于left或者是middle的时候,一直向右移动
            while (right < fruits.size() && (fruits[right] == fruits[left] || fruits[right] == fruits[middle])) {
                //出现第二种情况
                if (fruits[right] == fruits[left] && fruits[right] != fruits[middle]) flag = 0;
                right++;
            }
            //更新max
            max = (right - left) > max ? (right - left) : max;
            //第二种情况
            if (flag == 0) {
                middle = right;
                left = middle - 1;
                while (fruits[left] == fruits[middle - 1]) {
                    left--;
                }
                left++;
            }
            //第一种情况
            else {
                left = middle;
                middle = right;
            }
        }
        return max;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
方法二:滑动窗口

一、思路

定义四个指针
j 负责遍历fruits数组;
f1 为第一种水果类型的起始索引,即第一个篮子的起始索引;
f2 为第二种水果类型的起始索引,即第二个篮子的起始索引;
t 为未来两个篮子里的第一个篮子的起始索引。
滑动窗口的左边界为 f1,右边界为 j。

更新 j
通过for循环使 j 从 0 遍历到 fruits.size()-1 。

更新 f1
f1 初始为0,当遍历到第三种水果类型时,若 f1!=f2,则更新f1 为 t,即f1=t,保证计算子序列长度时只有两种水果类型。

更新 f2
f2 初始为0,当遍历到第二种水果类型或第三种水果类型时,则更新 f2 为 j,即f2=j,保证计算子序列长度时只有两种水果类型。

更新 t
t 初始为0,每次 t 与当前的 j 作对比,当 fruits[t]!=fruits[j]时,更新 t 为 j,即 t=j,作为未来两个篮子里的第一个篮子的起始索引。
C++版本:

```cpp
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //当fruits数组长度≤2,则直接返回fruits数组长度
        if(fruits.size()<3) return fruits.size();
//mn为结果,即fruits数组中包含两个不同水果类型的最大子序列长度
        int mn=0;
/*j为遍历fruits数组的指针,也是滑动窗口的右边界,f1,f2分别为第一个和第二个篮子
的起始索引,f1同时也是滑动窗口的左边界,t为未来两个篮子里的第一个篮子的起始索
引*/
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++)
        {
/*当f1=f2时,fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第二个篮子
要装的第二种水果;当f1!=f2时,fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明
遇到的是第三种水果*/
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2])
            {
/*当f1=f2时,说明第一个篮子已经装了一种水果,第二个篮子里还没有装,不更新f1,
只更新f2,即往第二个篮子里装第二种水果;
当f1!=f2时,fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第三种水果,
则更新f1和f2,即当前两个篮子的两种水果已装满,更新f1和f2为未来两个篮子里的两种
水果*/
                if(f1!=f2) f1=t;
                f2=j;
            }
/*t寻找未来两个篮子中第一个篮子要装的一种水果的起始索引,每次t与当前的j作对比,
当fruits[t]!=fruits[j]时,更新t=j*/
            if(fruits[t]!=fruits[j]) t=j;
/*更新当前子序列的长度,即每次计算装入两个篮子中的水果总数目*/
            mn=mn>(j-f1+1)?mn:(j-f1+1);
        }
        return mn;//返回最终结果mn
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size()<3) return fruits.size();
        int mn=0;
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++){
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]){
                if(f1!=f2) f1=t;
                f2=j;
            }
            if(fruits[t]!=fruits[j]) t=j;
            mn=mn>(j-f1+1)?mn:(j-f1+1);
        }
        return mn;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

作者:Linken_54
链接:https://leetcode.cn/problems/fruit-into-baskets/solution/by-0xula58rcn-umun/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/680369
推荐阅读
相关标签
  

闽ICP备14008679号