leetcode - 矩阵区域和
1314. 矩阵区域和 - 力扣(LeetCode)
给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:
i - k <= r <= i + k,j - k <= c <= j + k且(r, c)在矩阵内。
示例 1:输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]
示例 2:输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]
题意就是要计算 假设给出的 mat[i][j] ,那么就要是要计算下图当中给出的 区域的全部元素之和:

新返回的矩形当中,应该存储的是上述 绿色区域当中的全部的 元素之和。(k = 1)
所以,我们可以利用二位矩阵的前缀和 来解决上述的问题。
对于 前缀和 二位矩阵 的计算,可以参考之前博客:
leedcode 刷题 - 除自身以外数组的乘积 - 和为 K 的子数组-CSDN博客
leetcode - 串联所有单词的子串 - 最小覆盖子串 - x 的平方根-CSDN博客

上述就是递归公式,但是 dp[x2][y2] 不是在 dp 这个 二维前缀和数组当中的,这个位置是没有 数据的,所以,其实这个位置的数据是在 mat 当中的。也就对应的是 mat[i][j] 。
所以,上述就计算出了存储前缀和的二维数组。
此时,我们只需要根据上述的 存储前缀和的二维数组,就可以像下图当中这样去 计算,某一个满足题意的 区间的 元素之和:

即:
ret = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]
上述就是递推公式。
在上述计算出递推公式之后,就可以开始计算上述的 x1 y1 和 x2 y2 了。

上述前缀和二维数组当中的 下标是从 (1, 1) 开始计数的,但是,在题目当中的二维数组是从 (0,0) 开始计数的,所以,为了方便上述 前缀和二维数组的计算,所以,我们直接把 dp 数组加一行加一列:

使用黑色位置存储元素值。
dp[x][y] -> mat[x - 1][y -1]dp[x][y] -> ans[x - 1][y -1]
所以此时应该是:

完整代码:
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();//计算出前缀和二维数组vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i = 1;i <= m;i++)for(int j = 1;j <= n;j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];// 计算出 answer 二维数组的值vector<vector<int>> ret(m, vector<int>(n));for(int i = 0;i < m;i++)for(int j = 0;j < n;j++){int x1 = max(0 , i - k) + 1, y1 = max(0 , j - k) + 1;int x2 = min(m - 1 , i + k) + 1, y2 = min(n - 1 , j + k) + 1;ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];}return ret;}
};
相关文章:
leetcode - 矩阵区域和
1314. 矩阵区域和 - 力扣(LeetCode) 给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和: i - k < r < i k, j - k < c …...
头歌JUnit单元测试相关实验进阶
JUnit是一个由 Erich Gamma 和 Kent Beck 编写的一个回归测试框架(regression testing framework),主要供 Java 开发人员编写单元测试。Junit在极限编程和重构中被极力推荐使用,因为它可以大大地提高开发的效率。 Junit的特性&…...
【kafka实践】11|消费位移提交
消费者位移 消费者位移这一节介绍了消费者位移的基本概念和消息格式,本节我们来聊聊消费位移的提交。 Consumer 需要向 Kafka 汇报自己的位移数据,这个汇报过程被称为提交位移(Committing Offsets)。因为 Consumer 能够同时消费…...
Mac卸载、安装Python
卸载 说明 对于删除 Python,我们首先要知道其具体都安装了什么,实际上,在安装 Python 时,其自动生成: Python framework,即 Python 框架;Python 应用目录;指向 Python 的连接。 …...
算法——滑动窗口
滑动窗口大致分为两类:一类是窗口长度固定的,即left和right可以一起移动;另一种是窗口的长度变化(例如前五道题),即right疯狂移动,left没怎么动,这类题需要观察单调性(即指针)等各方…...
带头双向循环链表:一种高效的数据结构
💓 博客主页:江池俊的博客⏩ 收录专栏:数据结构探索👉专栏推荐:✅cpolar ✅C语言进阶之路💻代码仓库:江池俊的代码仓库🔥编译环境:Visual Studio 2022🎉欢迎大…...
C++基础 -34- 输入输出运算符重载
输出运算符重载格式 ostream & operator<<(ostream &out,person a) {cout << a.a << endl;return out; }举例输出运算符重载 #include "iostream"using namespace std;class person {public:person(int a):a(a){}int a; };ostream &…...
MimicGen论文分析与资料汇总
MimicGen论文分析与资料汇总 前言论文分析相关资料汇总 前言 论文分析 相关资料汇总 Paper:MimicGen: A Data Generation System for Scalable Robot Learning using Human Demonstrations mimicgen.github 破局利刃!英伟达合成数据新成果:为机器人造…...
JAVA-每一页PDF转图片
结论:1、iText几乎找不到如何PDF转图片的信息,但能找到获取到PDF里面的图片并保存下来的信息;2、PDF box满大街都是参考代码(下面会附上一个作为参考);3、收费的库使用起来更简单,但就是要收费&…...
VS安装QT VS Tools编译无法通过
场景: 项目拷贝到虚拟机内部后,配置好相关环境后无法编译,安装QT VS Tools后依旧无法编译,查找资料网上说的是QT工具版本不一致导致的,但反复试了几个版本后依旧无法编译通过。错误信息如下: C:\Users\Ad…...
【C语言之 CJson】学CJson看这一篇就够了
文章目录 前言一、下载CJson二、创建一个json2.1 创建json对象cJSON类型详解 2.2 创建键值对2.3 添加嵌套的 JSON 对象2.4 添加数组创建数组添加元素到数组添加数组到obj 2.5 将 JSON 对象转为字符串2.6 释放内存2.7 示例代码 三、解析json3.1 解析json root3.2 把一个key解析出…...
使用Java语言实现字母之间的大小写转换
这个类的作用为实现字母之间的大小写转换,通过加减32来完成。 输入的代码 import java.util.Scanner; public class WordChangeDemo {public static void main(String[] args){try (Scanner in new Scanner(System.in)) {System.out.println("请输入您要进…...
Docker的数据持久化;Docker网络;Dockerfile编写
Docker的数据持久化;Docker网络;Dockerfile编写; 文章目录 Docker的数据持久化;Docker网络;Dockerfile编写;**Docker的数据持久化**1)将本地目录映射到容器里2)数据卷3)将…...
OpenHarmony亮相MTSC 2023 | 质量效率共进,赋能应用生态发展
11月25日,MTSC 2023第十二届中国互联网测试开发大会在深圳登喜路国际大酒店圆满举行。大会以“软件质量保障体系和测试研发技术交流”为主要目的,旨在为行业搭建一个深入探讨和交流的桥梁和平台。OpenAtom OpenHarmony(简称“OpenHarmony”&a…...
windows11 调整鼠标灵敏度方法
首先 我们打开电脑设置 或者在 此电脑/此计算机/我的电脑 右击选择属性 然后 有的电脑 左侧菜单中 直接就有 设备 然后在设备中直接就可以找到 鼠标 选项 调整光标速度即可 如果操作系统和我的一样 可以直接搜索鼠标 然后 选择 鼠标设置 然后 调整上面的鼠标指针速度即可...
贪心算法个人见解
目录 基本思想: 贪心算法的步骤: 示例: 贪心算法(Greedy Algorithm)是一种基于贪心策略的算法范式,它在每一步选择中都采取当前状态下的最优选择,而不考虑全局最优解。贪心算法通常适用于那些…...
Win中Redis部署与配置
1.下载msi版本 下载传送门 2.双击next-->next安装安装 3.密码配置以及开机自启 在配置文件中配置相应配置进行配置密码以及端口和ip port 6379指定 Redis 监听端口,默认端口为 6379,作者在自己的一篇博文中解释了为什么选用 6379 作为默认端口&…...
vue el-button 封装及使用
使用了 Element UI 中的 el-button 组件,并对其进行了封装和定制。 创建组件index.vue (src/common-ui/button/index.vue) <template><el-buttonclass"h-button":type"type":icon"hIcon":disabled"disabled"clic…...
QT之QMediaPlayer的用法
QT之QMediaPlayer的用法 成员函数例程 成员函数 1)setMedia(const QMediaContent &media, QIODevice *stream nullptr) 设置要播放的媒体内容,其中参数media指定了媒体内容,stream参数指定了用于读取媒体的输入设备(如文件流࿰…...
TCP_报文格式解读
报文格式 header部分字段含义解析 固定字段 对于header中固定部分字段含义,见之前的blog《TCP报文分析》; 对部分字段含义补充说明 Data Offset:4bit,tcp header的长度,单位:32bit(4字节&…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
