aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--fruit_into_baskets.c65
-rw-r--r--fruit_into_baskets.py37
2 files changed, 80 insertions, 22 deletions
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 <stdio.h>
-#include <stdlib.h>
+#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]))