Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/02/07 09:57)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串221/719 (看更多)

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： ----------------------------------------- class Solution { public int totalFruit(int[] fruits) { int res = 0; int n = fruits.length; int[] window = new int[n]; int types = 0; int l = 0, r = 0; while (r < n) { if (window[fruits[r]] == 0) { types++; } window[fruits[r]]++; while (types > 2) { window[fruits[l]]--; if (window[fruits[l]] == 0) { types--; } l++; } res = Math.max(res, r - l + 1); r++; } return res; } } ----------------------------------------- -- https://i.imgur.com/sjdGOE3.jpg