【算法|前缀和系列No.5】leetcode1314. 矩阵区域和
个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【Leetcode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
点击直接跳转到该题目
目录
- 1️⃣题目描述
- 2️⃣题目解析
- 3️⃣解题代码
1️⃣题目描述
给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:
i - k <= r <= i + kj - 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.lengthn == mat[i].length1 <= m, n, k <= 1001 <= 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) + 1、y1 = max(0,j - k) + 1、x2 = min(i + k,m - 1) + 1、y2 = 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. 矩阵区域和
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望…...
python知识:从PDF 提取文本
一、说明 PDF 到文本提取是自然语言处理和数据分析中的一项基本任务,它允许研究人员和数据分析师从 PDF 文件中包含的非结构化文本数据中获得见解。Python 是一种通用且广泛使用的编程语言,它提供了多个库和工具来促进提取过程。 二、各种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模型五层协议 认识协议 约定双方进行的一种约定 协议分层 降低了学习和维护的成本(封装)灵活的针对这里的某一层协议进行替换 四/五层协议 五层协议的作用 应用层 应用层常见协议 应用层常见协议概览 基于TCP的协议 HTTP(超…...
vue 插槽 - 具名插槽
vue 插槽 - 具名插槽 **创建 工程: 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
文档地址: 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.摘要 最近,将注意力机制整合到分割网络中可以通过更重视提供更多信息的特征来提高它们的表征能力。然而,这些注意力机制忽视了语义分割的一个隐含子任务,并受到卷积核的网格结构的限制。在本文中,我们提出了一种新颖的squeeze-a…...
【Java】Java 11 新特性概览
Java 11 新特性概览 1. Java 11 简介2. Java 11 新特性2.1 HTTP Client 标准化2.2 String 新增方法(1)str.isBlank() - 判断字符串是否为空(2)str.lines() - 返回由行终止符划分的字符串集合(3)str.repeat(…...
用Vue3.0 写过组件吗?如果想实现一个 Modal你会怎么设计?
一、组件设计 组件就是把图形、非图形的各种逻辑均抽象为一个统一的概念(组件)来实现开发的模式 现在有一个场景,点击新增与编辑都弹框出来进行填写,功能上大同小异,可能只是标题内容或者是显示的主体内容稍微不同 …...
ArmSoM-W3之RK3588硬编解码MPP环境配置
1. 简介 瑞芯微提供的媒体处理软件平台(Media Process Platform,简称 MPP)是适用于瑞芯微芯片系列的 通用媒体处理软件平台。该平台对应用软件屏蔽了芯片相关的复杂底层处理,其目的是为了屏蔽不 同芯片的差异,为使用者…...
源码解析flink文件连接源TextInputFormat
背景: kafka的文件系统数据源可以支持精准一次的一致性,本文就从源码看下如何TextInputFormat如何支持状态的精准一致性 TextInputFormat源码解析 首先flink会把输入的文件进行切分,分成多个数据块的形式,每个数据源算子任务会被分配以读取…...
SQL ORDER BY Keyword(按关键字排序)
SQL ORDER BY 关键字 ORDER BY 关键字用于按升序或降序对结果集进行排序。 ORDER BY 关键字默认情况下按升序排序记录。 如果需要按降序对记录进行排序,可以使用DESC关键字。 SQL ORDER BY 语法 SELECT column1, column2, ... FROM table_name ORDER BY column1, …...
光伏三相并网逆变器的控制策略与性能分析(Simulink仿真实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
【网络安全 --- xss-labs靶场】xss-labs靶场安装详细教程,让你巩固对xss漏洞的理解及绕过技巧和方法(提供资源)
一,资源下载准备 1-1 VMware 16.0 安装请参考以下博客,若已经安装请忽略: 【网络安全 --- 工具安装】VMware 16.0 详细安装过程(提供资源)-CSDN博客【网络安全 --- 工具安装】VMware 16.0 详细安装过程(…...
蓝桥每日一题(day 3: 蓝桥587.约数个数)--数学--easy
题目 解题核心: 分解质因数,每个质因数的次方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文件从被加载到被卸载这个生命过程,总共要经历4个阶段: 加载->链接(验证准备解析)->初始化(使用前的准备)->使用->卸载 其中类加载过程包括加载、验证、准备、解析和初始化五个阶…...
PHP yield
概念: Generator:带 yield的function yield:Generator或task的中断关键字,执行到yield时一次调度周期执行完即阻塞,并返回右侧表达式结果,等待下一次调度器运行next()或迭代遍历才会继续往下执行࿰…...
react antd实现upload上传文件前form校验,同时请求带data
最近的需求,两个下拉框是必填项,点击上传按钮,如果有下拉框没选要有提示,如图 如果直接使用antd的Upload组件,一点击文件选择的窗口就打开了,哪怕在Button里再加点击事件,也只是(几乎…...
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.两个字符串的删除操作求公共部分长度:即最长公共子串 72. 编辑距离 583.两个字符串的删除操作…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
