From ce6f29aefa492ee055732324adce4686b1b6d361 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 4 Aug 2025 07:37:43 +0100 Subject: 904. fruit into baskets --- fruit_into_baskets.c | 65 ++++++++++++++++++++++++++++++++++----------------- fruit_into_baskets.py | 37 +++++++++++++++++++++++++++++ 2 files changed, 80 insertions(+), 22 deletions(-) create mode 100644 fruit_into_baskets.py diff --git a/fruit_into_baskets.c b/fruit_into_baskets.c index 17316e5..e57c1a7 100644 --- a/fruit_into_baskets.c +++ b/fruit_into_baskets.c @@ -1,6 +1,5 @@ // 904. Fruit Into Baskets -#include -#include +#include "leetcode.h" /* * you are visiting a farm that has a single row of fruit trees arranged from @@ -15,29 +14,51 @@ */ int totalFruit(int *fruits, int fruitsSize) { - int n = fruitsSize, type = 0, left = 0, right = 0; - int *hash = calloc(n, sizeof(int)); - while (right < fruitsSize) { - if (hash[fruits[right]] == 0) - type++; - hash[fruits[right]]++; - right++; - if (type > 2) { - if (hash[fruits[left]] == 1) - type--; - hash[fruits[left]]--; - left++; + int max = 0, p1 = 0, p2 = 0, f1 = -1, f2 = -1, i, j = 0; + for (i = 0; i < fruitsSize; ++i) { + if (fruits[i] == f1) + ++p1; + else if (f1 < 0) { + f1 = fruits[i]; + p1 = 1; + } else { + f2 = fruits[i]; + p2 = 1; + break; } } - free(hash); - return right - left; + while (++i < fruitsSize) { + if (fruits[i] == f1) + ++p1; + else if (fruits[i] == f2) + ++p2; + else { + if (i - j > max) + max = i - j; + while (p1 > 0 && p2 > 0) { + if (fruits[j] == f1) + --p1; + else + --p2; + ++j; + } + if (!p1) { + f1 = fruits[i]; + p1 = 1; + } else { + f2 = fruits[i]; + p2 = 1; + } + } + } + if (fruitsSize - j > max) + return fruitsSize - j; + return max; } int main() { - int fruits1[] = {1, 2, 1}, fs1 = 3; - int fruits2[] = {0, 1, 2, 2}, fs2 = 4; - int fruits3[] = {1, 2, 3, 2, 2}, fs3 = 5; - printf("%d\n", totalFruit(fruits1, fs1)); // expect: 3 - printf("%d\n", totalFruit(fruits2, fs2)); // expect: 3 - printf("%d\n", totalFruit(fruits3, fs3)); // expect: 4 + int f1[] = {1, 2, 1}, f2[] = {0, 1, 2, 2}, f3[] = {1, 2, 3, 2, 2}; + printf("%d\n", totalFruit(f1, ARRAY_SIZE(f1))); // expect: 3 + printf("%d\n", totalFruit(f2, ARRAY_SIZE(f2))); // expect: 3 + printf("%d\n", totalFruit(f3, ARRAY_SIZE(f3))); // expect: 4 } 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])) -- cgit v1.2.3