add 861

fishercoder1534 · fishercoder1534 · commit 8c536fbff51f · 2021-04-01T17:14:18.000-07:00
diff --git a/README.md b/README.md
@@ -428,6 +428,7 @@ _If you like this project, please leave me a star._ &#9733;
 |870|[Advantage Shuffle](https://leetcode.com/problems/advantage-shuffle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_870.java) |  |Medium|Array, Greedy
 |868|[Binary Gap](https://leetcode.com/problems/binary-gap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_868.java) |  |Easy|
 |867|[Transpose Matrix](https://leetcode.com/problems/transpose-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_867.java) |  |Easy|
+|861|[Score After Flipping Matrix](https://leetcode.com/problems/score-after-flipping-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_861.java) | |Medium| Greedy
 |860|[Lemonade Change](https://leetcode.com/problems/lemonade-change/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_860.java) | |Easy|
 |859|[Buddy Strings](https://leetcode.com/problems/buddy-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_859.java) |  |Easy|
 |856|[Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_856.java) |  |Medium| Stack, String
diff --git a/src/main/java/com/fishercoder/solutions/_861.java b/src/main/java/com/fishercoder/solutions/_861.java
@@ -0,0 +1,55 @@
+package com.fishercoder.solutions;
+
+public class _861 {
+    public static class Solution1 {
+        /**
+         * We can simply apply greedy methodology here.
+         * 1. we check if the left most digits are ones or not, if it's a zero,
+         * then we'll just flip this entire row, reason being the left most digit carries the biggest weight when interpreting this binary row/number;
+         * 2. after step #1, we'll check column wise starting from the second column,
+         * we'll count the number of ones in each column, if the number of ones in each column is less than or equal to half of the column length,
+         * then flipping this column would make a bigger number
+         */
+        public int matrixScore(int[][] A) {
+            int m = A.length;
+            int n = A[0].length;
+            for (int i = 0; i < m; i++) {
+                if (A[i][0] == 0) {
+                    for (int j = 0; j < n; j++) {
+                        if (A[i][j] == 0) {
+                            A[i][j] = 1;
+                        } else {
+                            A[i][j] = 0;
+                        }
+                    }
+                }
+            }
+            for (int j = 1; j < n; j++) {
+                int ones = 0;
+                for (int i = 0; i < m; i++) {
+                    if (A[i][j] == 1) {
+                        ones++;
+                    }
+                }
+                if (ones <= m / 2) {
+                    for (int i = 0; i < m; i++) {
+                        if (A[i][j] == 1) {
+                            A[i][j] = 0;
+                        } else {
+                            A[i][j] = 1;
+                        }
+                    }
+                }
+            }
+            int result = 0;
+            for (int i = 0; i < m; i++) {
+                StringBuilder sb = new StringBuilder();
+                for (int j = 0; j < n; j++) {
+                    sb.append(A[i][j]);
+                }
+                result += Integer.parseInt(sb.toString(), 2);
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_861Test.java b/src/test/java/com/fishercoder/_861Test.java
@@ -0,0 +1,23 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._861;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _861Test {
+    private static _861.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _861.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(39, solution1.matrixScore(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,0,1,1],[1,0,1,0],[1,1,0,0]")));
+    }
+
+}
