Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-02-07 09:57:52
904. Fruit Into Baskets
给你一个阵列fruits表示一整列的水果树,fruits[i]表示某一种类的水果,求出在满
足下列规则时,最多可以得到几个水果?
* 你有两个篮子,每个篮子只能装一种水果,篮子的空间是无限大
* 你每次只能从水果树中拿一颗水果,你可以从某个树开始拿,并且拿完i位置后就只
能拿i+1位置的果树(由左至右按顺序拿)
* 如果你已经拿了两种水果,遇到第三种水果时,你必须把其中一种水果全部丢掉
Example:
Input: fruits = [1,2,1]
Output: 3
Explanation: 我们可以拿所有的水果
Input: fruits = [0,1,2,2]
Output: 3
Explanation: 我们可以拿 [1,2,2] 这三颗果树的水果
Input: fruits = [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation:我们可以拿[1,2,1,1,2]这几颗果树的水果
思路:
1.本质上是一个连续子序列问题,这种问题肯定是用滑动窗口来解的。
2.我们不断的把水果加入窗口扩大窗口,窗口紧缩的条件为水果种类大于2,
并且不断的利用窗口的大小来更新结果。
3.当右边的指标到底的时候就可以求得解。
JavaCode:
作者: twosheep0603 (两羊)   2023-02-07 10:02:00
大师
作者: pandix (面包屌)   2023-02-07 10:34:00
第三个example应该要拿3吧

Links booklink

Contact Us: admin [ a t ] ucptt.com