大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193273.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...