1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// 904. Fruit Into Baskets
#include "leetcode.h"
/*
* 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
*/
int totalFruit(int *fruits, int fruitsSize) {
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;
}
}
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 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
}
|