add solutions for 1277

fishercoder1534 · fishercoder1534 · commit b1f99990a9cf · 2019-12-09T07:21:06.000-08:00
diff --git a/README.md b/README.md
@@ -10,6 +10,7 @@ _If you like this project, please leave me a star._ &#9733;
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
 |1282|[Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1282.java) |  |  | |Medium||
 |1281|[Subtract the Product and Sum of Digits of an Integer](https://leetcode.com/problems/subtract-the-product-and-sum-of-digits-of-an-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1281.java) |  |  | |Easy||
+|1277|[Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1277.java) |  |  | |Medium||
 |1266|[Minimum Time Visiting All Points](https://leetcode.com/problems/minimum-time-visiting-all-points/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1266.java) |  |  | |Easy||
 |1260|[Shift 2D Grid](https://leetcode.com/problems/shift-2d-grid/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1260.java) |  |  | [:tv:](https://www.youtube.com/watch?v=9hBcARSiU0s)|Easy||
 |1252|[Cells with Odd Values in a Matrix](https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1252.java) | O(m*n + k) | O(m*n) | |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1277.java b/src/main/java/com/fishercoder/solutions/_1277.java
@@ -39,8 +39,60 @@
  * */
 public class _1277 {
     public static class Solution1 {
+        /**
+         * In-place solution.
+         *
+         * credit: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441306/Python-DP-solution
+         * */
         public int countSquares(int[][] matrix) {
+            int m = matrix.length;
+            int n = matrix[0].length;
             int count = 0;
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    if (matrix[i][j] > 0 && i > 0 && j > 0) {
+                        matrix[i][j] = Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1])) + 1;
+                    }
+                    count += matrix[i][j];
+                }
+            }
+            return count;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * Use m*n extra space solution.
+         *
+         * credit: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441312/Java-Simple-DP-solution
+         */
+        public int countSquares(int[][] matrix) {
+            int m = matrix.length;
+            int n = matrix[0].length;
+            int[][] dp = new int[m][n];
+            for (int i = 0; i < m; i++) {
+                if (matrix[i][0] == 1) {
+                    dp[i][0] = 1;
+                }
+            }
+            for (int j = 0; j < n; j++) {
+                if (matrix[0][j] == 1) {
+                    dp[0][j] = 1;
+                }
+            }
+            for (int i = 1; i < m; i++) {
+                for (int j = 1; j < n; j++) {
+                    if (matrix[i][j] == 1) {
+                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
+                    }
+                }
+            }
+            int count = 0;
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    count += dp[i][j];
+                }
+            }
             return count;
         }
     }
diff --git a/src/test/java/com/fishercoder/_1277Test.java b/src/test/java/com/fishercoder/_1277Test.java
@@ -0,0 +1,40 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1277;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _1277Test {
+    private static _1277.Solution1 solution1;
+    private static _1277.Solution2 solution2;
+    private static int[][] matrix;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1277.Solution1();
+        solution2 = new _1277.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        matrix = new int[][]{
+                {0, 1, 1, 1},
+                {1, 1, 1, 1},
+                {0, 1, 1, 1}
+        };
+        assertEquals(15, solution1.countSquares(matrix));
+    }
+
+    @Test
+    public void test2() {
+        matrix = new int[][]{
+                {0, 1, 1, 1},
+                {1, 1, 1, 1},
+                {0, 1, 1, 1}
+        };
+        assertEquals(15, solution2.countSquares(matrix));
+    }
+
+}
