[L-0] add 575

fishercoder1534 · fishercoder1534 · commit ff1c6d4bf346 · 2017-05-06T19:13:21.000-07:00
diff --git a/README.md b/README.md
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|575|[Distribute Candies](https://leetcode.com/problems/distribute-candies/)|[Solution](../master/src/main/java/com/stevesun/solutions/_575.java) | O(nlogn) |O(1) | Easy | Array
 |567|[Permutation in String](https://leetcode.com/problems/permutation-in-string/)|[Solution](../master/src/main/java/com/stevesun/solutions/_567.java) | O(max(m,n)) |O(1) | Medium | Sliding Windows, Two Pointers
 |566|[Reshape the Matrix](https://leetcode.com/problems/reshape-the-matrix/)|[Solution](../master/src/main/java/com/stevesun/solutions/_566.java) | O(m*n) |O(1) | Easy | 
 |563|[Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/)|[Solution](../master/src/main/java/com/stevesun/solutions/_563.java) | O(n) |O(n) | Easy | Tree Recursion
diff --git a/src/main/java/com/stevesun/solutions/_575.java b/src/main/java/com/stevesun/solutions/_575.java
@@ -0,0 +1,42 @@
+package com.stevesun.solutions;
+
+import java.util.Arrays;
+
+/**
+ * 575. Distribute Candies
+ *
+ Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
+
+ Example 1:
+ Input: candies = [1,1,2,2,3,3]
+ Output: 3
+ Explanation:
+ There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
+ Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
+ The sister has three different kinds of candies.
+ Example 2:
+ Input: candies = [1,1,2,3]
+ Output: 2
+ Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
+ The sister has two different kinds of candies, the brother has only one kind of candies.
+ Note:
+
+ The length of the given array is in range [2, 10,000], and will be even.
+ The number in given array is in range [-100,000, 100,000].
+ */
+public class _575 {
+    public int distributeCandies(int[] candies) {
+        Arrays.sort(candies);
+        int sisCount = 0;
+        for (int i = 0; i < candies.length; i++) {
+            int val = candies[i];
+            sisCount++;
+            if (sisCount >= candies.length/2) return candies.length/2;
+            while (i < candies.length && candies[i] == val) {
+                i++;
+            }
+            i--;
+        }
+        return sisCount;
+    }
+}
diff --git a/src/test/java/com/stevesun/_575Test.java b/src/test/java/com/stevesun/_575Test.java
@@ -0,0 +1,46 @@
+package com.stevesun;
+
+import com.stevesun.solutions._575;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 5/6/17.
+ */
+public class _575Test {
+    private static _575 test;
+    private static int expected;
+    private static int actual;
+    private static int[] candies;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _575();
+    }
+
+    @Test
+    public void test1(){
+        candies = new int[]{1,1,2,3};
+        expected = 2;
+        actual = test.distributeCandies(candies);
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test2(){
+        candies = new int[]{1,1,2,2,3,3};
+        expected = 3;
+        actual = test.distributeCandies(candies);
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test3(){
+        candies = new int[]{1000,1,1,1};
+        expected = 2;
+        actual = test.distributeCandies(candies);
+        assertEquals(expected, actual);
+    }
+}
