add 904

fishercoder1534 · fishercoder1534 · commit f79d6e462a91 · 2020-11-17T11:40:59.000-08:00
diff --git a/README.md b/README.md
@@ -317,6 +317,7 @@ _If you like this project, please leave me a star._ &#9733;
 |912|[Sort an Array](https://leetcode.com/problems/sort-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_912.java) |  |Easy|
 |908|[Smallest Range I](https://leetcode.com/problems/smallest-range-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_908.java) |  |Easy|
 |901|[Online Stock Span](https://leetcode.com/problems/online-stock-span/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_901.java) |  |Medium| Stack
+|904|[Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_904.java) |  |Medium| Two Pointers
 |900|[RLE Iterator](https://leetcode.com/problems/rle-iterator/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_900.java) |  |Medium|
 |897|[Increasing Order Search Tree](https://leetcode.com/problems/increasing-order-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_897.java) | |Easy| DFS, recursion
 |896|[Monotonic Array](https://leetcode.com/problems/monotonic-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_896.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_904.java b/src/main/java/com/fishercoder/solutions/_904.java
@@ -0,0 +1,32 @@
+package com.fishercoder.solutions;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class _904 {
+    public static class Solution1 {
+        public int totalFruit(int[] tree) {
+            int maxFruits = 0;
+            Set<Integer> set = new HashSet<>();
+            int startIndex = 0;
+            for (int i = 0; i < tree.length; i++) {
+                if (set.size() < 2 || set.contains(tree[i])) {
+                    set.add(tree[i]);
+                    maxFruits = Math.max(maxFruits, i - startIndex + 1);
+                } else {
+                    int lastOne = tree[i - 1];
+                    for (int j = i - 2; j >= 0; j--) {
+                        if (tree[j] != lastOne) {
+                            startIndex = j + 1;
+                            set.remove(tree[j]);
+                            break;
+                        }
+                    }
+                    set.add(tree[i]);
+                    maxFruits = Math.max(maxFruits, i - startIndex + 1);
+                }
+            }
+            return maxFruits;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_904Test.java b/src/test/java/com/fishercoder/_904Test.java
@@ -0,0 +1,47 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._904;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _904Test {
+    private static _904.Solution1 solution1;
+    private static int[] tree;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _904.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        tree = new int[]{1, 2, 1};
+        assertEquals(3, solution1.totalFruit(tree));
+    }
+
+    @Test
+    public void test2() {
+        tree = new int[]{0, 1, 2, 2};
+        assertEquals(3, solution1.totalFruit(tree));
+    }
+
+    @Test
+    public void test3() {
+        tree = new int[]{1, 2, 3, 2, 2};
+        assertEquals(4, solution1.totalFruit(tree));
+    }
+
+    @Test
+    public void test4() {
+        tree = new int[]{3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};
+        assertEquals(5, solution1.totalFruit(tree));
+    }
+
+    @Test
+    public void test5() {
+        tree = new int[]{0, 1, 6, 6, 4, 4, 6};
+        assertEquals(5, solution1.totalFruit(tree));
+    }
+}
