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. 重要 延时性要…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
