数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找矩阵中元素和等于特定值的子矩阵数量
假设我们得到一个包含整数值的矩阵。我们需要找到矩阵中的子矩阵，其中子矩阵的元素之和等于给定的目标和值。我们返回子矩阵的数量。
因此，如果输入如下所示：
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 |
并且目标值为5，则输出将为3。
元素和等于6的子矩阵数量为2。
为了解决这个问题，我们将遵循以下步骤：
- n := mat的大小
- m := (如果n等于0，则为0，否则为mat[0]的大小)
- 如果m > n，则：
- 定义一个维度为m x n的二维数组transpose（转置）
- 初始化i := 0，当i < n时，更新（i加1），执行：
- 初始化j := 0，当j < m时，更新（j加1），执行：
- transpose[j, i] := mat[i, j]
- 初始化j := 0，当j < m时，更新（j加1），执行：
- 返回solve(transpose, sumTarget)
- ans := 0
- 初始化p := 0，当p < m时，更新（p加1），执行：
- 定义一个数组arr
- 初始化q := p，当q < m时，更新（q加1），执行：
- 初始化i := 0，当i < n时，更新（i加1），执行：
- arr[i] := arr[i] + mat[i, q]
- 定义一个包含键值对{0, 1}的map pcnt
- pref := 0
- 初始化i := 0，当i < n时，更新（i加1），执行：
- pref := pref + arr[i]
- tmp := (pref - sumTarget)在pcnt中的位置
- 如果tmp不等于pcnt的末尾位置，则：
- (pcnt[pref]加1)
- 初始化i := 0，当i < n时，更新（i加1），执行：
- 返回ans
示例
让我们看看以下实现，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>>& mat, int sumTarget) {
int n = mat.size();
int m = n == 0 ? 0 : mat[0].size();
if (m > n) {
vector<vector<int>> transpose(m, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
transpose[j][i] = mat[i][j];
}
}
return solve(transpose, sumTarget);
}
int ans = 0;
for (int p = 0; p < m; p++) {
vector<int> arr(n);
for (int q = p; q < m; q++) {
for (int i = 0; i < n; i++) {
arr[i] += mat[i][q];
}
unordered_map<int, int> pcnt = {{0, 1}};
int pref = 0;
for (int i = 0; i < n; i++) {
pref += arr[i];
auto tmp = pcnt.find(pref - sumTarget);
if (tmp != end(pcnt)) ans += tmp->second;
pcnt[pref]++;
}
}
}
return ans;
}
int main() {
vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};
cout<< solve(mat, 5) <<endl;
return 0;
}输入
{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}, 5输出
3
更新于: 2021年10月16日
229 次查看
广告