当前位置: 首页 > news >正文

重庆企业做网站多少钱个人免费域名注册网站

重庆企业做网站多少钱,个人免费域名注册网站,wordpress newsletter 插件,做标书有什么好的网站吗LCR 013. 二维区域和检索 - 矩阵不可变 给定一个二维矩阵 matrix,以下类型的多个请求: 计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。 实现 NumMatrix 类: NumMatrix(…

LCR 013. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 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 (蓝色矩形框的元素总和)

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -105 <= matrix[i][j] <= 105
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • 最多调用 104sumRegion 方法

法1:暴力

**分析:**两层for循环遍历

时间复杂度 O ( n 2 ) O(n^2) O(n2)

空间复杂度 O ( 1 ) O(1) O(1)

 var NumMatrix = function(matrix) {this.matrix = matrix;
};NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {matrix = this.matrix;let result = 0;for (let r = row1; r <= row2; r++) {for (let c = col1; c <= col2; c++) {result += matrix[r][c];}}return result
};const 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]
];
var obj = new NumMatrix(matrix);
console.log(obj.sumRegion(2, 1, 4, 3)); // 输出 8
console.log(obj.sumRegion(1, 1, 2, 2)); // 输出 11
console.log(obj.sumRegion(1, 2, 2, 4)); // 输出 12

leetcode上通过不了

法2: 前缀和(Prefix Sum)

分析:

定义一个prefixSum ,比原本的matrix多一行多一列。

prefixSum 中,prefixSum[i][j] 表示从 (0,0)(i-1, j-1) 的区域和。

比如要计算prefixSum[3][3],也就是matrix[3][3]左上角的和。

在这里插入图片描述

28怎么来,要求matrix[3][3]左上角的和,也就是要求

28 = matrix[i - 1][j - 1]      //这个就是matrix[2][2]=1
+ this.prefixSum[i - 1][j]     //prefixSum[2][3]=matrix[2][3]左上角的和=16
+ this.prefixSum[i][j - 1] 	   //prefixSum[3][2]=matrix[3][2]左上角的和=22
- this.prefixSum[i - 1][j - 1];//prefixSum[2][2]=matrix[2][2]左上角的和=11
// 1+16+22-11=28

在这里插入图片描述

可以看出prefixSum[3][2]prefixSum[2][3]有交集prefixSum[2][2],多以最后要减去一个prefixSum[2][2],再加上maxtrix[2][2](图中绿色填充)的。

int sumRegion(int row1, int col1, int row2, int col2)

再看比如说计算sumRegion(1,1,2,2)

this.prefixSum[row2 + 1][col2 + 1] -  // prefixSum[3][3]
this.prefixSum[row1][col2 + 1] -      // prefixSum[1][3]
this.prefixSum[row2 + 1][col1] +      // prefixSum[3][1] 
this.prefixSum[row1][col1];           // prefixSum[1][1]

在这里插入图片描述

时间复杂度 O ( n ) O(n) O(n)

空间复杂度 O ( 1 ) O(1) O(1)

 var NumMatrix = function(matrix) {// 初始化 NumMatrix 类的实例属性 matrixthis.matrix = matrix;const m = matrix.length;const n = matrix[0].length;// 创建一个 m+1 x n+1 的前缀和数组 (多加一行一列是为了方便计算)this.prefixSum = Array(m + 1).fill().map(() => Array(n + 1).fill(0));// 填充前缀和数组for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {this.prefixSum[i][j] = matrix[i - 1][j - 1] + this.prefixSum[i - 1][j] + this.prefixSum[i][j - 1] - this.prefixSum[i - 1][j - 1];}}    
};NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {// 使用前缀和公式计算区域和return this.prefixSum[row2 + 1][col2 + 1] - this.prefixSum[row1][col2 + 1] - this.prefixSum[row2 + 1][col1] + this.prefixSum[row1][col1];
};
http://www.hengruixuexiao.com/news/13902.html

相关文章:

  • 做旅行网站多少钱营销是什么意思
  • 网站建设太难了seo优化工具有哪些
  • 哈尔滨免费模板建站网络营销的现状
  • 东阿做网站外贸网站推广方法之一
  • 怎样学做网站百度浏览器下载
  • 做电商网站用什么技术百度网址大全官网旧版
  • seo网站优化是什么福州seo公司排名
  • 网络平台推广运营培训说到很多seo人员都转行了
  • 一个网站不兼容ie怎么做怎么学做电商然后自己创业
  • 中国供应商教程seo推广排名网站
  • 网上花店网站建设规划书青岛网站推广公司排名
  • 新沂网站开发口碑营销的特征
  • 做虚假彩票网站判几年seo搜索排名优化是什么意思
  • 做企业网站需要什么文件网站优化排名的方法
  • 网站推广方案中十大嵌入式培训机构
  • 网站域名后缀cc做品牌推广应该怎么做
  • 学习做网站多久手机维修培训班学校
  • python免费下载安装长春网站优化方案
  • 建设银行网站不能登录不了免费的api接口网站
  • 成都专业网站建设百度投流
  • 上海装修公司排名有哪些五种关键词优化工具
  • 网站seo是什么意线上引流线下推广方案
  • win本地网站建设万网官网首页
  • 浙江高端建设网站网络软文推广平台
  • 电子商务网站建设考纲企业网站建设的流程
  • 汕头住房和城乡建设厅网站网络推广和网站推广平台
  • 北京网站排名seo简阳seo排名优化课程
  • 上海建设工程标准与造价信息网站世界排名前十位
  • 做策划需要进的网站抄一则新闻四年级
  • 网站logo修改购买友情链接