add 1314

fishercoder1534 · fishercoder1534 · commit 290d0dccc0a2 · 2020-02-09T15:34:27.000-08:00
diff --git a/README.md b/README.md
@@ -26,6 +26,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1323|[Maximum 69 Number](https://leetcode.com/problems/maximum-69-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1323.java) | |Easy|Math|
 |1317|[Convert Integer to the Sum of Two No-Zero Integers](https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1317.java) | |Easy||
 |1315|[Sum of Nodes with Even-Valued Grandparent](https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1315.java) | |Medium|Tree, DFS|
+|1314|[Matrix Block Sum](https://leetcode.com/problems/matrix-block-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1314.java) | |Medium|Dynamic Programming|
 |1313|[Decompress Run-Length Encoded List](https://leetcode.com/problems/decompress-run-length-encoded-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1313.java) | |Easy|Array|
 |1305|[All Elements in Two Binary Search Trees](https://leetcode.com/problems/all-elements-in-two-binary-search-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1305.java) | |Medium||
 |1304|[Find N Unique Integers Sum up to Zero](https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1304.java) | |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1314.java b/src/main/java/com/fishercoder/solutions/_1314.java
@@ -0,0 +1,59 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 1314. Matrix Block Sum
+ *
+ * Given a m * n matrix mat and an integer K,
+ * return a matrix answer where each answer[i][j] is the sum of all elements
+ * mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.
+ *
+ * Example 1:
+ * Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
+ * Output: [[12,21,16],[27,45,33],[24,39,28]]
+ *
+ * Example 2:
+ * Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
+ * Output: [[45,45,45],[45,45,45],[45,45,45]]
+ *
+ * Constraints:
+ * m == mat.length
+ * n == mat[i].length
+ * 1 <= m, n, K <= 100
+ * 1 <= mat[i][j] <= 100
+ * */
+public class _1314 {
+    public static class Solution1 {
+        public int[][] matrixBlockSum(int[][] mat, int K) {
+            int m = mat.length;
+            int n = mat[0].length;
+            int[][] answer = new int[m][n];
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    List<Integer> iRange = findRange(i, K, m);
+                    List<Integer> jRange = findRange(j, K, n);
+                    int sum = 0;
+                    for (int ii = 0; ii < iRange.size(); ii++) {
+                        for (int jj = 0; jj < jRange.size(); jj++) {
+                            sum += mat[iRange.get(ii)][jRange.get(jj)];
+                        }
+                    }
+                    answer[i][j] = sum;
+                }
+            }
+            return answer;
+        }
+
+        private List<Integer> findRange(int iOrJ, int k, int upper) {
+            int min = (iOrJ - k) < 0 ? 0 : (iOrJ - k);
+            int max = (iOrJ + k) >= upper ? (upper - 1) : (iOrJ + k);
+            List<Integer> range = new ArrayList<>();
+            for (int i = min; i <= max; i++) {
+                range.add(i);
+            }
+            return range;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1314Test.java b/src/test/java/com/fishercoder/_1314Test.java
@@ -0,0 +1,48 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1314;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1314Test {
+    private static _1314.Solution1 solution1;
+    private static int[][] mat;
+    private static int[][] expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1314.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        mat = new int[][]{
+                {1, 2, 3},
+                {4, 5, 6},
+                {7, 8, 9}
+        };
+        expected = new int[][]{
+                {12, 21, 16},
+                {27, 45, 33},
+                {24, 39, 28}
+        };
+        assertEquals(expected, solution1.matrixBlockSum(mat, 1));
+    }
+
+    @Test
+    public void test2() {
+        mat = new int[][]{
+                {1, 2, 3},
+                {4, 5, 6},
+                {7, 8, 9}
+        };
+        expected = new int[][]{
+                {45, 45, 45},
+                {45, 45, 45},
+                {45, 45, 45}
+        };
+        assertEquals(expected, solution1.matrixBlockSum(mat, 2));
+    }
+}
