Skip to content

Commit 1ee7391

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1314. Matrix Block Sum
1 parent 214c212 commit 1ee7391

File tree

8 files changed

+366
-2
lines changed

8 files changed

+366
-2
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -187,6 +187,7 @@
187187
- [杨辉三角 II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README.md)
188188
- [下降路径最小和](./solution/0900-0999/0931.Minimum%20Falling%20Path%20Sum/README.md)
189189
- [三角形最小路径和](./solution/0100-0199/0120.Triangle/README.md)
190+
- [矩阵区域和](./solution/1300-1399/1314.Matrix%20Block%20Sum/README.md)
190191
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
191192
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
192193
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -181,6 +181,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
181181
- [Pascal's Triangle II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README_EN.md)
182182
- [Minimum Falling Path Sum](./solution/0900-0999/0931.Minimum%20Falling%20Path%20Sum/README_EN.md)
183183
- [Triangle](./solution/0100-0199/0120.Triangle/README_EN.md)
184+
- [Matrix Block Sum](./solution/1300-1399/1314.Matrix%20Block%20Sum/README_EN.md)
184185
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
185186
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
186187
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)

‎solution/1300-1399/1314.Matrix Block Sum/README.md

Lines changed: 125 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,22 +43,146 @@
4343

4444
<!-- 这里可写通用的实现逻辑 -->
4545

46+
动态规划-二维前缀和。
47+
4648
<!-- tabs:start -->
4749

4850
### **Python3**
4951

5052
<!-- 这里可写当前语言的特殊实现逻辑 -->
5153

5254
```python
53-
55+
class Solution:
56+
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
57+
m, n = len(mat), len(mat[0])
58+
pre = [[0] * (n + 1) for _ in range(m + 1)]
59+
for i in range(1, m + 1):
60+
for j in range(1, n + 1):
61+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + mat[i - 1][j - 1]
62+
63+
def get(i, j):
64+
i = max(min(m, i), 0)
65+
j = max(min(n, j), 0)
66+
return pre[i][j]
67+
68+
ans = [[0] * n for _ in range(m)]
69+
for i in range(m):
70+
for j in range(n):
71+
ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) - get(i - k, j + k + 1) + get(i - k, j - k)
72+
return ans
5473
```
5574

5675
### **Java**
5776

5877
<!-- 这里可写当前语言的特殊实现逻辑 -->
5978

6079
```java
80+
class Solution {
81+
private int[][] pre;
82+
private int m;
83+
private int n;
84+
public int[][] matrixBlockSum(int[][] mat, int k) {
85+
int m = mat.length, n = mat[0].length;
86+
int[][] pre = new int[m + 1][n + 1];
87+
for (int i = 1; i < m + 1; ++i) {
88+
for (int j = 1; j < n + 1; ++j) {
89+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + - pre[i - 1][j - 1] + mat[i - 1][j - 1];
90+
}
91+
}
92+
this.pre = pre;
93+
this.m = m;
94+
this.n = n;
95+
int[][] ans = new int[m][n];
96+
for (int i = 0; i < m; ++i) {
97+
for (int j = 0; j < n; ++j) {
98+
ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) - get(i - k, j + k + 1) + get(i - k, j - k);
99+
}
100+
}
101+
return ans;
102+
}
103+
104+
private int get(int i, int j) {
105+
i = Math.max(Math.min(m, i), 0);
106+
j = Math.max(Math.min(n, j), 0);
107+
return pre[i][j];
108+
}
109+
}
110+
```
111+
112+
### **C++**
113+
114+
```cpp
115+
class Solution {
116+
public:
117+
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
118+
int m = mat.size(), n = mat[0].size();
119+
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
120+
for (int i = 1; i < m + 1; ++i) {
121+
for (int j = 1; j < n + 1; ++j) {
122+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + - pre[i - 1][j - 1] + mat[i - 1][j - 1];
123+
}
124+
}
125+
vector<vector<int>> ans(m, vector<int>(n));
126+
for (int i = 0; i < m; ++i) {
127+
for (int j = 0; j < n; ++j) {
128+
ans[i][j] = get(i + k + 1, j + k + 1, m, n, pre) - get(i + k + 1, j - k, m, n, pre) - get(i - k, j + k + 1, m, n, pre) + get(i - k, j - k, m, n, pre);
129+
}
130+
}
131+
return ans;
132+
}
133+
134+
int get(int i, int j, int m, int n, vector<vector<int>>& pre) {
135+
i = max(min(m, i), 0);
136+
j = max(min(n, j), 0);
137+
return pre[i][j];
138+
}
139+
};
140+
```
61141

142+
### **Go**
143+
144+
```go
145+
func matrixBlockSum(mat [][]int, k int) [][]int {
146+
m, n := len(mat), len(mat[0])
147+
pre := make([][]int, m+1)
148+
for i := 0; i < m+1; i++ {
149+
pre[i] = make([]int, n+1)
150+
}
151+
for i := 1; i < m+1; i++ {
152+
for j := 1; j < n+1; j++ {
153+
pre[i][j] = pre[i-1][j] + pre[i][j-1] + -pre[i-1][j-1] + mat[i-1][j-1]
154+
}
155+
}
156+
157+
get := func(i, j int) int {
158+
i = max(min(m, i), 0)
159+
j = max(min(n, j), 0)
160+
return pre[i][j]
161+
}
162+
163+
ans := make([][]int, m)
164+
for i := 0; i < m; i++ {
165+
ans[i] = make([]int, n)
166+
for j := 0; j < n; j++ {
167+
ans[i][j] = get(i+k+1, j+k+1) - get(i+k+1, j-k) - get(i-k, j+k+1) + get(i-k, j-k)
168+
}
169+
}
170+
return ans
171+
}
172+
173+
func max(a, b int) int {
174+
if a > b {
175+
return a
176+
}
177+
return b
178+
}
179+
180+
func min(a, b int) int {
181+
if a < b {
182+
return a
183+
}
184+
return b
185+
}
62186
```
63187

64188
### **...**

‎solution/1300-1399/1314.Matrix Block Sum/README_EN.md

Lines changed: 125 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,18 +40,142 @@
4040

4141
## Solutions
4242

43+
Dynamic programming - 2D preSum.
44+
4345
<!-- tabs:start -->
4446

4547
### **Python3**
4648

4749
```python
48-
50+
class Solution:
51+
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
52+
m, n = len(mat), len(mat[0])
53+
pre = [[0] * (n + 1) for _ in range(m + 1)]
54+
for i in range(1, m + 1):
55+
for j in range(1, n + 1):
56+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + mat[i - 1][j - 1]
57+
58+
def get(i, j):
59+
i = max(min(m, i), 0)
60+
j = max(min(n, j), 0)
61+
return pre[i][j]
62+
63+
ans = [[0] * n for _ in range(m)]
64+
for i in range(m):
65+
for j in range(n):
66+
ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) - get(i - k, j + k + 1) + get(i - k, j - k)
67+
return ans
4968
```
5069

5170
### **Java**
5271

5372
```java
73+
class Solution {
74+
private int[][] pre;
75+
private int m;
76+
private int n;
77+
public int[][] matrixBlockSum(int[][] mat, int k) {
78+
int m = mat.length, n = mat[0].length;
79+
int[][] pre = new int[m + 1][n + 1];
80+
for (int i = 1; i < m + 1; ++i) {
81+
for (int j = 1; j < n + 1; ++j) {
82+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + - pre[i - 1][j - 1] + mat[i - 1][j - 1];
83+
}
84+
}
85+
this.pre = pre;
86+
this.m = m;
87+
this.n = n;
88+
int[][] ans = new int[m][n];
89+
for (int i = 0; i < m; ++i) {
90+
for (int j = 0; j < n; ++j) {
91+
ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) - get(i - k, j + k + 1) + get(i - k, j - k);
92+
}
93+
}
94+
return ans;
95+
}
96+
97+
private int get(int i, int j) {
98+
i = Math.max(Math.min(m, i), 0);
99+
j = Math.max(Math.min(n, j), 0);
100+
return pre[i][j];
101+
}
102+
}
103+
```
104+
105+
### **C++**
106+
107+
```cpp
108+
class Solution {
109+
public:
110+
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
111+
int m = mat.size(), n = mat[0].size();
112+
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
113+
for (int i = 1; i < m + 1; ++i) {
114+
for (int j = 1; j < n + 1; ++j) {
115+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + - pre[i - 1][j - 1] + mat[i - 1][j - 1];
116+
}
117+
}
118+
vector<vector<int>> ans(m, vector<int>(n));
119+
for (int i = 0; i < m; ++i) {
120+
for (int j = 0; j < n; ++j) {
121+
ans[i][j] = get(i + k + 1, j + k + 1, m, n, pre) - get(i + k + 1, j - k, m, n, pre) - get(i - k, j + k + 1, m, n, pre) + get(i - k, j - k, m, n, pre);
122+
}
123+
}
124+
return ans;
125+
}
126+
127+
int get(int i, int j, int m, int n, vector<vector<int>>& pre) {
128+
i = max(min(m, i), 0);
129+
j = max(min(n, j), 0);
130+
return pre[i][j];
131+
}
132+
};
133+
```
54134

135+
### **Go**
136+
137+
```go
138+
func matrixBlockSum(mat [][]int, k int) [][]int {
139+
m, n := len(mat), len(mat[0])
140+
pre := make([][]int, m+1)
141+
for i := 0; i < m+1; i++ {
142+
pre[i] = make([]int, n+1)
143+
}
144+
for i := 1; i < m+1; i++ {
145+
for j := 1; j < n+1; j++ {
146+
pre[i][j] = pre[i-1][j] + pre[i][j-1] + -pre[i-1][j-1] + mat[i-1][j-1]
147+
}
148+
}
149+
150+
get := func(i, j int) int {
151+
i = max(min(m, i), 0)
152+
j = max(min(n, j), 0)
153+
return pre[i][j]
154+
}
155+
156+
ans := make([][]int, m)
157+
for i := 0; i < m; i++ {
158+
ans[i] = make([]int, n)
159+
for j := 0; j < n; j++ {
160+
ans[i][j] = get(i+k+1, j+k+1) - get(i+k+1, j-k) - get(i-k, j+k+1) + get(i-k, j-k)
161+
}
162+
}
163+
return ans
164+
}
165+
166+
func max(a, b int) int {
167+
if a > b {
168+
return a
169+
}
170+
return b
171+
}
172+
173+
func min(a, b int) int {
174+
if a < b {
175+
return a
176+
}
177+
return b
178+
}
55179
```
56180

57181
### **...**

‎solution/1300-1399/1314.Matrix Block Sum/Solution.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class Solution {
2+
public:
3+
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
4+
int m = mat.size(), n = mat[0].size();
5+
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
6+
for (int i = 1; i < m + 1; ++i) {
7+
for (int j = 1; j < n + 1; ++j) {
8+
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + - pre[i - 1][j - 1] + mat[i - 1][j - 1];
9+
}
10+
}
11+
vector<vector<int>> ans(m, vector<int>(n));
12+
for (int i = 0; i < m; ++i) {
13+
for (int j = 0; j < n; ++j) {
14+
ans[i][j] = get(i + k + 1, j + k + 1, m, n, pre) - get(i + k + 1, j - k, m, n, pre) - get(i - k, j + k + 1, m, n, pre) + get(i - k, j - k, m, n, pre);
15+
}
16+
}
17+
return ans;
18+
}
19+
20+
int get(int i, int j, int m, int n, vector<vector<int>>& pre) {
21+
i = max(min(m, i), 0);
22+
j = max(min(n, j), 0);
23+
return pre[i][j];
24+
}
25+
};

‎solution/1300-1399/1314.Matrix Block Sum/Solution.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
func matrixBlockSum(mat [][]int, k int) [][]int {
2+
m, n := len(mat), len(mat[0])
3+
pre := make([][]int, m+1)
4+
for i := 0; i < m+1; i++ {
5+
pre[i] = make([]int, n+1)
6+
}
7+
for i := 1; i < m+1; i++ {
8+
for j := 1; j < n+1; j++ {
9+
pre[i][j] = pre[i-1][j] + pre[i][j-1] + -pre[i-1][j-1] + mat[i-1][j-1]
10+
}
11+
}
12+
13+
get := func(i, j int) int {
14+
i = max(min(m, i), 0)
15+
j = max(min(n, j), 0)
16+
return pre[i][j]
17+
}
18+
19+
ans := make([][]int, m)
20+
for i := 0; i < m; i++ {
21+
ans[i] = make([]int, n)
22+
for j := 0; j < n; j++ {
23+
ans[i][j] = get(i+k+1, j+k+1) - get(i+k+1, j-k) - get(i-k, j+k+1) + get(i-k, j-k)
24+
}
25+
}
26+
return ans
27+
}
28+
29+
func max(a, b int) int {
30+
if a > b {
31+
return a
32+
}
33+
return b
34+
}
35+
36+
func min(a, b int) int {
37+
if a < b {
38+
return a
39+
}
40+
return b
41+
}

0 commit comments

Comments
 (0)