leetcode 304. Range Sum Query 2D - Immutable(递推)
2024-09-02 03:08:57
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
] sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
题解:
二维的情况和一维的思路类似,就是求一个递推式然后把和预处理出来,然后O(1)查询。
一维的递推式是:s[i]=s[i-1]+a[i];
二维的由画图可知:s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
n=matrix.size();
m=n>?matrix[].size():;
s=vector<vector<int>>(n+,vector<int>(m+,));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
s[i][j]=matrix[i-][j-]+s[i-][j]+s[i][j-]-s[i-][j-];
}
}
} int sumRegion(int row1, int col1, int row2, int col2) {
return s[row2+][col2+]-s[row2+][col1]-s[row1][col2+]+s[row1][col1];
}
private:
int n,m;
vector<vector<int> >s;
}; // Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);
最新文章
- 理解RESTful架构
- 【新手出发】从搭虚拟机开始,一步一步在CentOS上跑起来.Net Core程序
- advstringgrid笔记
- ie浏览器,背景色兼容解决方法
- Spring MVC实例(增删改查)
- IOS上传图片
- 关于freemarker标签+Spring3.0 V层学习
- The 2013 ACM-ICPC Asia Changsha Regional Contest - A
- VIP网络水军账号
- 转。webapp开发小tips
- 关于 WP上应用调试时报错“指定的通信资源(端口)”已由另一个应用程序使用 问题
- 使用python进行加密解密AES算法
- 5分钟教你玩转 sklearn 机器学习(上)
- 客户端热更新框架之UI热更框架设计(上)
- Keepalived 的使用
- BeanFactory和FactoryBean的区别
- Spring Boot + Spring Cloud 实现权限管理系统 后端篇(二十):服务熔断(Hystrix、Turbine)
- java_二进制的前导的零
- CocosCreator内置函数实现物体拖动
- android 开发小工具收集