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

面试算法13:二维子矩阵的数字之和

题目

输入一个二维矩阵,如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和?对于同一个二维矩阵,计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如,输入图2.1中的二维矩阵,以及左上角坐标为(2,1)和右下角坐标为(4,3)的子矩阵,该函数输出8。
在这里插入图片描述

分析

如果不考虑时间复杂度,则采用蛮力法用两个嵌套的循环总是可以求出一个二维矩阵的数字之和。如果矩阵的行数和列数分别是m和n,那么这种蛮力法的时间复杂度是O(mn)。

只是这个题目提到,对于一个二维矩阵,可能由于输入不同的坐标而反复求不同子矩阵的数字之和,这说明应该优化求和的过程,要尽可能快地实现子矩阵的数字求和。
在这里插入图片描述
阴影面积 = 黄色正方形面积 + 绿色正方行面积 - 红色长方形面积 - 蓝色长方形面积

因此,可以在预处理阶段求出从左上角坐标为(0,0)到每个右下角坐标的子矩阵的数字之和。首先创建一个和输入矩阵大小相同的辅助矩阵sums,该矩阵中的坐标(i,j)的数值为输入矩阵中从左上角坐标(0,0)到右下角坐标(i,j)的子矩阵的数字之和。

下面分析如何生成辅助矩阵sums,即求得数组中的每个数字sums[i][j]。按照生成辅助矩阵sums的规则,sums[i][j]的值等于输入矩阵中从左上角坐标为(0,0)到右下角坐标为(i,j)的子矩阵的数字之和。可以把从左上角坐标为(0,0)到右下角坐标为(i,j)的子矩阵的数字看成由两部分组成。第1部分是从左上角坐标为(0,0)到右下角坐标为(i-1,j)的子矩阵,该子矩阵的数字之和等于sums[i-1][j]。第2部分是输入矩阵中第i行中列号从0到j的所有数字。如果按照从左到右的顺序计算sums[i][j],则可以逐个累加第i行的数字,从而得到子矩阵第2部分的数字之和。

public class Test {public static void main(String[] args) {int[][] nums = {{3, 0, 1, 4, 2},{5, 6, 3, 2, 1},{1, 2, 0, 1, 5},{4, 1, 0, 1, 7},{1, 0, 3, 0, 5}};sums = generateNumMatrix(nums);int result = sumRegion(2, 1, 4, 3);System.out.println(result);}private static int[][] sums;public static int[][] generateNumMatrix(int[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return null;}int[][] sums = new int[matrix.length + 1][matrix[0].length + 1];for (int i = 0; i < matrix.length; i++) {int rowSum = 0;for (int j = 0; j < matrix[0].length; j++) {rowSum += matrix[i][j];sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;}}return sums;}public static int sumRegion(int row1, int col1, int row2, int col2) {//return sums[row2][col2] + sums[row1-1][col1-1] - sums[row1-1][col2] - sums[row2][col1-1];return sums[row2 + 1][col2 + 1] + sums[row1][col1] - sums[row1][col2 + 1] - sums[row2 + 1][col1];}
}

如果输入矩阵的行数和列数分别是m和n,那么辅助数组sums的行数和列数分别为m+1和n+1,这样只是为了简化代码逻辑。如果用公式sums[r2][c2]+sums[r1-1][c2]-sums[r2][c1-1]+sums[r1-1][c1-1]求解左上角坐标为(r1,c1)、右下角坐标为(r2,c2)的子矩阵的数字之和,由于坐标值r1或c1有可能等于0,因此r1-1或c1-1可能是负数,不再是有效的数组下标。如果在矩阵的最上面增加一行,最左面增加一列,这样就不必担心出现数组下标为-1的情形。

相关文章:

面试算法13:二维子矩阵的数字之和

题目 输入一个二维矩阵&#xff0c;如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和&#xff1f;对于同一个二维矩阵&#xff0c;计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如&#xff0c;输入图2.1中的二维矩阵&#xff0c;以及左上角坐标…...

Vue安装插件时候中遇到冲突依赖解决方案

错误如下&#xff1a; npm ERR! code ERESOLVE npm ERR! ERESOLVE could not resolve npm ERR! npm ERR! While resolving: vue/eslint-config-standard6.1.0 npm ERR! Found: eslint-plugin-vue8.7.1 npm ERR! node_modules/eslint-plugin-vue npm ERR! dev eslint-pl…...

realloc函数应用IO泄露体验

本题主要介绍realloc函数&#xff0c;平时我们使用realloc最多便是在打malloc_hook–>onegadget的时候&#xff0c;使用realloc_hook调整onegadget的栈帧&#xff0c;从而getshell。 在realloc函数中&#xff0c;也能像malloc一样创建堆&#xff0c;并且比malloc麻烦一些&a…...

(c语言)野指针

#include<stdio.h> //野指针 int* test() { int a 10; return &a; } int main() { //野指针一&#xff1a; int* p; *p 10; //非法访问内存 //p没有初始化&#xff0c;就意味着没有明确的指向 //一个局部变量不初始化的话&#xff…...

【Git】轻松学会 Git(一):掌握 Git 的基本操作

文章目录 前言一、创建 Git 本地仓库1.1 什么是仓库1.2 创建本地仓库1.3 .git 目录结构 二、配置 Git三、认识 Git 的工作区、暂存区和版本库3.1 什么是 Git 的工作区、暂存区和版本库3.2 工作区、暂存区和版本库之间的关系 四、添加文件4.1 添加文件到暂存区和版本库中的命令4…...

rust trait对象

在拥有继承的语言中&#xff0c;可以定义一个名为shape的基类&#xff0c;该类上有一个draw方法。其他的类比如Button、SelectBox继承shape。它们各自覆盖draw方法。调用这些子类的draw方法时&#xff0c;就可以把它们统一当作shape来使用。不过Rust并没有继承&#xff0c;如果…...

Linux学习第21天:Linux内核定时器驱动开发: 流淌的时间长河

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 在人类的发展进化中&#xff0c;时间是一个非常重要神秘的物质量。任何事物都是在时间的长河中流淌发生、发展、变化。我们进行驱动开发中对时间的定义和使用也是…...

Centos服务在服务器重启后自启

以Dolphin为例 打开rc.local文件以编辑&#xff1a; sudo vi /etc/rc.d/rc.local在文件中添加您的启动命令。在您的情况下&#xff0c;要添加的命令如下&#xff1a; sh /opt/dolphinscheduler/zookeeper/bin/zkServer.sh start sh /opt/dolphinscheduler/dolphinscheduler/…...

慢性疼痛治疗服务公司Kindly MD申请700万美元纳斯达克IPO上市

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 猛兽财经获悉,慢性疼痛治疗服务公司Kindly MD近期已向美国证券交易委员会&#xff08;SEC&#xff09;提交招股书&#xff0c;申请在纳斯达克IPO上市&#xff0c;股票代码为&#xff08;KDLY&#xff09;,Kindly MD计划通过…...

代码随想录 Day6 哈希 LeetcodeT454 四数之和II T383赎金信 T15 三数之和 T18 四数之和

本文代码思路来源于: 代码随想录 前言 希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用api,比较方便理解. LeetCode T454 四数之和 题目链接:454. 四数相加 II - 力扣&#xff08;LeetCode&#xff09; 题目思路 暴力解法仍然是遍历四个数组解决此题, 哈希的思路有…...

干货速来|教你如何撰写毕业论文

撰写毕业论文对于正常大学毕业至关重要。毕业论文是对学生在大学期间所学知识的综合运用和深入研究的体现&#xff0c;也是对学术能力和独立思考能力的考验。 撰写毕业论文的过程需要学生投入大量的时间和精力&#xff0c;包括选题、文献综述、研究方法选择、数据收集和分析、…...

【ROS 2】-2 话题通信

飞书原文链接&#xff1a; Docs...

Unity之NetCode多人网络游戏联机对战教程(2)--简单实现联机

文章目录 1.添加基本组件2.创建NetworkManager组件3.创建Player4.创建地面5.创建GameManager6.编译运行7. 测试联机后话 1.添加基本组件 NetworkManagerPlayerScene 2.创建NetworkManager组件 创建一个空物体&#xff0c;命名为NetworkManager 选择刚刚创建的NetworkManager…...

makdown文法

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…...

新手程序员怎么接单?

程序员如何在自己年富力强的时候&#xff0c;最大化发挥自己的能力&#xff1f;将超能力转化为“钞能力”&#xff1f; 有人还在苦哈哈当老黄牛&#xff0c;一身使不完的牛劲&#xff0c;有人已经另辟蹊径&#xff0c;开创了自己的一片致富小天地。 接单找兼职&#xff0c;就…...

接口测试——接口协议抓包分析与mock_L2

目录&#xff1a; 抓包工具charles抓包工具fiddler抓包工具证书配置app抓包实战练习接口测试实战练习 1.抓包工具charles 工具介绍 支持 SSL 代理支持流量控制支持重发网络请求&#xff0c;方便后端调试支持修改网络请求参数支持网络请求的截获并动态修改可以自动将 json 或…...

Seata入门系列【1】安装seata 1.7.1+nacos 2.1.1

1 介绍 Seata 是一款开源的分布式事务解决方案&#xff0c;致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式&#xff0c;为用户打造一站式的分布式解决方案。 Github: https://github.com/seata/seata 官方文档&#xff1a;h…...

2023年职业院校技能大赛中职组----大数据应用与服务赛项任务书试题

2023年职业院校技能大赛中职组----大数据应用与服务赛项任务书试题 模块一&#xff1a;数据库系统运维&#xff08;25分&#xff09;任务一&#xff1a;数据库系统搭建&#xff08;10分&#xff09;任务二&#xff1a;房源数据库系统运维&#xff08;15分&#xff09; 模块二&a…...

产品经理的职业前景怎么样?一文为你全面解答!

随着科技的迅速发展和市场竞争的日益激烈&#xff0c;产品经理这个职业变得越来越炙手可热。产品经理负责一款产品的全生命周期管理&#xff0c;从需求收集到设计、开发、测试、发布&#xff0c;再到市场推广和用户反馈&#xff0c;都需要产品经理参与决策。因此&#xff0c;这…...

【深度学习】图像去噪(2)——常见网络学习

【深度学习】图像去噪 是在 【深度学习】计算机视觉 系列文章的基础上&#xff0c;再次针对深度学习&#xff08;尤其是图像去噪方面&#xff09;的基础知识有更深入学习和巩固。 1 DnCNN 1.1 网络结构 1.1.1 残差学习 1.1.2 Batch Normalization (BN) 1.1.2.1 背景和目标…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...