796. 子矩阵的和
Problem: 796. 子矩阵的和
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组,使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样,对于任意的子矩阵(x1, y1)到(x2, y2),我们可以通过四个前缀和的值快速计算出其和。
解题方法
1.首先,我们需要读入矩阵的大小和矩阵的元素值。
2.然后,我们计算二维前缀和。对于每个位置(i, j),其前缀和的值等于其上方元素的前缀和加上其左方元素的前缀和,再减去其左上方元素的前缀和,最后加上其自身的值。
3.最后,对于每个查询,我们可以通过四个前缀和的值快速计算出子矩阵的和。
复杂度
时间复杂度:
预处理的时间复杂度为 O ( n ∗ m ) O(n*m) O(n∗m),其中 n n n和 m m m分别为矩阵的行数和列数。
每次查询的时间复杂度为 O ( 1 ) O(1) O(1)。
空间复杂度:
我们需要额外的 O ( n ∗ m ) O(n*m) O(n∗m)的空间来存储前缀和。
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int n, m, q;static int MAXN = 1001;static int MAXM = 1001;static int[][] arr = new int[MAXN][MAXM];public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();q = nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] = nextInt();}}for (int i = 1; i <= n; i++) {arr[i][0] += arr[i - 1][0];}for (int j = 1; j <= m; j++) {arr[0][j] += arr[0][j - 1];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];}}while (q-- > 0) {int x1 = nextInt();int y1 = nextInt();int x2 = nextInt();int y2 = nextInt();out.println(arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]);}out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
相关文章:
796. 子矩阵的和
Problem: 796. 子矩阵的和 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组,使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样,对于任意的子矩阵(x…...
如何在 Python 中处理 Unicode
介绍 Unicode 是世界上大多数计算机的标准字符编码。它确保文本(包括字母、符号、表情符号,甚至控制字符)在不同设备、平台和数字文档中显示一致,无论使用的操作系统或软件是什么。它是互联网和计算机行业的重要组成部分…...
CSDN文章导出PDF整理状况一览
最近CSDN有了导出文章PDF功能,导出的PDF还可以查询, 因此,把文章导出PDF,备份一下自己的重要资料。 目前整理内容如下 No.文章标题整理时间整理之后 文章更新Size (M)10001_本地电脑-开发相关软件保持位…...
jmeter-05变量(用户定义变量,用户参数,csv文档参数化)
文章目录 一、jmeter有三种变量二、用户定义变量(这个更多的可以理解为全局变量)1、设置2、引用三、用户参数(可以理解为局部变量)1、设置2、引用3、用户参数化要配合线程组的线程数使用4、结果五、csv文档参数1、创建csv文件2、设置2、引用csv文件可以配合线程组的线程数,…...
CSS之水平垂直居中
如何实现一个div的水平垂直居中 <div class"content-wrapper"><div class"content">content</div></div>flex布局 .content-wrapper {width: 400px;height: 400px;background-color: lightskyblue;display: flex;justify-content:…...
2.8日学习打卡----初学RabbitMQ(三)
2.8日学习打卡 一.springboot整合RabbitMQ 之前我们使用原生JAVA操作RabbitMQ较为繁琐,接下来我们使用 SpringBoot整合RabbitMQ,简化代码编写 创建SpringBoot项目,引入RabbitMQ起步依赖 <!-- RabbitMQ起步依赖 --> <dependency&g…...
Unity学习笔记(零基础到就业)|Chapter02:C#基础
Unity学习笔记(零基础到就业)|Chapter02:C#基础 前言一、复杂数据(变量)类型part01:枚举数组1.特点2.枚举(1)基本概念(2)申明枚举变量(3ÿ…...
容器化的基础概念:不可变基础设施解释:将服务器视为乐高积木,而非橡皮泥。
不可变基础设施解释:将服务器视为乐高积木,而非橡皮泥。 想象一下用乐高积木代替橡皮泥进行搭建。使用橡皮泥时,您可以直接塑形和改变它。而使用乐高积木,您需要逐个零件搭建特定结构,并在需要时整体替换它们。这就是…...
智胜未来,新时代IT技术人风口攻略-第二版(弃稿)
文章目录 抛砖引玉 鸿蒙生态小科普焦虑之下 理想要落到实处校园鼎力 鸿蒙发展不可挡培训入场 机构急于吃红利企业布局 鸿蒙应用规划动智胜未来 技术人风口来临 鸿蒙已经成为行业的焦点,未来的发展潜力无限。作为一名程序员兼UP主,我非常荣幸地接受了邀请…...
Git分支和迭代流程
Git分支 feature分支:功能分支 dev分支:开发分支 test分支:测试分支 master分支:生产环境分支 hotfix分支:bug修复分支。从master拉取,修复并测试完成merge回master和dev。 某些团队可能还会有 reale…...
数据库管理-第150期 Oracle Vector DB AI-02(20240212)
数据库管理150期 2024-02-12 数据库管理-第150期 Oracle Vector DB & AI-02(20240212)1 LLM2 LLM面临的挑战3 RAG4 向量数据库LLM总结 数据库管理-第150期 Oracle Vector DB & AI-02(20240212) 作者:胖头鱼的鱼…...
MySQL双写机制
双写机制 问题的出现 在发生数据库宕机时,可能Innodb正在写入某个页到表中,但是这个页只写了一部分,这种情况被称为部分写失效,虽然innodb会先写重做日志,在修改页,但是重做日志中记录的是对页的物理操作,但…...
uniapp的配置和使用
①安装环境和编辑器 注册小程序账号 微信开发者工具下载 uniapp 官网 HbuilderX 下载 首先先下载Hbuilder和微信开发者工具 (都是傻瓜式安装),然后注册小程序账号: 拿到appid: ②简单通过demo使用微信开发者工具和…...
【ES】--Elasticsearch的分词器深度研究
目录 一、问题描述及分析二、analyze分析器原理三、 multi-fields字段支持多场景搜索(如同时简繁体、拼音等)1、ts_match_analyzer配置分词2、ts_match_all_analyzer配置分词3、ts_match_1_analyzer配置分词4、ts_match_2_analyzer配置分词5、ts_match_3_analyzer配置分词6、ts…...
【Langchain Agent研究】SalesGPT项目介绍(三)
【Langchain Agent研究】SalesGPT项目介绍(二)-CSDN博客 上节课,我们介绍了salesGPT项目的初步的整体结构,poetry脚手架工具和里面的run.py。在run.py这个运行文件里,引用的最主要的类就是SalesGPT类,今天我…...
Java安全 URLDNS链分析
Java安全 URLDNS链分析 什么是URLDNS链URLDNS链分析调用链路HashMap类分析URL类分析 exp编写思路整理初步expexp改进最终exp 什么是URLDNS链 URLDNS链是Java安全中比较简单的一条利用链,无需使用任何第三方库,全依靠Java内置的一些类实现,但…...
【网站项目】026校园美食交流系统
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。🌹赠送计算机毕业设计600个选题excel文件,帮助大学选题。赠送开题报告模板ÿ…...
使用raw.gitmirror.com替换raw.githubusercontent.com以解决brew upgrade python@3.12慢的问题
MacOS系统上,升级python3.12时,超级慢,而且最后还失败了。看了日志,发现是用curl从raw.githubusercontent.com上下载Python安装包超时了。 解决方案一:开启翻墙工具,穿越围墙 解决方案二:使用…...
深度学习的进展
#深度学习的进展# 深度学习的进展 深度学习是人工智能领域的一个重要分支,它利用神经网络模拟人类大脑的学习过程,通过大量数据训练模型,使其能够自动提取特征、识别模式、进行分类和预测等任务。近年来,深度学习在多个领域取得…...
[高性能] - 缓存架构
对于交易系统来说,低延时是核心业务的基本要求。因此需要对业务进行分级,还需要对数据按质量要求进行分类,主要包含两个维度:重要性,延时要求,数据质量。共包含以下三种场景: 1. 重要 延时性要…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
