Added tasks 1071, 1072, 1073.

javadev · web-flow · commit 19a29acc8f60 · 2022-02-27T15:40:55.000+02:00
diff --git a/src/main/java/g1001_1100/s1071_greatest_common_divisor_of_strings/Solution.java b/src/main/java/g1001_1100/s1071_greatest_common_divisor_of_strings/Solution.java
@@ -0,0 +1,23 @@
+package g1001_1100.s1071_greatest_common_divisor_of_strings;
+
+// #Easy #String #Math #2022_02_27_Time_1_ms_(82.09%)_Space_42.6_MB_(33.55%)
+
+public class Solution {
+    public String gcdOfStrings(String str1, String str2) {
+        if (str1 == null || str2 == null) {
+            return "";
+        }
+        if (str1.equals(str2)) {
+            return str1;
+        }
+        int m = str1.length();
+        int n = str2.length();
+        if (m > n && str1.substring(0, n).equals(str2)) {
+            return gcdOfStrings(str1.substring(n), str2);
+        }
+        if (n > m && str2.substring(0, m).equals(str1)) {
+            return gcdOfStrings(str2.substring(m), str1);
+        }
+        return "";
+    }
+}
diff --git a/src/main/java/g1001_1100/s1071_greatest_common_divisor_of_strings/readme.md b/src/main/java/g1001_1100/s1071_greatest_common_divisor_of_strings/readme.md
@@ -0,0 +1,30 @@
+1071\. Greatest Common Divisor of Strings
+
+Easy
+
+For two strings `s` and `t`, we say "`t` divides `s`" if and only if `s = t + ... + t` (i.e., `t` is concatenated with itself one or more times).
+
+Given two strings `str1` and `str2`, return _the largest string_ `x` _such that_ `x` _divides both_ `str1` _and_ `str2`.
+
+**Example 1:**
+
+**Input:** str1 = "ABCABC", str2 = "ABC"
+
+**Output:** "ABC"
+
+**Example 2:**
+
+**Input:** str1 = "ABABAB", str2 = "ABAB"
+
+**Output:** "AB"
+
+**Example 3:**
+
+**Input:** str1 = "LEET", str2 = "CODE"
+
+**Output:** ""
+
+**Constraints:**
+
+*   `1 <= str1.length, str2.length <= 1000`
+*   `str1` and `str2` consist of English uppercase letters.
diff --git a/src/main/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/Solution.java b/src/main/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/Solution.java
@@ -0,0 +1,43 @@
+package g1001_1100.s1072_flip_columns_for_maximum_number_of_equal_rows;
+
+// #Medium #Array #Hash_Table #Matrix #2022_02_27_Time_26_ms_(95.71%)_Space_51.4_MB_(92.86%)
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class Solution {
+    public int maxEqualRowsAfterFlips(int[][] matrix) {
+        /*
+        Idea:
+        For a given row[i], 0<=i<m, row[j], 0<=j<m and j!=i, if either of them can have
+        all values equal after some number of flips, then
+         row[i]==row[j]  <1> or
+         row[i]^row[j] == 111...111 <2> (xor result is a row full of '1')
+
+        Go further, in case<2> row[j] can turn to row[i] by flipping each column of row[j]
+        IF assume row[i][0] is 0, then question is convert into:
+         1> flipping each column of each row if row[i][0] is not '0',
+         2> count the frequency of each row.
+         The biggest number of frequencies is the answer.
+         */
+
+        // O(M*N), int M = matrix.length, N = matrix[0].length;
+        int answer = 0;
+        Map<String, Integer> frequency = new HashMap<>();
+        for (int[] row : matrix) {
+            StringBuilder rowStr = new StringBuilder();
+            for (int c : row) {
+                if (row[0] == 1) {
+                    rowStr.append(c == 1 ? 0 : 1);
+                } else {
+                    rowStr.append(c);
+                }
+            }
+            String key = rowStr.toString();
+            int value = frequency.getOrDefault(key, 0) + 1;
+            frequency.put(key, value);
+            answer = Math.max(answer, value);
+        }
+        return answer;
+    }
+}
diff --git a/src/main/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/readme.md b/src/main/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/readme.md
@@ -0,0 +1,40 @@
+1072\. Flip Columns For Maximum Number of Equal Rows
+
+Medium
+
+You are given an `m x n` binary matrix `matrix`.
+
+You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from `0` to `1` or vice versa).
+
+Return _the maximum number of rows that have all values equal after some number of flips_.
+
+**Example 1:**
+
+**Input:** matrix = [[0,1],[1,1]]
+
+**Output:** 1
+
+**Explanation:** After flipping no values, 1 row has all values equal.
+
+**Example 2:**
+
+**Input:** matrix = [[0,1],[1,0]]
+
+**Output:** 2
+
+**Explanation:** After flipping values in the first column, both rows have equal values.
+
+**Example 3:**
+
+**Input:** matrix = [[0,0,0],[0,0,1],[1,1,0]]
+
+**Output:** 2
+
+**Explanation:** After flipping values in the first two columns, the last two rows have equal values.
+
+**Constraints:**
+
+*   `m == matrix.length`
+*   `n == matrix[i].length`
+*   `1 <= m, n <= 300`
+*   `matrix[i][j]` is either `0` or `1`.
diff --git a/src/main/java/g1001_1100/s1073_adding_two_negabinary_numbers/Solution.java b/src/main/java/g1001_1100/s1073_adding_two_negabinary_numbers/Solution.java
@@ -0,0 +1,48 @@
+package g1001_1100.s1073_adding_two_negabinary_numbers;
+
+// #Medium #Array #Math #2022_02_27_Time_1_ms_(100.00%)_Space_42.4_MB_(57.83%)
+
+public class Solution {
+    public int[] addNegabinary(int[] arr1, int[] arr2) {
+        int len1 = arr1.length;
+        int len2 = arr2.length;
+        int[] reverseArr1 = new int[len1];
+        for (int i = len1 - 1; i >= 0; i--) {
+            reverseArr1[len1 - i - 1] = arr1[i];
+        }
+        int[] reverseArr2 = new int[len2];
+        for (int i = len2 - 1; i >= 0; i--) {
+            reverseArr2[len2 - i - 1] = arr2[i];
+        }
+        int[] sumArray = new int[Math.max(len1, len2) + 2];
+        System.arraycopy(reverseArr1, 0, sumArray, 0, len1);
+        for (int i = 0; i < sumArray.length; i++) {
+            if (i < len2) {
+                sumArray[i] += reverseArr2[i];
+            }
+            if (sumArray[i] > 1) {
+                sumArray[i] -= 2;
+                sumArray[i + 1]--;
+            } else if (sumArray[i] == -1) {
+                sumArray[i] = 1;
+                sumArray[i + 1]++;
+            }
+        }
+        int resultLen = sumArray.length;
+        for (int i = sumArray.length - 1; i >= 0; i--) {
+            if (sumArray[i] == 0) {
+                resultLen--;
+            } else {
+                break;
+            }
+        }
+        if (resultLen == 0) {
+            return new int[] {0};
+        }
+        int[] result = new int[resultLen];
+        for (int i = resultLen - 1; i >= 0; i--) {
+            result[resultLen - i - 1] = sumArray[i];
+        }
+        return result;
+    }
+}
diff --git a/src/main/java/g1001_1100/s1073_adding_two_negabinary_numbers/readme.md b/src/main/java/g1001_1100/s1073_adding_two_negabinary_numbers/readme.md
@@ -0,0 +1,35 @@
+1073\. Adding Two Negabinary Numbers
+
+Medium
+
+Given two numbers `arr1` and `arr2` in base **\-2**, return the result of adding them together.
+
+Each number is given in _array format_: as an array of 0s and 1s, from most significant bit to least significant bit. For example, `arr = [1,1,0,1]` represents the number `(-2)^3 + (-2)^2 + (-2)^0 = -3`. A number `arr` in _array, format_ is also guaranteed to have no leading zeros: either `arr == [0]` or `arr[0] == 1`.
+
+Return the result of adding `arr1` and `arr2` in the same format: as an array of 0s and 1s with no leading zeros.
+
+**Example 1:**
+
+**Input:** arr1 = [1,1,1,1,1], arr2 = [1,0,1]
+
+**Output:** [1,0,0,0,0]
+
+**Explanation:** arr1 represents 11, arr2 represents 5, the output represents 16.
+
+**Example 2:**
+
+**Input:** arr1 = [0], arr2 = [0]
+
+**Output:** [0]
+
+**Example 3:**
+
+**Input:** arr1 = [0], arr2 = [1]
+
+**Output:** [1]
+
+**Constraints:**
+
+*   `1 <= arr1.length, arr2.length <= 1000`
+*   `arr1[i]` and `arr2[i]` are `0` or `1`
+*   `arr1` and `arr2` have no leading zeros
diff --git a/src/test/java/g1001_1100/s1071_greatest_common_divisor_of_strings/SolutionTest.java b/src/test/java/g1001_1100/s1071_greatest_common_divisor_of_strings/SolutionTest.java
@@ -0,0 +1,23 @@
+package g1001_1100.s1071_greatest_common_divisor_of_strings;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void gcdOfStrings() {
+        assertThat(new Solution().gcdOfStrings("ABCABC", "ABC"), equalTo("ABC"));
+    }
+
+    @Test
+    void gcdOfStrings2() {
+        assertThat(new Solution().gcdOfStrings("ABABAB", "ABAB"), equalTo("AB"));
+    }
+
+    @Test
+    void gcdOfStrings3() {
+        assertThat(new Solution().gcdOfStrings("LEET", "CODE"), equalTo(""));
+    }
+}
diff --git a/src/test/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/SolutionTest.java b/src/test/java/g1001_1100/s1072_flip_columns_for_maximum_number_of_equal_rows/SolutionTest.java
@@ -0,0 +1,26 @@
+package g1001_1100.s1072_flip_columns_for_maximum_number_of_equal_rows;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void maxEqualRowsAfterFlips() {
+        assertThat(new Solution().maxEqualRowsAfterFlips(new int[][] {{0, 1}, {1, 1}}), equalTo(1));
+    }
+
+    @Test
+    void maxEqualRowsAfterFlips2() {
+        assertThat(new Solution().maxEqualRowsAfterFlips(new int[][] {{0, 1}, {1, 0}}), equalTo(2));
+    }
+
+    @Test
+    void maxEqualRowsAfterFlips3() {
+        assertThat(
+                new Solution()
+                        .maxEqualRowsAfterFlips(new int[][] {{0, 0, 0}, {0, 0, 1}, {1, 1, 0}}),
+                equalTo(2));
+    }
+}
diff --git a/src/test/java/g1001_1100/s1073_adding_two_negabinary_numbers/SolutionTest.java b/src/test/java/g1001_1100/s1073_adding_two_negabinary_numbers/SolutionTest.java
@@ -0,0 +1,27 @@
+package g1001_1100.s1073_adding_two_negabinary_numbers;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void addNegabinary() {
+        assertThat(
+                new Solution().addNegabinary(new int[] {1, 1, 1, 1, 1}, new int[] {1, 0, 1}),
+                equalTo(new int[] {1, 0, 0, 0, 0}));
+    }
+
+    @Test
+    void addNegabinary2() {
+        assertThat(
+                new Solution().addNegabinary(new int[] {0}, new int[] {0}), equalTo(new int[] {0}));
+    }
+
+    @Test
+    void addNegabinary3() {
+        assertThat(
+                new Solution().addNegabinary(new int[] {0}, new int[] {1}), equalTo(new int[] {1}));
+    }
+}
