Leetcode — 904. Fruit Into Baskets (中文)

問題連結: https://leetcode.com/problems/fruit-into-baskets/

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets. If you cannot, stop.
2. Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

想法:

如果看過我的其他篇中文題目講解的人, 可能會發現我這次直接複製在Leetcode上的題目敘述與範例, 沒有幫忙把題目翻譯, 其實是因為這題題目講解得實在沒有很白話, 我大概看了好幾次才懂這題要幹嘛, 因此我想直接在這裡用我的方法來"改寫"題目

上述落落長的題目其實就是指:

題目給予一個整數陣列tree, tree[i]代表的是在第i個樹所種出來的水果種類(水果種類將由數字來代表) 
你至多只能從一顆樹上摘一顆水果, 雖然並沒有限制你能從幾棵樹上摘水果, 但你的手上至多只能拿兩種不同的水果 
若你決定從第i個樹開始摘水果, 你可以在接下來的每棵樹都摘水果, 直到你碰到了第三個類型的水果, 你就不能摘了, 不然會違反規定, 因此決定從哪棵樹開始摘水果很重要
題目要求你在這個條件下, 回傳你最多可以摘多少顆水果

而因為根本很難一看整個陣列就知道我們該從哪裡開始摘水果, 那我們可以變成我們在走到每棵樹的時候都決定摘, 若我們從第一棵樹摘到現在這棵樹tree i的時候的總水果種類已超過2個的時候, 那我們只要假設我們不是在第一棵樹開始摘的就好, 我們只要可以知道我們從 可以被允許最遠的tree j 開始摘 摘到現在的tree i就好, 所以tree j到tree i所累積的水果數量就是合法的

👷給個例子, 當一開始的整數陣列為 [1,2,2,3,2,2].

數字可能不好聯想整個情況, 讓我們把這些數字轉成我們人類生活的水果名稱: 1 = apple🍎, 2 = banana🍌, 3 = pineapple🍍

所以整個流程會是:

🔧Step 1. 我們摘種類1的水果 — 蘋果, 現在我們手上有的水果是一顆蘋果: [ 🍎]

🔧Step 2. 我們摘種類2的水果 — 香蕉, 現在我們手上有的水果是一顆蘋果及一根香蕉: [ 🍎, 🍌]

🔧Step 3. 我們摘種類2的水果 — 香蕉, 現在我們手上有的水果是一顆蘋果及二根香蕉: [ 🍎, 🍌, 🍌]

🔧Step 4. 我們摘種類3的水果 — 鳳梨, 然而, 我們手上已經有兩種不同種類的水果了, 因此我們需要放棄前面摘過的部分水果, 才能把鳳梨加進我們手中, 現在我們手上有的水果是二根香蕉跟一個鳳梨 : [ 🍌, 🍌, 🍍]

🔧Step 5. 我們摘種類2的水果 — 香蕉, 現在我們手上有的水果是三根香蕉跟一個鳳梨: [ 🍌, 🍌, 🍍, 🍌]

🔧Step 6. 我們摘種類2的水果 — 香蕉, 現在我們手上有的水果是四根香蕉跟一個鳳梨: [ 🍌, 🍌,🍍, 🍌, 🍌]

🚧經過所有樹的期間, 最多可以有五個水果停留在我們手上

在上述的例子, 你可能發現了有幾個我們必須先解決的事情才能知道如何解這題:

1. 當我們走到樹i的時候, 我們手上所擁有的是哪兩個不同種類的水果?
2. 當我們遇到第三種類水果的時候, 我們要怎麼決定捨棄哪個種類的水果?
3. 我們要如何知道自己手上有多少顆水果?

其實前兩個問題不難,

1. 我們可以用變數來紀錄我們目前手上拿的是哪兩種種類的水果
2. 而若我們需要加新種類水果到我們手上的時候, 我們應該是要留我們在這棵樹的前一棵樹的水果種類, 不然我們就會必須捨棄掉在這棵樹之前的所有水果了

接著剛剛回答第二點的答案, 我們繼續講這個捨棄水果的環節, 當我們決定捨棄另一個種類的水果時,代表雖然不用全部水果都要丟掉, 但因為有一部分水果是我們捨棄的水果種類, 因此這些跟捨棄水果有關的所有水果都需要丟掉, 因此我們只留 我們最後一次拿捨棄水果 之後開始拿的所有水果

有點繞口, 讓我們來看例子, 假設我們在遇到一個新水果種類之前(假設是鳳梨好了), 現在手上有這些蘋果和梨子[ 🍎, 🍐, 🍎,🍐,🍐]
我們決定留梨子 🍐, 因為他是我們現在新種類的最後一個水果, 那我們現在就只能留 我們最後一次拿蘋果之後的梨子們, 因此我們捨棄蘋果後只剩下 [🍐,🍐]

因此, 我們需要隨時記錄現在遇到的水果已經連續幾個了, 如果遇到新種類的水果, 那就又從頭開始計算現在這個新種類的水果連續幾個 (有點像我們遊戲裡面的combo數的概念🎮 🙉

程式邏輯:

我們先介紹一下我們程式中使用的變數:

1. type1, type2: 紀錄現在我們手上是哪兩個水果種類, 注意我們會隨時讓type1 為我們現在位置的前一棵樹的水果種類(也就是type1=tree[i-1])
2. combos: 數我們目前已經連續遇到幾個水果種類為type1 的水果了, 假設combos的值為2, 則代表 tree[i-2] 和 tree[i-1]都是 type1 的水果, tree[i-3]則不是
3. curLen: 數目前手上我們有幾顆水果
4. max: 紀錄我們目前手上曾經有的最多水果的顆數

而我們在程式裡面做的事情就是要一直維護上面的變數們:

• 當必需的時候, 更新(或互換) type1 和 type2 的值, 因為 type1 需一直是前一棵樹tree[i-1]的水果種類
• 當type1的值一變動的時候, combos會設為1(代表從頭計算新種類水果)
• 當我們遇到一個不是type1或type2種類的水果的時候, curLen的值(也就是我們手上的水果數)就必須要重新計算, 但要記得curLen並不是從1開始計算, 因為我們仍然會保留部分跟tree[i-1]同種類的水果們

以下為 4ms的程式碼, 贏過 99% —

public int totalFruit(int[] tree) {
        int n = tree.length;
        int type1 = tree[0], type2 = -1;
        int combos = 1;//assume type1 is prev type
        int curLen = 1, max = 1;
        for(int i=1;i<n;i++)
        {
            if(tree[i] != type1 && tree[i] != type2 && type2!=-1)
            {
                max = Math.max(curLen, max);
                curLen = combos + 1;
                type2 = type1; 
                type1 = tree[i];
                combos = 1;
                continue;
            }
            if(tree[i] == type1)
                combos++;
            else //swap type1 and type2 
            {
                type2 = type1;
                type1 = tree[i];
                combos = 1;
            }
            curLen++;
        }
        return Math.max(max,curLen);
    }