怎样做免费网站推广,网站空间多大合适,企业解决方案 msdn技术资源库,优化网站公司价格是多少钱文章目录1. 题目2. 解题1. 题目
给你一个 2D 矩阵 matrix#xff0c;请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形中所有元素的和。
上述粉色矩形框内的#xff0c;该矩形由左上角 (row1, col1) (2, 1) 和右下角 (row2, col2) (4, 3) 确定。其中请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形中所有元素的和。
上述粉色矩形框内的该矩形由左上角 (row1, col1) (2, 1) 和右下角 (row2, col2) (4, 3) 确定。其中所包括的元素总和 sum 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
update(3, 2, 2)
sumRegion(2, 1, 4, 3) - 10注意:
矩阵 matrix 的值只能通过 update 函数来进行修改
你可以默认 update 函数和 sumRegion 函数的调用次数是均匀分布的
你可以默认 row1 ≤ row2col1 ≤ col2 来源力扣LeetCode 链接https://leetcode-cn.com/problems/range-sum-query-2d-mutable 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 304. 二维区域和检索 - 矩阵不可变DP二维树状数组可以更高效树状数组默写不来用行的前缀和做时间复杂度O(n)
class NumMatrix {vectorvectorint mat;vectorvectorint rowpresum;
public:NumMatrix(vectorvectorint matrix) {mat matrix;rowpresum matrix;for(int i 0, j; i matrix.size(); i){for(j 1; j matrix[0].size(); j)rowpresum[i][j] rowpresum[i][j-1] matrix[i][j];}}void update(int row, int col, int val) {mat[row][col] val;rowpresum[row][col] (col 0 ? rowpresum[row][col-1] : 0) val;for(int j col1; j mat[0].size(); j)rowpresum[row][j] rowpresum[row][j-1] mat[row][j];}int sumRegion(int row1, int col1, int row2, int col2) {int sum 0;for(int i row1; i row2; i){sum rowpresum[i][col2] - (col10 ? 0 : rowpresum[i][col1-1]);}return sum;}
};28 ms 12.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
