add 954

fishercoder1534 · fishercoder1534 · commit 4b437003fff1 · 2019-12-10T08:53:31.000-08:00
diff --git a/README.md b/README.md
@@ -83,6 +83,7 @@ _If you like this project, please leave me a star._ &#9733;
 |966|[Vowel Spellchecker](https://leetcode.com/problems/vowel-spellchecker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_966.java) | O(hlogn) | O(n) | |Medium| Hash Table, String
 |965|[Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_965.java) | O(n) | O(h) | |Easy| DFS, recursion|
 |961|[N-Repeated Element in Size 2N Array](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_961.java) | O(n) | O(1) | |Easy|
+|954|[Array of Doubled Pairs](https://leetcode.com/problems/array-of-doubled-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_954.java) | |  | |Medium|
 |953|[Verifying an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_953.java) | O(1) | O(1) | |Easy|
 |951|[Flip Equivalent Binary Trees](https://leetcode.com/problems/flip-equivalent-binary-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_951.java) | O(n) | O(h) | |Medium| Tree, DFS, recursion|
 |950|[Reveal Cards In Increasing Order](https://leetcode.com/problems/reveal-cards-in-increasing-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_950.java) | O(nlogn) | O(n) | |Medium|
diff --git a/src/main/java/com/fishercoder/solutions/_954.java b/src/main/java/com/fishercoder/solutions/_954.java
@@ -0,0 +1,70 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * 954. Array of Doubled Pairs
+ *
+ * Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.
+ *
+ * Example 1:
+ * Input: [3,1,3,6]
+ * Output: false
+ *
+ * Example 2:
+ * Input: [2,1,2,6]
+ * Output: false
+ *
+ * Example 3:
+ * Input: [4,-2,2,-4]
+ * Output: true
+ * Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
+ *
+ * Example 4:
+ * Input: [1,2,4,16,8,4]
+ * Output: false
+ *
+ * Note:
+ * 0 <= A.length <= 30000
+ * A.length is even
+ * -100000 <= A[i] <= 100000
+ * */
+public class _954 {
+    public static class Solution1 {
+        public boolean canReorderDoubled(int[] A) {
+            for (int i = 0; i < A.length; i++) {
+                if (A[i] < 0) {
+                    A[i] = -A[i];
+                }
+            }
+            Arrays.sort(A);
+            Map<Integer, Integer> map = new HashMap<>();
+            for (int num : A) {
+                map.put(num, map.getOrDefault(num, 0) + 1);
+            }
+            for (int num : A) {
+                if (num != 0) {
+                    if (map.get(num) < 0) {
+                        return false;
+                    } else if (map.get(num) == 0) {
+                        continue;
+                    } else {
+                        int count = map.get(num);
+                        map.put(num, map.get(num) - count);
+                        int doubleNum = num * 2;
+                        if (!map.containsKey(doubleNum)) {
+                            return false;
+                        } else {
+                            map.put(doubleNum, map.get(doubleNum) - count);
+                        }
+                    }
+                } else if (map.get(num) % 2 != 0) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_954Test.java b/src/test/java/com/fishercoder/_954Test.java
@@ -0,0 +1,59 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._954;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _954Test {
+    private static _954.Solution1 solution1;
+    private static int[] A;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _954.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        A = new int[]{3, 1, 3, 6};
+        assertEquals(false, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test2() {
+        A = new int[]{2, 1, 2, 6};
+        assertEquals(false, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test3() {
+        A = new int[]{4, -2, 2, -4};
+        assertEquals(true, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test4() {
+        A = new int[]{1, 2, 4, 16, 8, 4};
+        assertEquals(false, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test5() {
+        A = new int[]{1, 2, 4, 8};
+        assertEquals(true, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test6() {
+        A = new int[]{10, 20, 40, 80};
+        assertEquals(true, solution1.canReorderDoubled(A));
+    }
+
+    @Test
+    public void test7() {
+        A = new int[]{0, 0};
+        assertEquals(true, solution1.canReorderDoubled(A));
+    }
+}
