fd

dingjikerbo · dingjikerbo · commit 3d5a4286f43c · 2018-11-20T11:40:18.000+08:00
diff --git a/README.md b/README.md
@@ -384,4 +384,5 @@
 |669|[Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/)|[Java](leetcode/solution/src/TrimABinarySearchTree.java)|100||
 |681|[Next Closest Time](https://leetcode.com/problems/next-closest-time/)|[Java](leetcode/solution/src/NextClosestTime.java)|80|这题多做几遍|
 |684|[Redundant Connection](https://leetcode.com/problems/redundant-connection/)| [Java](leetcode/solution/src/RedundantConnection.java)|||
-|771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)|[Java](leetcode/solution/src/JewelsAndStones.java)|100||
+|771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)|[Java](leetcode/solution/src/JewelsAndStones.java)|100||
+|904|[Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)|[Java](leetcode/solution/src/FruitIntoBaskets.java)|90||
diff --git a/leetcode/solution/src/FruitIntoBaskets.java b/leetcode/solution/src/FruitIntoBaskets.java
@@ -0,0 +1,31 @@
+import java.util.HashMap;
+
+/**
+ * 这题和sliding window较类似
+ * 意思是给定一个数组，找出其中的一个最长的连续子数组，只能有两个不同的数
+ */
+public class FruitIntoBaskets {
+
+
+    public static int totalFruit(int[] tree) {
+        int max = 0;
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int i = 0, j = 0; j < tree.length; j++) {
+            int value = tree[j];
+
+            map.put(value, map.getOrDefault(value, 0) + 1);
+
+            for ( ; map.size() > 2; i++) {
+                int val = tree[i], cnt = map.get(val);
+                if (cnt == 1) {
+                    map.remove(val);
+                } else {
+                    map.put(val, cnt - 1);
+                }
+            }
+            max = Math.max(max, j - i + 1);
+        }
+
+        return max;
+    }
+}
diff --git a/leetcode/solution/src/MinimumWindowSubstring.java b/leetcode/solution/src/MinimumWindowSubstring.java
@@ -1,6 +1,6 @@
 public class MinimumWindowSubstring {
 
-    // 耗时8ms，时间复杂度O(n)
+    // 耗时6ms，时间复杂度O(n)
     public String minWindow(String s, String t) {
         int[] tc = new int[256], sc = new int[256];
         for (char c : t.toCharArray()) {
diff --git a/leetcode/solution/src/WordBreak.java b/leetcode/solution/src/WordBreak.java
@@ -5,7 +5,8 @@
  */
 public class WordBreak {
 
-    // 耗时8ms
+    // 耗时3ms
+    // 典型的DP问题
     public boolean wordBreak(String s, List<String> wordDict) {
         int n = s.length();
 
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -2,37 +2,32 @@
 
 public class Main {
 
-    // 1 5 1
-    public void nextPermutation(int[] nums) {
-        int i = nums.length - 1, j;
-        for (i = nums.length - 1; i > 0; i--) {
-            if (nums[i - 1] < nums[i]) {
-                break;
-            }
-        }
-        if (i > 0) {
-            for (j = i; j < nums.length; j++) {
-                if (nums[j] <= nums[i - 1]) {
-                    break;
+    public static int totalFruit(int[] tree) {
+        int max = 0;
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int i = 0, j = 0; j < tree.length; j++) {
+            int value = tree[j];
+
+            map.put(value, map.getOrDefault(value, 0) + 1);
+
+            for ( ; map.size() > 2; i++) {
+                int val = tree[i], cnt = map.get(val);
+                if (cnt == 1) {
+                    map.remove(val);
+                } else {
+                    map.put(val, cnt - 1);
                 }
             }
-            swap(nums, i - 1, j - 1);
+            max = Math.max(max, j - i + 1);
         }
-        revert(nums, i, nums.length - 1);
-    }
-
-    private void revert(int[] nums, int start, int end) {
-        for ( ; start < end; start++, end--) {
-            swap(nums, start, end);
-        }
-    }
 
-    private void swap(int[] nums, int i, int j) {
-        int t = nums[i];
-        nums[i] = nums[j];
-        nums[j] = t;
+        return max;
     }
 
     public static void main(String[] args) {
+        int n = totalFruit(new int[]{
+                1, 2, 1
+        });
+        System.out.println(n);
     }
 }
