当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...