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

【算法|前缀和系列No.5】leetcode1314. 矩阵区域和

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【Leetcode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

给你一个 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]]

注意:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

2️⃣题目解析

  • answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

其中:

  • x1 = max(0,i - k) + 1y1 = max(0,j - k) + 1x2 = min(i + k,m - 1) + 1y2 = min(j + k,n - 1) + 1

另外一定要注意下标的映射关系。

3️⃣解题代码

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] + mat[i - 1][j - 1] - dp[i - 1][j - 1];// 使用前缀和矩阵vector<vector<int>> answer(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,x2 = min(i + k,m - 1) + 1,y2 = min(j + k,n - 1) + 1;answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];}return answer;}
};

最后就通过啦!!!

相关文章:

【算法|前缀和系列No.5】leetcode1314. 矩阵区域和

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

python知识:从PDF 提取文本

一、说明 PDF 到文本提取是自然语言处理和数据分析中的一项基本任务&#xff0c;它允许研究人员和数据分析师从 PDF 文件中包含的非结构化文本数据中获得见解。Python 是一种通用且广泛使用的编程语言&#xff0c;它提供了多个库和工具来促进提取过程。 二、各种PDF操作库 让我…...

基于MATLAB的GPS卫星绕地运行轨迹动态模拟仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 Prn NavData(PRNS_SEL,1);%识别导航数据中的PRNiode NavData(PRNS_SEL,11);%企…...

TCP/IP模型五层协议

TCP/IP模型五层协议 认识协议 约定双方进行的一种约定 协议分层 降低了学习和维护的成本&#xff08;封装&#xff09;灵活的针对这里的某一层协议进行替换 四/五层协议 五层协议的作用 应用层 应用层常见协议 应用层常见协议概览 基于TCP的协议 HTTP&#xff08;超…...

vue 插槽 - 具名插槽

vue 插槽 - 具名插槽 **创建 工程&#xff1a; H:\java_work\java_springboot\vue_study ctrl按住不放 右键 悬着 powershell H:\java_work\java_springboot\js_study\Vue2_3入门到实战-配套资料\01-随堂代码素材\day05\准备代码\09-插槽-具名插槽 vue --version vue create…...

Elasticsearch2.x Doc values

文档地址&#xff1a; https://www.elastic.co/guide/en/elasticsearch/reference/2.4/doc-values.html https://www.elastic.co/guide/en/elasticsearch/guide/2.x/docvalues-intro.html https://www.elastic.co/guide/en/elasticsearch/guide/2.x/docvalues.html https://ww…...

Squeeze-and-Attention Networks for Semantic Segmentation

0.摘要 最近&#xff0c;将注意力机制整合到分割网络中可以通过更重视提供更多信息的特征来提高它们的表征能力。然而&#xff0c;这些注意力机制忽视了语义分割的一个隐含子任务&#xff0c;并受到卷积核的网格结构的限制。在本文中&#xff0c;我们提出了一种新颖的squeeze-a…...

【Java】Java 11 新特性概览

Java 11 新特性概览 1. Java 11 简介2. Java 11 新特性2.1 HTTP Client 标准化2.2 String 新增方法&#xff08;1&#xff09;str.isBlank() - 判断字符串是否为空&#xff08;2&#xff09;str.lines() - 返回由行终止符划分的字符串集合&#xff08;3&#xff09;str.repeat(…...

用Vue3.0 写过组件吗?如果想实现一个 Modal你会怎么设计?

一、组件设计 组件就是把图形、非图形的各种逻辑均抽象为一个统一的概念&#xff08;组件&#xff09;来实现开发的模式 现在有一个场景&#xff0c;点击新增与编辑都弹框出来进行填写&#xff0c;功能上大同小异&#xff0c;可能只是标题内容或者是显示的主体内容稍微不同 …...

ArmSoM-W3之RK3588硬编解码MPP环境配置

1. 简介 瑞芯微提供的媒体处理软件平台&#xff08;Media Process Platform&#xff0c;简称 MPP&#xff09;是适用于瑞芯微芯片系列的 通用媒体处理软件平台。该平台对应用软件屏蔽了芯片相关的复杂底层处理&#xff0c;其目的是为了屏蔽不 同芯片的差异&#xff0c;为使用者…...

源码解析flink文件连接源TextInputFormat

背景&#xff1a; kafka的文件系统数据源可以支持精准一次的一致性,本文就从源码看下如何TextInputFormat如何支持状态的精准一致性 TextInputFormat源码解析 首先flink会把输入的文件进行切分&#xff0c;分成多个数据块的形式&#xff0c;每个数据源算子任务会被分配以读取…...

SQL ORDER BY Keyword(按关键字排序)

SQL ORDER BY 关键字 ORDER BY 关键字用于按升序或降序对结果集进行排序。 ORDER BY 关键字默认情况下按升序排序记录。 如果需要按降序对记录进行排序&#xff0c;可以使用DESC关键字。 SQL ORDER BY 语法 SELECT column1, column2, ... FROM table_name ORDER BY column1, …...

光伏三相并网逆变器的控制策略与性能分析(Simulink仿真实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【网络安全 --- xss-labs靶场】xss-labs靶场安装详细教程,让你巩固对xss漏洞的理解及绕过技巧和方法(提供资源)

一&#xff0c;资源下载准备 1-1 VMware 16.0 安装请参考以下博客&#xff0c;若已经安装请忽略&#xff1a; 【网络安全 --- 工具安装】VMware 16.0 详细安装过程&#xff08;提供资源&#xff09;-CSDN博客【网络安全 --- 工具安装】VMware 16.0 详细安装过程&#xff08;…...

蓝桥每日一题(day 3: 蓝桥587.约数个数)--数学--easy

题目 解题核心&#xff1a; 分解质因数&#xff0c;每个质因数的次方1的累乘积就是anscode #include <iostream> #include<algorithm> #include<unordered_map> //# #include<> typedef long long LL; const int N 110, MOD 1e9 7;using namespac…...

深入剖析Java类加载过程:探寻类加载器的奥秘

摘要: 一个java文件从被加载到被卸载这个生命过程&#xff0c;总共要经历4个阶段&#xff1a; 加载->链接&#xff08;验证准备解析&#xff09;->初始化&#xff08;使用前的准备&#xff09;->使用->卸载 其中类加载过程包括加载、验证、准备、解析和初始化五个阶…...

PHP yield

概念&#xff1a; Generator&#xff1a;带 yield的function yield&#xff1a;Generator或task的中断关键字&#xff0c;执行到yield时一次调度周期执行完即阻塞&#xff0c;并返回右侧表达式结果&#xff0c;等待下一次调度器运行next()或迭代遍历才会继续往下执行&#xff0…...

react antd实现upload上传文件前form校验,同时请求带data

最近的需求&#xff0c;两个下拉框是必填项&#xff0c;点击上传按钮&#xff0c;如果有下拉框没选要有提示&#xff0c;如图 如果直接使用antd的Upload组件&#xff0c;一点击文件选择的窗口就打开了&#xff0c;哪怕在Button里再加点击事件&#xff0c;也只是&#xff08;几乎…...

echars 设置滚动条演示,

dataZoom: [// 滑动条{zoomLock:true,xAxisIndex: 0, // 这里是从X轴的0刻度开始type: "slider", // 这个 dataZoom 组件是 slider 型 dataZoom 组件startValue: 0, // 从头开始。endValue: 20, // 一次性展示几个。// fillerColor: "#023661", // 选中范围…...

代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离

代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离 文章目录 代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离[toc]583.两个字符串的删除操作求公共部分长度&#xff1a;即最长公共子串 72. 编辑距离 583.两个字符串的删除操作…...

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

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

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...