当前位置:网站首页>leetcode-304:二维区域和检索 - 矩阵不可变
leetcode-304:二维区域和检索 - 矩阵不可变
2022-07-07 08:17:00 【菊头蝙蝠】
题目
给定一个二维矩阵 matrix,以下类型的多个请求:
- 计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。
实现 NumMatrix 类:
- NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
- int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
示例 1:
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
解题
方法一:前缀和
preSums[i][j]
表示左上角为(0,0),右下角索引为(i,j)的矩阵里的所有元素和
1、首先通过下述递推关系式计算出preSums[i][j]
S ( O , D ) = S ( O , C ) + S ( O , B ) − S ( O , A ) + D S(O,D)=S(O,C)+S(O,B)−S(O,A)+D S(O,D)=S(O,C)+S(O,B)−S(O,A)+D
2、根据已经计算出的preSums,可以得出想要计算的矩阵中所有元素之和
S ( A , D ) = S ( O , D ) − S ( O , E ) − S ( O , F ) + S ( O , G ) S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G) S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)
class NumMatrix {
public:
vector<vector<int>> preSums;
NumMatrix(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
preSums.resize(m+1,vector<int>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
preSums[i+1][j+1]=preSums[i+1][j]+preSums[i][j+1]-preSums[i][j]+matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return preSums[row2+1][col2+1]-preSums[row1][col2+1]-preSums[row2+1][col1]+preSums[row1][col1];
}
};
边栏推荐
- [email protected]能帮助我们快速拿到日志对象
- ArcGIS operation: converting DWG data to SHP data
- Review of the losers in the postgraduate entrance examination
- Socket通信原理和实践
- [牛客网刷题 Day5] JZ77 按之字形顺序打印二叉树
- Smart city construction based on GIS 3D visualization technology
- php \n 换行无法输出
- Pdf document signature Guide
- Guide de signature du Code Appx
- BigDecimal数值比较
猜你喜欢
P2788 数学1(math1)- 加减算式
Yarn的基础介绍以及job的提交流程
串口通讯继电器-modbus通信上位机调试软件工具项目开发案例
Use the fetch statement to obtain the repetition of the last row of cursor data
【acwing】789. Range of numbers (binary basis)
The request object parses the request body and request header parameters
Vs code specifies the extension installation location
1321:【例6.3】删数问题(Noip1994)
Inno setup packaging and signing Guide
The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
随机推荐
STM32中AHB总线_APB2总线_APB1总线这些是什么
Yarn的基础介绍以及job的提交流程
一文讲解单片机、ARM、MUC、DSP、FPGA、嵌入式错综复杂的关系
求方程ax^2+bx+c=0的根(C语言)
Wallys/IPQ6010 (IPQ6018 FAMILY) EMBEDDED BOARD WITH ON-BOARD WIFI DUAL BAND DUAL CONCURRENT
ORM -- grouping query, aggregation query, query set queryset object properties
[higherhrnet] higherhrnet detailed heat map regression code of higherhrnet
1321:【例6.3】删数问题(Noip1994)
2022.7.4DAY596
嵌入式工程师如何提高工作效率
php \n 换行无法输出
Slurm资源管理与作业调度系统安装配置
SQLyog数据库怎么取消自动保存更改
Postman interface test IV
C logging method
Google colab loads Google drive (Google drive is used in Google colab)
Use the fetch statement to obtain the repetition of the last row of cursor data
Deconvolution popular detailed analysis and nn Convtranspose2d important parameter interpretation
JMeter about setting thread group and time
[牛客网刷题 Day5] JZ77 按之字形顺序打印二叉树