C语言重构【304】二维区域和检索 - 矩阵不可变
2021/5/10 18:56:32
本文主要是介绍C语言重构【304】二维区域和检索 - 矩阵不可变,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 所有题目源代码:[Git地址](https://github.com/ch98road/leetcode)
- 题目
- 方案:
- 复杂度计算
所有题目源代码:Git地址
题目
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。 上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。
示例: 给定 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
方案:
- 大致思想就是先存好每个元素到0.0元素的和,然后要算的时候简单计算一下就行了,不用每个都遍历过去
class NumMatrix { public: vector<vector<int>> mymatrix; NumMatrix(vector<vector<int>> &matrix) { //意思是计算出某一点到(0,0)的和然后-上-左+左上 int row = matrix.size(); int col = matrix[0].size(); vector<vector<int>> tmp(row, vector<int>(col, 0)); mymatrix = tmp; mymatrix[0][0] = matrix[0][0]; for (int i = 1; i < row; i++) { //init 第0列 mymatrix[i][0] = mymatrix[i - 1][0] + matrix[i][0]; // cout<<mymatrix[i][0]<<endl; } for (int i = 1; i < col; i++) { //init 第0行 mymatrix[0][i] = mymatrix[0][i - 1] + matrix[0][i]; // cout<<mymatrix[0][i]<<endl; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { mymatrix[i][j] = mymatrix[i - 1][j] + mymatrix[i][j - 1] - mymatrix[i - 1][j - 1] + matrix[i][j]; // cout<<mymatrix[i][j]<<endl; } } } int sumRegion(int row1, int col1, int row2, int col2) { //=(r2,c2)-(r1-1,c2)-(r2,c1-1)+(r1-1,c1-1) int res = mymatrix[row2][col2]; if (row1 > 0) res -= mymatrix[row1 - 1][col2]; if (col1 > 0) res -= mymatrix[row2][col1 - 1]; if (row1 > 0 && col1 > 0) res += mymatrix[row1 - 1][col1 - 1]; return res; } }; /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */
复杂度计算
- 时间复杂度:O(1):但是建造和矩阵的时候是n^2
- 空间复杂度:O(n^2)
这篇关于C语言重构【304】二维区域和检索 - 矩阵不可变的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain