大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
904. 水果成篮
题目描述
题目链接：904水果成蓝
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
解题思路
树由整数数组fruits表示，其中水果[i]是第i棵树产生的水果类型。 你想收集尽可能多的水果。但是，所有者有一些严格的规则，您必须遵守： 你只有两个篮子，每个篮子只能装一种水果。每篮水果的数量没有限制。 从您选择的任何一棵树开始，您必须在向右移动时从每棵树（包括起始树）中恰好摘下一个水果,摘下的水果必须放在你的一个篮子里。 一旦你到了一棵树上，树上的果实没法放入你的篮子（两个篮子已经满了），你必须停下来。 给定整数数组水果，返回可以拾取的最大水果数。 本题，其实就是选只有两个元素的最长连续子序列，比如1，2，3，2，2最长就是2，3，2，2（只包括2或者3，而且是最长的）。
代码演示–暴力解法
def totalFruit(fruits):
""" :type fruits: List[int] :rtype: int """
res = 0
num = []
for i in range(len(fruits)):
j = i
while (len(set(num)) <= 2 and j < len(fruits)):
num.append(fruits[j])
j += 1
if(len(set(num)) <= 2 ):
res = max(res, len(num))
elif(len(set(num)) == 3):
res = max(res,len(num) - 1)
del num[:]
return res
# fruits = [1,2,1]
# fruits = [0,1,2,2]
# fruits = [1,2,3,2,2]
# fruits = [3,3,3,1,2,1,1,2,3,3,4]
fruits = [1,1]
r = totalFruit(fruits)
print(r)
超时间限制，呜呜呜
代码演示–滑动窗口
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
if(len(fruits) == 1 or len(fruits) == 2):
return len(fruits)
# 记录当前篮子里的水果
basket1 = -1
basket2 = -1
sum = 0
# 记录当前的水果和当前水果的起始位置
curfruit = -1
curfruitloc = 0
subsum = 0
# 当前篮子起始位置
index = 0
for i in range(len(fruits)):
if(fruits[i] == basket1 or fruits[i] == basket2):
if(fruits[i] != curfruit):
curfruit = fruits[i]
curfruitloc = i
else:
index = curfruitloc
curfruitloc = i
if(basket1 == curfruit):
basket2 = fruits[i]
curfruit = basket2
else:
basket1 = fruits[i]
curfruit = basket1
subsum = i - index + 1
sum = sum if sum > subsum else subsum
return sum
参考
链接：https://leetcode-cn.com/problems/fruit-into-baskets
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/193273.html原文链接：https://javaforall.net
