將水果放入籃子 - LeetCode --- Fruit Into Baskets - LeetCode
Description
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
你想盡可能多地採摘水果。不過，主人有一些嚴格的規定你必須遵守：
- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
你只有兩個籃子，每個籃子只能裝一種水果。每個籃子可以容納的水果數量沒有限制。 - Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
從你選擇的任何一棵樹開始，你必須向右移動，從每棵樹（包括起始樹）上摘取恰好一個水果 。摘取的水果必須能放入你的一個籃子裡。 - Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
一旦你到達一棵果實放不進籃子的樹，你就必須停下來。
Given the integer array fruits, return the maximum number of fruits you can pick.
給定整數數組 fruits ，返回您可以挑選的最大水果數量 。
Solution
There are two method to solve it. Remarkably, one of the method is much faster than the other. So, let's see what's the different between thess two solutions.
這篇文章將提供兩種方法。並且，在學習完這兩種方法後，你會發現其中一種的速度驚人地快很多。所以趕快讓我們進入學習地世界吧！
method 1
Both of thess method use the concept of sliding window. If you are the first time learning this concept, I recommend this video。It has great anime to make learner understand easily.
這兩種方法都用到了 sliding window 的概念。如果是第一次接觸到這個概念，我推薦這部影片。其中包含了清楚的動畫讓使用者可以快速理解 sliding window 的概念。
from collections import defaultdict
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
left = 0
fruit_type = defaultdict(int)
best = 0
for current in range(len(fruits)):
fruit_type[fruits[current]] += 1
while len(fruit_type) > 2:
fruit_type[fruits[left]] -= 1
if fruit_type[fruits[left]] == 0:
del fruit_type[fruits[left]]
left += 1
best = max(best, sum(fruit_type.values()))
return best
If you really understand the concept of sliding window, the code above should be straightforward. The part might be raise question are the variable and the defaultdict in the first line. Let me explain it one by one.
如果有理解 sliding window 的概念，上方的程式碼應該不成問題。可能有疑問的地方是變數和第一行的 defaultdict。讓我逐個解釋。
defaultdict allows user to automatically create a key and asign it a default value when accessing a key that doesn't exist. Unlike a regular dictionary, it won't raise a KeyError when the key is missing. If we don't use defaultdict, the line 8 should add some judgement.
defaultdict允許使用者在存取不存在的鍵時，自動建立該鍵並賦予一個預設值。 不會像普通字典那樣在鍵不存在時拋出 KeyError。如果不使用 defaultdict，第 8 行需要再多一個判斷。
The variable left keeps track the left-end index of the window, making it easier to remove later. The variable fruit_type keeps track of how many types of fruit are currently in the window. A dictionary is used because of its key-value pair structure, and the fact that each key can only appear once, ensuring no duplicates. The variable best is responsible for recording the length of the longest window. The variable current in the for loop represents the current position and the right-end index of the window.
變數 left 記錄著窗戶的左端 index，方便之後刪除。變數 fruit_type 記錄著目前的 窗戶中有幾種水果，而選擇 dictionary 是因為他鍵值對的特性以及不能有重複的 key。變數 best 負責記錄最大窗戶長。for 迴圈的變數 current 代表現在位置以及窗戶最右端的 index。
method 2
This method is faster—by 174 milliseconds. That might not sound like much, but what if I told you that this small boost could elevate you from outperforming just 10% of others to beating over 94% of top performers? Tempting, right? Let's dive in and see how it works.
這個方法比較快，快了 174 ms。174 ms 可能聽起來沒什麼，但如果說這可以讓你從只贏過 10% 的人晉升為超越 94% 的頂尖人才，是否就聽起來心動多了呢？讓我們一起趕快看看吧。
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
best = 0
lasttype, secondtype, currentlength = -1, -1, 0
lastcount = 0
for currenttype in fruits:
if secondtype == currenttype or currenttype == lasttype:
currentlength += 1
else :
currentlength = lastcount + 1
if currenttype == lasttype:
lastcount += 1
else:
lastcount = 1
lasttype, secondtype = currenttype, lasttype
best = max(best, currentlength)
return best
I think what sets the second approach apart is that it doesn't use a dictionary to store the types and counts of fruit—instead, it relies on two variables.
我認為第二個方法最不一樣的地方在於它不是用 dictionary 來存水果種類和個數，而是用兩個變數來存。
After understanding the code, I strongly recommend readers try implementing it themselves. You’ll uncover clever design choices that simply can't be fully appreciated by just reading.
在理解完程式碼後，建議讀者一定要自己試試看，因為你將會從中發現他們的一些巧思，這是光用看的所無法體會的。
Hearing that someone give a like to this article will be lucky a week. ><
聽說幫這篇文章案讚的將會好運一整周。❤️
