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

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

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];
};

相关文章:

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

LCR 013. 二维区域和检索 - 矩阵不可变 给定一个二维矩阵 matrix&#xff0c;以下类型的多个请求&#xff1a; 计算其子矩形范围内元素的总和&#xff0c;该子矩阵的左上角为 (row1, col1) &#xff0c;右下角为 (row2, col2) 。 实现 NumMatrix 类&#xff1a; NumMatrix(…...

aosp15 - Activity生命周期切换

本文探查的是&#xff0c;从App冷启动后到MainActivity生命周期切换的系统实现。 调试步骤 在com.android.server.wm.RootWindowContainer#attachApplication 方法下断点&#xff0c;为了attach目标进程在com.android.server.wm.ActivityTaskSupervisor#realStartActivityLock…...

vxe-table 虚拟滚动的动态响应

虚拟滚动主要是在有限范围内渲染想要显示的数据&#xff0c;主要体现在懒加载数据和动态渲染上。如何提高虚拟滚动的操作性呢&#xff1f;请看本章解析 1.什么是虚拟滚动&#xff1f;代码如何实现&#xff1f; VXE-Table提供了一种名为“虚拟滚动”的功能&#xff0c;该功能可…...

quasar dev 命令卡住很久

别以为这是一个瞬间的截图&#xff0c;其实停留在这里很久很久。 折腾挺久&#xff0c;无论npm run dev:proxy还是 quasar dev&#xff0c;都是一样的情况。 最终解决办法&#xff1a; 有语法问题&#xff0c;通过 quasar build 命令暴露出来错误所在的行数。...

黑盒RCE测试 异或测试

前言 了解了漏洞的原理之后就需要知道 他在哪能出现 并且被利用 这个还是很重要的 异或测试 使用异或&#xff08;XOR&#xff09;运算进行加密解密的原理_异或加密-CSDN博客 异或测试是在 白盒内执行的 一个例题看一下 输入什么都是会报错 这种情况就需要使用 异或计…...

kotlin中泛型中in和out的区别

概念含义 in关键字&#xff08;逆变&#xff09; 在Kotlin泛型中&#xff0c;in关键字主要用于定义逆变&#xff08;Contravariance&#xff09;。它表示一个泛型类型参数可以是指定类型或者它的超类型。简单来说&#xff0c;就是对于类型A和B&#xff0c;如果A是B的子类型&…...

c# iis 解决跨域问题

该错误是一个典型的跨域问题&#xff0c;说明从 http://www.fuc.com 发起的请求被目标服务器&#xff08;https://aip.baidubce.com&#xff09;拒绝&#xff0c;原因是目标服务器未返回正确的 AccessControlAllowOrigin 响应头。 解决方法 1. 了解问题的本质 CORS&#xff08…...

MySQL版本对应的mysql-connector-java版本下载地址

MySQL版本mysql-connector-java版本mysql-connector-java下载地址MySQL安装版下载地址MySQL免安装版下载地址5.1.x5.1.xmysql-connector-java 5.1.xMySQL Installer 5.1.xMySQL Community Server 5.1.x5.5.x5.1.x, 5.5.x mysql-connector-java 5.1.x, mysql-connector-java 5.5…...

【读书笔记】《论语别裁》爱与罪

一、内容摘要 《论语别裁》第01章讨论了孔子关于孝悌的思想&#xff0c;以及其在中国文化中的重要性和复杂性。文中引用了有子的观点&#xff0c;强调孝弟是为人之本。然而&#xff0c;随着历史的发展&#xff0c;孔子的思想也被误解或被用作维护专制统治的工具。通过司马迁的…...

uniApp上传文件踩坑日记

最近在做移动端app&#xff0c;开始接触uniapp。想着直接用PC端的前后端API去做文件上传&#xff0c;但是uniapp的底层把请求拆成了普通请求和文件上传请求&#xff0c;所以不能用一个axios去做所有请求的处理&#xff0c;拆成uni.request和uni.uploadFile去分别处理两种情况。…...

Webhook 是什么?详解其工作原理

在现代技术中&#xff0c;一切都相互连接&#xff0c;每个应用程序通过许多服务的组合和协调实现无缝工作。这种协调是通过 webhooks 实现的。 Webhooks 是基于 HTTP 的回调函数&#xff0c;其中一个服务使用 API 立即通知另一个服务发生的事件。这就是简单的版本。从技术上讲…...

log4j2漏洞复现(CVE-2021-44228)

靶场环境 步骤一&#xff1a;设置出战规则 步骤二&#xff1a;开启靶场 cd vulhub cd log4j cd CVE-2021-44228 docker-compose up -d docker ps 访问端口 靶机开启 步骤三&#xff1a;外带注入 获得dnslog 靶机访问dnslog 得到dnslog的二级域名信息 步骤四&#xff1a;构造…...

tcpdump抓包分析

使用tcpdump进行抓包分析是一个常见的网络诊断和分析任务。以下是如何使用tcpdump进行抓包和分析的一些基本步骤和技巧&#xff1a; 1. 基本抓包 首先&#xff0c;你需要确定要抓取数据包的网络接口。可以使用ifconfig或ip addr命令查看网络接口。然后&#xff0c;使用以下命…...

LearnOpenGL学习(碰撞检测,粒子)

完整代码见&#xff1a;zaizai77/OpenGLTo2DGame: 基于OpenGL制作2D游戏 物体本身的数据来检测碰撞会很复杂&#xff0c;一半使用重叠在物体上的更简单的外形来检测。 AABB - AABB 碰撞 AABB代表的是轴对齐碰撞箱(Axis-aligned Bounding Box)&#xff0c;碰撞箱是指与场景基…...

操作系统(24)提高磁盘I/O速度的途径

前言 操作系统提高磁盘I/O速度的途径多种多样&#xff0c;这些途径旨在减少磁盘访问的延迟和开销&#xff0c;提高数据传输的效率。 一、磁盘高速缓存&#xff08;Disk Cache&#xff09; 磁盘高速缓存是一种在内存中为磁盘数据设置的缓冲区&#xff0c;用于存储磁盘中某些盘块…...

C/C++基础知识复习(45)

1) C 中面向对象编程如何实现数据隐藏&#xff1f; 在 C 中&#xff0c;数据隐藏是通过将类的成员变量和方法的访问权限控制起来实现的。通常&#xff0c;数据隐藏是通过使用 访问控制 机制来实现的&#xff0c;C 提供了三种访问控制修饰符&#xff1a; private: 使成员变量和…...

现代C++锁介绍

文章目录 场景描述&#x1f41e; 初始实现: 非线程安全版本互斥锁: std::mutex使用mutex保护共享资源使用std::lock_guard简化锁的管理 优化读操作: std::shared_mutex多个锁的管理: std::scoped_lock使用std::scoped_lock避免死锁 其他高级锁⏳ 带超时的锁: std::timed_mutex使…...

Squid代理服务器的安装使用

1.简介 Squid代理服务器是一种高效的中间服务器&#xff0c;位于客户端和目标服务器之间&#xff0c;起到了重要的网络中介作用。以下是对Squid代理服务器的详细介绍&#xff1a; 一、功能特点 缓存功能&#xff1a; Squid可以缓存经过它的请求和响应数据。当客户端发起请求时…...

爬虫学习案例8

爬取京东评论信息 采用DrissionPage自动化工具采集&#xff0c;感觉比Selenium工具好&#xff0c;真香。 安装第三方库 pip install DrissionPage pip install pandas pip install pyecharts pip install jieba pip install wordcloud1.安装DrissionPage库 DrissionPage安装…...

深入了解 CouchDB 的 Mango 查询:操作符和限制

CouchDB 是一个基于文档的数据库管理系统,支持 HTTP 协议,拥有强大的同步机制和灵活的数据模型。Mango 查询是 CouchDB 中用于数据检索的现代化查询接口,灵感来自 MongoDB 的查询语法。本文将深入探讨 Mango 查询中的各种操作符和限制,并提供详细的例子和说明,帮助你更好地…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...