分析题目
原题如下:
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
- 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
- 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。
然后我们来分析一下题目:
-
我们的目标是什么?对,“收集的水果的 最大 数目。”。
翻译成人话就是,本题要求我们在限定条件下收集到最多的水果数量。 -
目标有了,那现在让我们来把抽象的条件具象化。
- 收集的水果种类最多只能有两种
- 不能回头重新收集,也就是:要连续进行收集
-
那么现在总结一下就是,题目问我们最多能连续收集多少个两种种类的水果?
解题思路
现在题目能理解了,就要开始思考解题思路了。
如上所述,关键点是:“最多”“连续”和“两种”
那么现在我们可以想到这样一个思路:因为要连续收集两种不同的水果,所以我们可以想到用指针来指向起点和终点,通过遍历果树的同时增大指针终点,使得起点与终点之间的间隔尽可能大,从而得到一个最大的结果。
看起来没有问题,所以现在就是要想具体的解决方案了:
- 既然要用指针指向起点和终点了,那肯定就要先决定变量了,所以用 left 指向起点,right 指向终点。
- 那现在问题来了,要怎么移动终点呢?很明显,用循环来遍历每颗果树,然后遍历到了哪颗果树,终点就在哪。
- 最后,用 max 来储存right(终点)-left(起点)的值,就是能摘到水果的最大值了!
- 等等,好像有哪里不对?既然有最大值,那也应该会有不是最大值的值吧?为什么这里没有出现?噢!水果的种类不止两种,是可能出现第三种甚至第四种的!
- 所以现在问题又来了,我们要怎么确定自己取得的值是仅限两种水果的呢?哎有了,只要出现了第三种水果了,那就放弃掉原先第一种水果不就行了?也就是让(原)第二种水果成为(现)第一种水果,(原)第三种水果成为(现)第二种水果,那就又是仅限两种水果了!
- 不过还有问题,那连续摘取两种水果的最大值 max 要怎么办啊?so easy~对比不就好了?只要每次遍历果树时,都把现在这两种水果所取得的最大值赋值给 n ,然后再让 n 跟 max 比大小就行了!
- 看起来真是完美呢,肯定能直接运行了吧!哎,什么?还有BUG?不可能吧?在哪里?哈?每次换水果种类的时候,起点要定在哪?笨哎你,直接定在之前的终点不就行了!直接就是一个顿挫,完美~
- 不可以的啦!直接定在终点的话,那如果原先那两个种类的水果是连续的要怎么办?就像“2,1,1,1,3”,那是不是就要把前两个“1”给扔掉了?那是不是就会漏掉几个水果了?
- 所以我的解决方法就是:用 z 来存储连续的水果个数,然后换种类的时候再把 z 加上去!具体实施就是在每次遍历果树的时候,顺带匹配一下当前水果的种类跟上一个水果的种类是否一样,一样的话就使得 z+=1,否则就让 z=1,也就是连续的个数就是 1。这下就是真正的完美了~
如上就是具体的解题思路了,以下是代码:
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
# 用 a 来存储水果种类1,用 b 来存储水果种类2,然后又因为不知道第二个种类的水果什么时候才会出现,甚至不知道会不会有第二个种类的水果,所以就把 b 设为-1了,
a,b,max=fruits[0],-1,1
# left 是起点的意思,起点必然是0,这个不用多说了吧?然后 z 是最后水果的连续出现的个数,最少都是 1.
left,z=0,1
size = len(fruits)
for right in range(1,size):
# 如果没有出现过第二种种类的水果且这个水果跟 a 不符,就把这个水果赋值给 b(第二种水果的种类)
if b==-1 and fruits[right]!=a:
b=fruits[right]
# 这里应该不用多说?就是最新出现的水果是与众不同的第三种水果的时候执行啦~
elif fruits[right]!=a and fruits[right]!=b:
# 这里应该也能理解?就是1. 起点=终点-连续值;2. 把最新出现的水果种类和上一个水果种类重新赋值给a,b
left=right-z
a=fruits[right-1]
b=fruits[right]
if fruits[right]==fruits[right-1]:
z+=1
else:
z=1
n=right-left+1
if n>max:
max=n
return max
# 后面好像也没什么好说的了,都在解题思路里说的很清楚了。
标签:水果,right,904,max,力扣,终点,fruits,成篮,种类
From: https://www.cnblogs.com/aduiduidui/p/17557228.html