diff options
author | Jack Sangdahl <[email protected]> | 2025-08-04 07:37:43 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-04 07:37:43 +0100 |
commit | ce6f29aefa492ee055732324adce4686b1b6d361 (patch) | |
tree | 3e1491a1c546811de0d26dacab6d049e7a8756f0 /fruit_into_baskets.py | |
parent | 23f4ec5bfd6efc70417e3952217e11efd75b9d23 (diff) | |
download | leetcode-ce6f29aefa492ee055732324adce4686b1b6d361.tar.gz leetcode-ce6f29aefa492ee055732324adce4686b1b6d361.zip |
904. fruit into baskets
Diffstat (limited to 'fruit_into_baskets.py')
-rw-r--r-- | fruit_into_baskets.py | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/fruit_into_baskets.py b/fruit_into_baskets.py new file mode 100644 index 0000000..9197d03 --- /dev/null +++ b/fruit_into_baskets.py @@ -0,0 +1,37 @@ +# 904. Fruit Into Baskets + +""" +you are visiting a farm that has a single row of fruit trees arranged from +left t oright. the trees are represented by an integer array 'fruits' where +'fruits[i]' is the type of fruit the i'th tree produces. you want to collect +as much fruit as possible. however, the owner has some strict rules that you +must follow: you can only have two baskets and each can only hoold a single +type of fruit (unlimited quantity). starting from any tree, you must pick +exacty one fruit from every tree while moving to the right. once you reach a +tree with fruit that cannot fit in your baskets, you must stop. given the int +array 'fruits', return the maximum number of fruits you can pick +""" + + +class Solution(object): + def totalFruit(self, fruits): + """ + :type fruits: List[int] + :rtype: int + """ + cnt, i = {}, 0 + for j, v in enumerate(fruits): + cnt[v] = cnt.get(v, 0) + 1 + if len(cnt) > 2: + cnt[fruits[i]] -= 1 + if cnt[fruits[i]] == 0: + del cnt[fruits[i]] + i += 1 + return j - i + 1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.totalFruit(fruits=[1, 2, 1])) + print(obj.totalFruit(fruits=[0, 1, 2, 2])) + print(obj.totalFruit(fruits=[1, 2, 3, 2, 2])) |