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