当前位置：首页 > news >正文

力扣刷题904——水果成篮

news 2025/8/18 12:47:38

904——水果成篮（中等题）

题目：

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

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

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

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

第一次思路：

class Solution:def totalFruit(self, fruits: List[int]) -> int:if not fruits:return 0left = 0max_fruit = 0basket1 = None  # 用 None 表示篮子还空basket2 = Nonecount1 = 0count2 = 0for right in range(len(fruits)):fruit = fruits[right]if fruit == basket1:count1 += 1elif fruit == basket2:count2 += 1else:# 遇到第三种水果，需要缩小窗口while count1 > 0 and count2 > 0:left_fruit = fruits[left]if left_fruit == basket1:count1 -= 1if count1 == 0:basket1 = Noneelse:  # left_fruit == basket2count2 -= 1if count2 == 0:basket2 = Noneleft += 1# 分配空篮子if basket1 is None:basket1 = fruitcount1 = 1else:basket2 = fruitcount2 = 1# 更新最大水果数max_fruit = max(max_fruit, count1 + count2)return max_fruit

这个思路，但是太复杂了，做的过程繁琐耗时，并没有自己完全实现出来。

官方题解：

from typing import Listclass Solution:def totalFruit(self, fruits: List[int]) -> int:if not fruits:return 0left = 0max_fruit = 0basket = {}  # 用字典记录窗口内水果及数量
# enumerate 是 Python 的一个内置函数，它会把列表 fruits 同时输出“索引 + 元素”for right, fruit in enumerate(fruits):# 把当前水果加入篮子
# dict.get(key, default) 是 Python 字典的方法，
# 如果字典里有 key（这里是 fruit）：返回对应的值（数量）。
# 如果字典里没有 key：返回 default（这里是 0）basket[fruit] = basket.get(fruit, 0) + 1# 如果篮子超过两种水果，移动左指针缩小窗口while len(basket) > 2:# 取出 窗口最左边的水果类型left_fruit = fruits[left]# 移除最左边的水果类型basket[left_fruit] -= 1if basket[left_fruit] == 0:del basket[left_fruit]left += 1# 更新最大水果总数max_fruit = max(max_fruit, right - left + 1)return max_fruit