【力扣】304. 二维区域和检索 - 矩阵不可变 <二维前缀和>
目录
- 【力扣】304. 二维区域和检索 - 矩阵不可变
- 二维前缀和理论
- 初始化
- 计算面积
- 题解
【力扣】304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix,以下类型的多个请求:
- 计算其子矩形范围内元素的总和,该子矩阵的 左上角 为
(row1, col1),右下角 为(row2, col2)。
实现 NumMatrix 类:
NumMatrix(int[][] matrix)给定整数矩阵matrix进行初始化int sumRegion(int row1, int col1, int row2, int col2)返回 左上角(row1, col1)、右下角(row2, col2)所描述的子矩阵的元素 总和 。

提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
- 1 0 5 10^5 105 <= matrix[i][j] <= 1 0 5 10^5 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 1 0 4 10^4 104 次 sumRegion 方法
二维前缀和理论
初始化


因此二维前缀和预处理公式:
s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j]
计算面积


因此二维前缀和计算公式:(以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵的和)
s[x2][y2] - s[x2][y1 - 1] + s[x1 - 1][y2] -s[x1 - 1][y1 - 1]
题解
都加一,数组从(0,0)开始
class NumMatrix {int[][] s;public NumMatrix(int[][] matrix) {int m = matrix.length;if (m > 0) {int n = matrix[0].length;s = new int[m + 1][n + 1];// 初始化for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j];}}}}// 计算面积public int sumRegion(int x1, int y1, int x2, int y2) {return s[x2 + 1][y2 + 1] - s[x2 + 1][y1] - s[x1][y2 + 1] + s[x1][y1];}
}
相关文章:
【力扣】304. 二维区域和检索 - 矩阵不可变 <二维前缀和>
目录 【力扣】304. 二维区域和检索 - 矩阵不可变二维前缀和理论初始化计算面积 题解 【力扣】304. 二维区域和检索 - 矩阵不可变 给定一个二维矩阵 matrix,以下类型的多个请求: 计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, …...
线上问诊:数仓开发(三)
系列文章目录 线上问诊:业务数据采集 线上问诊:数仓数据同步 线上问诊:数仓开发(一) 线上问诊:数仓开发(二) 线上问诊:数仓开发(三) 文章目录 系列文章目录前言一、ADS1.交易主题1.交易综合统计2.各医院交易统计3.各性…...
微信小程序 通过响应式数据控制元素class属性
我想大家照这个和我最初的目的一样 希望有和vue中v-bind:class一样方便的指令 但答案不太尽人意 这里 我们只能采用 三元运算符的形式 参考代码如下 <view class"item {{ userId item.userId ? isThisUser : }}"> </view>这里 我们判断 如果当前ite…...
linux并发服务器 —— linux网络编程(七)
网络结构模式 C/S结构 - 客户机/服务器;采用两层结构,服务器负责数据的管理,客户机负责完成与用户的交互;C/S结构中,服务器 - 后台服务,客户机 - 前台功能; 优点 1. 充分发挥客户端PC处理能力…...
Java后端开发面试题——企业场景篇
单点登录这块怎么实现的 单点登录的英文名叫做:Single Sign On(简称SSO),只需要登录一次,就可以访问所有信任的应用系统 JWT解决单点登录 用户访问其他系统,会在网关判断token是否有效 如果token无效则会返回401&am…...
TiDB x 安能物流丨打造一栈式物流数据平台
作者:李家林 安能物流数据库团队负责人 本文以安能物流作为案例,探讨了在数字化转型中,企业如何利用 TiDB 分布式数据库来应对复杂的业务需求和挑战。 安能物流作为中国领先的综合型物流集团,需要应对大规模的业务流程ÿ…...
负载均衡算法实现
负载均衡算法实现 负载均衡介绍 负责均衡主要有以下五种方法实现: 1、轮询法 将请求按顺序轮流地分配到后端服务器上,它均衡地对待后端的每一台服务器,而不关心服务器实际的连接数和当前的系统负载; 2、随机法 通过系统的随机算法&#…...
Flutter 完美的验证码输入框 转载
刚开始看到这个功能的时候一定觉得so easy,开始的时候我也是这么觉得的,这还不简单,然而真正写的时候才发现并没有想象的那么简单。 先上图,不上图你们都不想看,我难啊,到Github: https://gith…...
SpringBoot整合Jpa实现增删改查功能(提供Gitee源码)
前言:在日常开发中,总是撰写一些简单的SQL会非常耗时间,Jpa可以完美的帮我们提高开发的效率,对于常规的SQL不需要我们自己撰写,相对于MyBatis有着更简单易用的功能,但是MyBatis自由度相对于Jpa会更高一些&a…...
微服务[Nacos]
CAP 1)一致性(Consistency) (所有节点在同一时间具有相同的数据) 2)可用性(Availability)(保证每个请求不管成功或者失败都有响应) 3)分区容错(Partition tolerance)(系统中任意信息的丢失或失败不会影响系统的继续运作) 一、虚拟机镜像准备 …...
8K视频来了,8K 视频编辑的最低系统要求
当今 RED、Canon、Ikegami、Sony 等公司的 8K 摄像机以及 8K 电视,许多视频内容制作人和电影制作人正在认真考虑 8K 拍摄、编辑和后期处理,需要什么样的系统来处理如此海量的数据? 中央处理器(CPU) 首先,…...
AsyncContext优雅实现HTTP长轮询接口
一、背景 接到一个需求,实现方案时需要提供一个HTTP接口,接口需要hold住5-8秒,轮询查询数据库,一旦数据库中值有变化,取出变化的值进行处理,处理完成后返回响应。这不就是长轮询吗,如何优雅的实…...
如何制作一个百货小程序
在这个数字化时代,小程序已成为各行各业的必备工具。其中,百货小程序因其便捷性和多功能性,越来越受到人们的青睐。那么,如何制作一个百货小程序呢?下面,我们就详细介绍一下无需编写代码的步骤。 一、进入后…...
【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法
文章目录 局部搜索算法内存限制局部搜索算法示例:n-皇后爬山算法随机重启爬山模拟退火算法局部剪枝搜索遗传算法小结 局部搜索算法 在某些规模太大的问题状态空间内,A*往往不够用 问题空间太大了无法访问 f 小于最优的所有状态通常,甚至无法储…...
MATLAB旋转动图的绘制
MATLAB旋转动图的绘制 文章目录 MATLAB旋转动图的绘制1、动图效果2、matlab代码 利用matlab实现三维旋转动图的绘制。 1、动图效果 2、matlab代码 close all clear clcf(x,y,z)(x.^2 (9./4).*y.^2 z.^2 - 1).^3 - x.^2.*z.^3 - (9./80).*y.^2.*z.^3; [x,y,z]meshgrid(linspac…...
算法笔记 近似最近邻查找(Approximate Nearest Neighbor Search,ANN)
1 介绍 精准最近邻搜索中数据维度一般较低,所以会采用穷举搜索,即在数据库中依次计算其中样本与所查询数据之间的距离,抽取出所计算出来的距离最小的样本即为所要查找的最近邻。 当数据量非常大的时候,搜索效率急剧下降。——>…...
uni-app 之 vue语法
uni-app 之 vue语法 image.png --- v-html 字符 --- image.png <template><view><view>{{title}}</view>--- v-html 字符 ---<view>{{title2}}</view><view v-html"title2"></view><view>{{arr}}</view&g…...
Android之RecyclerView仿ViewPage滑动
文章目录 前言一、效果图二、实现步骤1.xml主布局2.所有用到的drawable资源文件3.xml item布局4.adapter适配器5.javabean实体类6.activity使用 总结 前言 我们都知道ViewPageFragment滑动,但是的需求里面已经有了这玩意,但是在Fragment中还要有类似功能…...
【owt-server】AudioSendAdapter分析
owt-server/source/core/rtc_adapter/AudioSendAdapter.cc使用其他线程运行rtprtcpmodule taskrunner分配线程:因此,对rtprtcp的使用都是加了mutex的:首先为音频发送者生成一个随机的ssrc并注册 // SSRCs of this type.std::vector<uint32_t> ssrcs_;发送还要向rtprtc…...
day33 List接口
List实现类 java.util.ArrayList: 底层通过数组保存数据 , 查询快,增删慢 java.util.LinkedList: 底层通过链表保存数据, 查询慢,增删快 如果对操作性能没有特殊要求,我们一般选择ArrayList…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
