cpp刷题打卡记录5—

cpp刷题打卡记录5——水果成篮

2026-02-04 00:52:32 栏目：最新资讯 5 阅读

题目力扣链接

题目简述：

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

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

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

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

题目代码：

1、自己尝试：

class Solution {
public:
    int totalFruit(vector& fruits) {
        int slow = 0, fast = 0;
        int treeNums = 0;
        int result = INT32_MIN;
        for(fast = 0; fast < fruits.size(); fast++){
            if(fruits[fast] != fruits[slow] && fruits[fast] != fruits[slow+1]){
                slow++;
            }
        }
        treeNums = fast - slow; //为什么不是fast-slow+1呢，因为出循环的时候fast还加了一次
        result = result > treeNums ? result : treeNums;
        return result;
    }
};

错误代码，没有考虑到完整情况。代码的思想是默认slow和slow+1索引对应的值必定是不同的类型，然后只要不等于这两个就是遇见了第三种水果，就开始移动slow。写的太搞笑了，一点没有考虑清楚，直接忽略了全是同一种水果和连续很多同种水果。

2、

class Solution {
public:
    int totalFruit(vector& fruits) {
        int slow = 0, fast = 0;
        int type1 = -1, type2 = -1;
        int count1 = 0, count2 = 0;
        int treeNums = 0;
        for(fast = 0; fast < fruits.size(); fast++){
            int currentFruit = fruits[fast];
            if(type1 == -1){
                type1 = currentFruit;
                count1++;
            }
            else if(type2 == -1 && currentFruit != type1){ //一定要注意currentFruit != type1这个条件
                type2 = currentFruit;
                count2++;
            }
            else if(currentFruit == type1){
                count1++;
            }
            else if(currentFruit == type2){
                count2++;
            }
            else{ //遇到第三种水果
                while(count1>0 && count2>0){
                    if(fruits[slow] == type1){
                        count1--;
                    }
                    else if(fruits[slow] == type2){
                        count2--;
                    }
                    slow++;
                }
                if(count1 == 0){
                    type1 = currentFruit;
                    count1 = 1;
                }
                else{
                    type2 = currentFruit;
                    count2 = 1;
                }
            }
            treeNums = max(treeNums, (fast- slow+ 1));//！！注意这个记录数量的位置（只摘前两种水果可能也会是最大的数量）
        }
        return treeNums;
    }
};

新增type1和type2记录两种不同类型的水果，count1和count2记录两种不同类型水果的数量。当遇见第三种水果时，开始向前移动slow并且往外面拿水果（因为只有一个篮子空了才能去装别的类型的水果），直到把某个篮子拿空，再重新装入新的类型的水果。因此此代码时间复杂度为O(n)，空间复杂度为O(1)。

3、利用哈希表（应该是代码最简洁的方法）

class Solution {
public:
    int totalFruit(vector& fruits) {
        int left = 0;               // 窗口左边界
        int maxFruits = 0;          // 最大水果数
        unordered_map basket;  // 记录窗口内每种水果的数量
        
        for (int right = 0; right < fruits.size(); right++) {
            // 将当前水果加入窗口
            basket[fruits[right]]++;
            
            // 如果窗口内水果种类超过2种，移动左指针
            while (basket.size() > 2) {
                basket[fruits[left]]--;  // 减少左边界水果的数量
                if (basket[fruits[left]] == 0) {
                    basket.erase(fruits[left]);  // 如果数量为0，从map中移除
                }
                left++;  // 移动左指针
            }
            
            // 更新最大水果数
            maxFruits = max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
};

不太会写出来，但是能看懂，主要是对于map极其不熟悉。时间复杂度为O(n)，空间复杂度为O(1)。该方法主要是利用了map的特性，map里面存的数据都是成对出现的（如{1,2}），对应到题目中就是让key作为水果的种类，value作为对应某一类水果的数量。

map中插入方法（如basket[4]=40）的特性是，插入{4,40}，但这种方法有一特殊之处就是当如果写一个key不存在的数，这种方法会自动给该key值对应的value赋成0。所以basket[fruits[right]]++有两种情况：当fruits[right]在表中存在时，给所对应的value值+1；当fruits[right]不存在时，根据特性给其value值赋值成0，然后再++，成1。

也可以使用insert的插入方式：

basket[fruits[right]]++

就等同于

unordered_map::iterator it1 = basket.find(fruits[fast]);

if(it1 == basket.end()){

basket.insert(make_pair(fruits[fast], 1));

}

else{

it1->second++;

}

显然利用中括号的插入方式能更好利用其特性，使代码更加简洁。

图解过程：