剑指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.lengthn == matrix[i].length1 <= m, n <= 200-105 <= matrix[i][j] <= 1050 <= row1 <= row2 < m0 <= col1 <= col2 < n- 最多调用
104次sumRegion方法
法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,以下类型的多个请求: 计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。 实现 NumMatrix 类: NumMatrix(…...
aosp15 - Activity生命周期切换
本文探查的是,从App冷启动后到MainActivity生命周期切换的系统实现。 调试步骤 在com.android.server.wm.RootWindowContainer#attachApplication 方法下断点,为了attach目标进程在com.android.server.wm.ActivityTaskSupervisor#realStartActivityLock…...
vxe-table 虚拟滚动的动态响应
虚拟滚动主要是在有限范围内渲染想要显示的数据,主要体现在懒加载数据和动态渲染上。如何提高虚拟滚动的操作性呢?请看本章解析 1.什么是虚拟滚动?代码如何实现? VXE-Table提供了一种名为“虚拟滚动”的功能,该功能可…...
quasar dev 命令卡住很久
别以为这是一个瞬间的截图,其实停留在这里很久很久。 折腾挺久,无论npm run dev:proxy还是 quasar dev,都是一样的情况。 最终解决办法: 有语法问题,通过 quasar build 命令暴露出来错误所在的行数。...
黑盒RCE测试 异或测试
前言 了解了漏洞的原理之后就需要知道 他在哪能出现 并且被利用 这个还是很重要的 异或测试 使用异或(XOR)运算进行加密解密的原理_异或加密-CSDN博客 异或测试是在 白盒内执行的 一个例题看一下 输入什么都是会报错 这种情况就需要使用 异或计…...
kotlin中泛型中in和out的区别
概念含义 in关键字(逆变) 在Kotlin泛型中,in关键字主要用于定义逆变(Contravariance)。它表示一个泛型类型参数可以是指定类型或者它的超类型。简单来说,就是对于类型A和B,如果A是B的子类型&…...
c# iis 解决跨域问题
该错误是一个典型的跨域问题,说明从 http://www.fuc.com 发起的请求被目标服务器(https://aip.baidubce.com)拒绝,原因是目标服务器未返回正确的 AccessControlAllowOrigin 响应头。 解决方法 1. 了解问题的本质 CORS(…...
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章讨论了孔子关于孝悌的思想,以及其在中国文化中的重要性和复杂性。文中引用了有子的观点,强调孝弟是为人之本。然而,随着历史的发展,孔子的思想也被误解或被用作维护专制统治的工具。通过司马迁的…...
uniApp上传文件踩坑日记
最近在做移动端app,开始接触uniapp。想着直接用PC端的前后端API去做文件上传,但是uniapp的底层把请求拆成了普通请求和文件上传请求,所以不能用一个axios去做所有请求的处理,拆成uni.request和uni.uploadFile去分别处理两种情况。…...
Webhook 是什么?详解其工作原理
在现代技术中,一切都相互连接,每个应用程序通过许多服务的组合和协调实现无缝工作。这种协调是通过 webhooks 实现的。 Webhooks 是基于 HTTP 的回调函数,其中一个服务使用 API 立即通知另一个服务发生的事件。这就是简单的版本。从技术上讲…...
log4j2漏洞复现(CVE-2021-44228)
靶场环境 步骤一:设置出战规则 步骤二:开启靶场 cd vulhub cd log4j cd CVE-2021-44228 docker-compose up -d docker ps 访问端口 靶机开启 步骤三:外带注入 获得dnslog 靶机访问dnslog 得到dnslog的二级域名信息 步骤四:构造…...
tcpdump抓包分析
使用tcpdump进行抓包分析是一个常见的网络诊断和分析任务。以下是如何使用tcpdump进行抓包和分析的一些基本步骤和技巧: 1. 基本抓包 首先,你需要确定要抓取数据包的网络接口。可以使用ifconfig或ip addr命令查看网络接口。然后,使用以下命…...
LearnOpenGL学习(碰撞检测,粒子)
完整代码见:zaizai77/OpenGLTo2DGame: 基于OpenGL制作2D游戏 物体本身的数据来检测碰撞会很复杂,一半使用重叠在物体上的更简单的外形来检测。 AABB - AABB 碰撞 AABB代表的是轴对齐碰撞箱(Axis-aligned Bounding Box),碰撞箱是指与场景基…...
操作系统(24)提高磁盘I/O速度的途径
前言 操作系统提高磁盘I/O速度的途径多种多样,这些途径旨在减少磁盘访问的延迟和开销,提高数据传输的效率。 一、磁盘高速缓存(Disk Cache) 磁盘高速缓存是一种在内存中为磁盘数据设置的缓冲区,用于存储磁盘中某些盘块…...
C/C++基础知识复习(45)
1) C 中面向对象编程如何实现数据隐藏? 在 C 中,数据隐藏是通过将类的成员变量和方法的访问权限控制起来实现的。通常,数据隐藏是通过使用 访问控制 机制来实现的,C 提供了三种访问控制修饰符: private: 使成员变量和…...
现代C++锁介绍
文章目录 场景描述🐞 初始实现: 非线程安全版本互斥锁: std::mutex使用mutex保护共享资源使用std::lock_guard简化锁的管理 优化读操作: std::shared_mutex多个锁的管理: std::scoped_lock使用std::scoped_lock避免死锁 其他高级锁⏳ 带超时的锁: std::timed_mutex使…...
Squid代理服务器的安装使用
1.简介 Squid代理服务器是一种高效的中间服务器,位于客户端和目标服务器之间,起到了重要的网络中介作用。以下是对Squid代理服务器的详细介绍: 一、功能特点 缓存功能: Squid可以缓存经过它的请求和响应数据。当客户端发起请求时…...
爬虫学习案例8
爬取京东评论信息 采用DrissionPage自动化工具采集,感觉比Selenium工具好,真香。 安装第三方库 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 查询中的各种操作符和限制,并提供详细的例子和说明,帮助你更好地…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
