leetcode 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

最多调用 104 次 sumRegion 方法

解题思路:(前缀和思路)

对于一个二维矩阵,可能由于输入不同的坐标而反复求不同子矩阵的数字之和,所以需要尽可能快的实现子矩阵的数字求和

用前缀和的方式可快速求子矩阵的数字和

为了代码实现上方便,特意在最左边一列,最上边一列空出来

先根据原矩阵,求出前缀和矩阵,然后通过观察得知公式
sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1]
class NumMatrix {int[][] sums;public NumMatrix(int[][] matrix) {int m = matrix.length;if (m > 0) {int n = matrix[0].length;sums = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];}}}}public int sumRegion(int row1, int col1, int row2, int col2) {return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];}
}


 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/243254.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Quartus II使用小技巧

工程结构&#xff1a; 在建立完某项设计的文件后&#xff0c;依次在其里面新建四个文件夹&#xff0c;分别为&#xff1a;rtl、qprj、msim、doc。 rtl文件夹用于存放设计的源文件。 doc文件夹用于存放设计的一些文档性的资料。 qprj文件夹用于存放quaruts 工程以及quartus生…

Git入门详细教程

一、Git概述&#x1f387; Git官网 Git是一个开源的分布式版本控制系统&#xff0c;用于跟踪文件的变化和协作开发。它允许多个开发者在同一项目中共同工作&#xff0c;并能够有效地管理代码的版本和历史记录。Git可以帮助开发团队更好地协作&#xff0c;追踪代码变更&#xf…

记一次多平台免杀PHP木马的制作过程

注意&#xff1a;本文转载自本作者稀土掘金博客 博客地址&#xff1a; 御坂19008号 的个人主页 - 动态 - 掘金 文章目录 前言声明绕过情况使用方法运行环境绕过点介绍技术原理讲解变量传值覆盖模块代码执行阻断模块InazumaPuzzle程序锁定器PerlinNoise危险函数生成与执行类构造…

Android 基础技术——addView 流程

笔者希望做一个系列&#xff0c;整理 Android 基础技术&#xff0c;本章是关于 addView 在了解 addView 流程之前&#xff0c;先回答下以下几个问题&#xff1a; PhoneWindow是什么时候创建的&#xff1f; DectorView 是什么&#xff1f; DectorView 是什么时候创建的&#xf…

Oracle行转列函数,列转行函数

Oracle行转列函数&#xff0c;列转行函数 Oracle 可以通过PIVOT,UNPIVOT,分解一行里面的值为多个列,及来合并多个列为一行。 PIVOT PIVOT是用于将行数据转换为列数据的查询操作(类似数据透视表)。通过使用PIVOT&#xff0c;您可以按照特定的列值将数据进行汇总&#xff0c;并将…

Flowable 生成流程图

/*** 生成流程图** param processId 任务ID*/ RequestMapping("/diagram/{processId}") public void genProcessDiagram(HttpServletResponse response,PathVariable("processId") String processId) {InputStream inputStream flowTaskService.diagram(p…

SpringCloud整合Zookeeper代替Eureka案例

文章目录 本期代码下载地址zookeeper简介zookeeper下载安装新建服务提供者测试 新建消费者测试 本期代码下载地址 地址:https://github.com/13thm/study_springcloud/tree/main/days4 zookeeper简介 zookeeper是一个分布式协调工具&#xff0c;可以实现注册中心功能 关闭Lin…

WampServer

开发笔记 推荐链接php无法保存SESSION问题部署SSL时候产生的问题 推荐链接 链接目录 php无法保存SESSION问题 php.ini文件和phpForApache.ini 文件 里面都有 对路径的控制&#xff0c;相关路径问题可能也需要进行修改&#xff0c;打开文件搜索wamp64或wamp 就可以看到了&…

线程池--JAVA

虽然线程是轻量级进程&#xff0c;但是如果当创建和销毁的的频率非常之高&#xff0c;那么它也就会消耗很多的资源。 而线程池就是用来优化线程频繁创建和销毁的场景&#xff0c;减少线程创建、销毁的频率。 ExecutorService JAVA标准库为我们实现了线程池&#xff0c;Execu…

windows11上安装虚拟机VMware

1、安装虚拟机&#xff08;待补充&#xff09; 第二步&#xff1a;安装VMware tools 实现windows文件上传到虚拟机中 1、安装好虚拟机后&#xff0c;查看虚拟机ip用Xshell连接虚拟机&#xff0c;并安装VMware tools(只有安装了VMware tools才能实现虚拟机和本机的文件共享。在…

无人机航迹规划(四):七种元启发算法(DBO、LO、SWO、COA、LSO、KOA、GRO)求解无人机路径规划(提供MATLAB代码)

一、七种算法&#xff08;DBO、LO、SWO、COA、LSO、KOA、GRO&#xff09;简介 1、蜣螂优化算法DBO 蜣螂优化算法&#xff08;Dung beetle optimizer&#xff0c;DBO&#xff09;由Jiankai Xue和Bo Shen于2022年提出&#xff0c;该算法主要受蜣螂的滚球、跳舞、觅食、偷窃和繁殖…

Python编辑开发---pycharm pro 2023 中文

PyCharm Pro 2023是一款功能强大的Python集成开发环境&#xff08;IDE&#xff09;&#xff0c;旨在提高Python开发人员的生产力。它提供了智能代码编辑、实时代码分析和调试工具&#xff0c;支持版本控制和数据库工具&#xff0c;以及可扩展的插件系统。PyCharm Pro 2023可在多…

什么是区块链?

区块链 区块链 &#xff08;英语&#xff1a;blockchain&#xff09;是借由 密码学 与 共识机制 等技术建立&#xff0c;存储数据的 保证不可篡改和不可伪造的 分布式技术。 什么是区块 区块 就是将一批数据打包在一起&#xff0c;并且给打包出来的区块编号。第一个区块的编…

Kylin 安装novnc 远程访问

noVNC可以使用浏览器直接访问服务器&#xff0c;而不需要使用VNC客户端。 1.初始环境 关闭防火墙或允许IP访问本机 2.安装依赖 dnf install -y tigervnc-server git 3.git下载novnc git clone https://github.com/novnc/noVNC.git git clone https://gitee.com/yangyizhao…

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能(C++)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能&#xff08;C&#xff09; Baumer工业相机Baumer工业相机NEOAPI SDK和短曝光功能的技术背景Baumer工业相机通过NEOAPI SDK使用相机日志跟踪功能1.引用合适的类文件2.通过NEOAPI SDK使用相机日志跟踪功能3.通…

如何用数据赋能社媒营销决策?

在数字化时代&#xff0c;越来越多的商家开始意识到数据分析对于改善经营的重要性。 传统决策更多依赖过往经验、商业直觉、他人的思路模板等方法&#xff0c;或者依靠描述性统计、简单的数据分析。在数字时代&#xff0c;则通过精细化数据分析&#xff0c;做出更明智的营销决策…

S2-08 ESP-IDF开发 : 存储

S2-06 和 S2-07 暂时先不发&#xff0c;课上没给同学们将&#xff0c;分别是 DMA 和 USB 章节&#xff0c;作为专项讲 存储 ESP32 系列芯片中&#xff0c;不同型号的芯片所携带的 ROM、SRAM、RCT SRAM、PSRAM 以及 Flash大小不同&#xff0c;他们的作用如下&#xff1a; SRAM…

2023年总结我所经历的技术大变革

&#x1f4e2;欢迎点赞 &#xff1a;&#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff0c;赐人玫瑰&#xff0c;手留余香&#xff01;&#x1f4e2;本文作者&#xff1a;由webmote 原创&#x1f4e2;作者格言&#xff1a;新的征程&#xff0c;我们面对的不仅…

如何使用支付宝沙箱环境本地配置模拟支付并结合内网穿透远程调试

文章目录 前言1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级子域名8. 测试使用固定二级子域名访问 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff…

基本查找(顺序查找)

基本查找/顺序查找 基本思想思路代码示例输出结果 ​ 说明&#xff1a;顺序查找适合于存储结构为数组或者链表。 基本思想 顺序查找也称为线形查找&#xff0c;属于无序查找算法。从数据结构线的一端开始&#xff0c;顺序扫描&#xff0c;依次将遍历到的结点与要查找的值相比…