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

【力扣】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&#xff0c;以下类型的多个请求&#xff1a; 计算其子矩形范围内元素的总和&#xff0c;该子矩阵的 左上角 为 (row1, …...

线上问诊:数仓开发(三)

系列文章目录 线上问诊&#xff1a;业务数据采集 线上问诊&#xff1a;数仓数据同步 线上问诊&#xff1a;数仓开发(一) 线上问诊&#xff1a;数仓开发(二) 线上问诊&#xff1a;数仓开发(三) 文章目录 系列文章目录前言一、ADS1.交易主题1.交易综合统计2.各医院交易统计3.各性…...

微信小程序 通过响应式数据控制元素class属性

我想大家照这个和我最初的目的一样 希望有和vue中v-bind:class一样方便的指令 但答案不太尽人意 这里 我们只能采用 三元运算符的形式 参考代码如下 <view class"item {{ userId item.userId ? isThisUser : }}"> </view>这里 我们判断 如果当前ite…...

linux并发服务器 —— linux网络编程(七)

网络结构模式 C/S结构 - 客户机/服务器&#xff1b;采用两层结构&#xff0c;服务器负责数据的管理&#xff0c;客户机负责完成与用户的交互&#xff1b;C/S结构中&#xff0c;服务器 - 后台服务&#xff0c;客户机 - 前台功能&#xff1b; 优点 1. 充分发挥客户端PC处理能力…...

Java后端开发面试题——企业场景篇

单点登录这块怎么实现的 单点登录的英文名叫做&#xff1a;Single Sign On&#xff08;简称SSO&#xff09;,只需要登录一次&#xff0c;就可以访问所有信任的应用系统 JWT解决单点登录 用户访问其他系统&#xff0c;会在网关判断token是否有效 如果token无效则会返回401&am…...

TiDB x 安能物流丨打造一栈式物流数据平台

作者&#xff1a;李家林 安能物流数据库团队负责人 本文以安能物流作为案例&#xff0c;探讨了在数字化转型中&#xff0c;企业如何利用 TiDB 分布式数据库来应对复杂的业务需求和挑战。 安能物流作为中国领先的综合型物流集团&#xff0c;需要应对大规模的业务流程&#xff…...

负载均衡算法实现

负载均衡算法实现 负载均衡介绍 负责均衡主要有以下五种方法实现: 1、轮询法 将请求按顺序轮流地分配到后端服务器上&#xff0c;它均衡地对待后端的每一台服务器&#xff0c;而不关心服务器实际的连接数和当前的系统负载&#xff1b; 2、随机法 通过系统的随机算法&#…...

Flutter 完美的验证码输入框 转载

刚开始看到这个功能的时候一定觉得so easy&#xff0c;开始的时候我也是这么觉得的&#xff0c;这还不简单&#xff0c;然而真正写的时候才发现并没有想象的那么简单。 先上图&#xff0c;不上图你们都不想看&#xff0c;我难啊&#xff0c;到Github&#xff1a; https://gith…...

SpringBoot整合Jpa实现增删改查功能(提供Gitee源码)

前言&#xff1a;在日常开发中&#xff0c;总是撰写一些简单的SQL会非常耗时间&#xff0c;Jpa可以完美的帮我们提高开发的效率&#xff0c;对于常规的SQL不需要我们自己撰写&#xff0c;相对于MyBatis有着更简单易用的功能&#xff0c;但是MyBatis自由度相对于Jpa会更高一些&a…...

微服务[Nacos]

CAP 1&#xff09;一致性(Consistency) (所有节点在同一时间具有相同的数据) 2&#xff09;可用性(Availability)(保证每个请求不管成功或者失败都有响应) 3&#xff09;分区容错(Partition tolerance)(系统中任意信息的丢失或失败不会影响系统的继续运作) 一、虚拟机镜像准备 …...

8K视频来了,8K 视频编辑的最低系统要求

当今 RED、Canon、Ikegami、Sony 等公司的 8K 摄像机以及 8K 电视&#xff0c;许多视频内容制作人和电影制作人正在认真考虑 8K 拍摄、编辑和后期处理&#xff0c;需要什么样的系统来处理如此海量的数据&#xff1f; 中央处理器&#xff08;CPU&#xff09; 首先&#xff0c;…...

AsyncContext优雅实现HTTP长轮询接口

一、背景 接到一个需求&#xff0c;实现方案时需要提供一个HTTP接口&#xff0c;接口需要hold住5-8秒&#xff0c;轮询查询数据库&#xff0c;一旦数据库中值有变化&#xff0c;取出变化的值进行处理&#xff0c;处理完成后返回响应。这不就是长轮询吗&#xff0c;如何优雅的实…...

如何制作一个百货小程序

在这个数字化时代&#xff0c;小程序已成为各行各业的必备工具。其中&#xff0c;百货小程序因其便捷性和多功能性&#xff0c;越来越受到人们的青睐。那么&#xff0c;如何制作一个百货小程序呢&#xff1f;下面&#xff0c;我们就详细介绍一下无需编写代码的步骤。 一、进入后…...

【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

文章目录 局部搜索算法内存限制局部搜索算法示例&#xff1a;n-皇后爬山算法随机重启爬山模拟退火算法局部剪枝搜索遗传算法小结 局部搜索算法 在某些规模太大的问题状态空间内&#xff0c;A*往往不够用 问题空间太大了无法访问 f 小于最优的所有状态通常&#xff0c;甚至无法储…...

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 介绍 精准最近邻搜索中数据维度一般较低&#xff0c;所以会采用穷举搜索&#xff0c;即在数据库中依次计算其中样本与所查询数据之间的距离&#xff0c;抽取出所计算出来的距离最小的样本即为所要查找的最近邻。 当数据量非常大的时候&#xff0c;搜索效率急剧下降。——>…...

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滑动&#xff0c;但是的需求里面已经有了这玩意&#xff0c;但是在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&#xff1a; 底层通过数组保存数据 &#xff0c; 查询快&#xff0c;增删慢 java.util.LinkedList&#xff1a; 底层通过链表保存数据&#xff0c; 查询慢&#xff0c;增删快 如果对操作性能没有特殊要求&#xff0c;我们一般选择ArrayList…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...

【SSM】SpringMVC学习笔记7:前后端数据传输协议和异常处理

这篇学习笔记是Spring系列笔记的第7篇&#xff0c;该笔记是笔者在学习黑马程序员SSM框架教程课程期间的笔记&#xff0c;供自己和他人参考。 Spring学习笔记目录 笔记1&#xff1a;【SSM】Spring基础&#xff1a; IoC配置学习笔记-CSDN博客 对应黑马课程P1~P20的内容。 笔记2…...

【NLP】 38. Agent

什么是 Agent&#xff1f; 一个 Agent 就是能够 理解、思考&#xff0c;并且进行世界交互 的模型系统&#xff0c;并不是纯粹的 prompt 返回器。 它可以&#xff1a; 读取外部数据&#xff08;文件/API&#xff09;使用记忆进行上下文维持用类Chain-of-Thought (CoT)方式进行…...

Digital IC Design Flow

Flow介绍 1.设计规格 架构师根据市场需求制作算法模型(Algorithm emulation)及芯片架构(Chip architecture),确定芯片设计规格书(Chip design specification) 原型验证 原型验证(Prototype Validation)通常位于产品开发流程的前期阶段,主要是在设计和开发的初步阶…...

稻米分类和病害检测数据集(猫脸码客第237期)

稻米分类图像数据集&#xff1a;驱动农业智能化发展的核心资源 引言 在全球农业体系中&#xff0c;稻米作为最关键的粮食作物之一&#xff0c;其品种多样性为人类饮食提供了丰富选择。然而&#xff0c;传统稻米分类方法高度依赖人工经验&#xff0c;存在效率低、主观性强等缺…...