commit 3607f823852dd0645194fc2a764bf69ad2c891c7
parent 85455c7f3ed8fdfbce2a2bd5bbc3a25b20c8125c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 3 Feb 2023 20:43:44 +0100
Dynamic Programming I: Day 14
Diffstat:
3 files changed, 60 insertions(+), 0 deletions(-)
diff --git a/Problems/0304.cpp b/Problems/0304.cpp
@@ -0,0 +1,26 @@
+class NumMatrix {
+ int n, m;
+ vector<vector<int>> dp;
+
+public:
+ NumMatrix(vector<vector<int>> &matrix)
+ : n(matrix.size()), m(matrix[0].size()),
+ dp(vector<vector<int>>(n, vector<int>(m, 0))) {
+ for (int i = 0, sum = 0; i < n; i++) sum = dp[i][0] = matrix[i][0] + sum;
+ for (int i = 0, sum = 0; i < m; i++) sum = dp[0][i] = matrix[0][i] + sum;
+ for (int i = 1; i < n; i++) {
+ for (int j = 1; j < m; j++) {
+ dp[i][j] =
+ matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
+ }
+ }
+ }
+
+ int sumRegion(int x1, int y1, int x2, int y2) {
+ int res = dp[x2][y2];
+ if (x1 > 0) res -= dp[x1 - 1][y2];
+ if (y1 > 0) res -= dp[x2][y1 - 1];
+ if (x1 > 0 && y1 > 0) res += dp[x1 - 1][y1 - 1];
+ return res;
+ }
+};
diff --git a/Problems/1314.cpp b/Problems/1314.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ inline int clamp(const int a, const int x, const int y) {
+ return min(max(a, x), y);
+ }
+
+public:
+ vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k) {
+ int n = mat.size(), m = mat[0].size();
+ vector<vector<int>> dp(n, vector<int>(m, 0)), res(n, vector<int>(m, 0));
+
+ for (int i = 0, sum = 0; i < n; i++) sum = dp[i][0] = mat[i][0] + sum;
+ for (int i = 0, sum = 0; i < m; i++) sum = dp[0][i] = mat[0][i] + sum;
+ for (int i = 1; i < n; i++) {
+ for (int j = 1; j < m; j++) {
+ dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
+ }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ int x1 = clamp(i - k, 0, n - 1), y1 = clamp(j - k, 0, m - 1);
+ int x2 = clamp(i + k, 0, n - 1), y2 = clamp(j + k, 0, m - 1);
+ res[i][j] = dp[x2][y2];
+ if (x1 > 0) res[i][j] -= dp[x1 - 1][y2];
+ if (y1 > 0) res[i][j] -= dp[x2][y1 - 1];
+ if (x1 > 0 && y1 > 0) res[i][j] += dp[x1 - 1][y1 - 1];
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -158,6 +158,7 @@ for solving problems.
| 0295 | Hard | [Find Median from Data Stream](Problems/0295.cpp) |
| 0299 | Medium | [Bulls and Cows](Problems/0299.cpp) |
| 0300 | Medium | [Longest Increasing Subsequence](Problems/0300.cpp) |
+| 0304 | Medium | [Range Sum Query 2D - Immutable](Problems/0304.cpp) |
| 0309 | Medium | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp) |
| 0310 | Medium | [Minimum Height Trees](Problems/0310.cpp) |
| 0326 | Easy | [Power of Three](Problems/0326.cpp) |
@@ -303,6 +304,7 @@ for solving problems.
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
| 1311 | Medium | [Get Watched Videos by Your Friends](Problems/1311.cpp) |
+| 1314 | Medium | [Matrix Block Sum](Problems/1314.cpp) |
| 1315 | Medium | [Sum of Nodes with Even-Valued Grandparent](Problems/1315.cpp) |
| 1319 | Medium | [Number of Operations to Make Network Connected](Problems/1319.cpp) |
| 1323 | Easy | [Maximum 69 Number](Problems/1323.cpp) |
