[LintCode] Submatrix Sum 子矩阵之和
2024-10-16 14:18:42
Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.
Have you met this question in a real interview?
Yes
Example
Given matrix
[
[1 ,5 ,7],
[3 ,7 ,-8],
[4 ,-8 ,9],
]
return [(1,1), (2,2)]
Challenge
O(n3) time.
这道题跟LeetCode上的那道Max Sum of Rectangle No Larger Than K很类似。
解法一：
class Solution {
public:
/**
* @param matrix an integer matrix
* @return the coordinate of the left-up and right-down number
*/
vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[].empty()) return {};
vector<vector<int>> sums = matrix;
int m = matrix.size(), n = matrix[].size();
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
int t = sums[i][j];
if (i > ) t += sums[i - ][j];
if (j > ) t += sums[i][j - ];
if (i > && j > ) t -= sums[i - ][j - ];
sums[i][j] = t;
for (int p = ; p <= i; ++p) {
for (int q = ; q <= j; ++q) {
int d = sums[i][j];
if (p > ) d -= sums[p - ][j];
if (q > ) d -= sums[i][q - ];
if (p > && q > ) d += sums[p - ][q - ];
if (d == ) return {{p, q}, {i, j}};
}
}
}
}
printVec(sums);
return {};
}
};
解法二：
class Solution {
public:
/**
* @param matrix an integer matrix
* @return the coordinate of the left-up and right-down number
*/
vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[].empty()) return {};
int m = matrix.size(), n = matrix[].size();
for (int i = ; i < n; ++i) {
vector<int> sums(m, );
for (int j = i; j < n; ++j) {
for (int k = ; k < m; ++k) {
sums[k] += matrix[k][j];
}
int curSum = ;
unordered_map<int, int> map{{,-}};
for (int k = ; k < m; ++k) {
curSum += sums[k];
if (map.count(curSum)) return {{map[curSum] + , i}, {k, j}};
map[curSum] = k;
}
}
}
return {};
}
};
参考资料：
http://www.jiuzhang.com/solutions/submatrix-sum/
最新文章
- 采用cocos2d－x lua 制作数字滚动效果样例
- bzoj3316: JC loves Mkk
- ubuntu 常用命令集合版（二）【大侠勿喷，菜鸟欢迎】(转)
- C# C/S WPF 远程操作服务器上面的文件
- HttpClient和HttpURLConnection整合汇总对比
- 实例--post请求，完成一个抽奖程序概率的测试
- Linux 内核模块设计
- Redux1
- apache 2.4.9 配置其他客户端访问 required all granted
- Apache+php+mysql win7 64位安装的几个注意事项
- XWalkView+html 开发Android应用
- C/C++取出变量的每一位的值（第一次知道还有QBitArray）
- luogu P4074 [WC2013]糖果公园
- ubuntu12.04安装Docker
- Android 播放内部mp3音乐
- vue使用日期时间插件layDate
- Guava HashMultiset（MultiSet）
- Linux ip命令详解
- 用 Delphi 7 实现基于 FFMS2 的视频转 GIF 工具 [原创]
- poj 1218 THE DRUNK JAILER