【C++算法】32.前缀和_矩阵区域和

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:


题目链接:

1314. 矩阵区域和


题目描述:

decc7f6a3b3fe63df13a15491690ed86


解法

防止有人看不明白题目,先解释一下题目

e0c5519d6ad0b102dbf0fc432598de35

二维前缀和思想:

使用前缀和矩阵

ret = [x1,y1]~[x2,y2]

= D

= (A+B+C+D)-(A+B)-(A+C)+A

= dp[x2,y2]-dp[x1-1,y2]-dp[x2,y1-1]+dp[x1-1,y1-1]

重要的是怎么找到坐标answer[i][j]

b51872f5f086a410383e9bbd0b954157

这里要注意:是坐标,不是坐标系。

如果是(0,0)的话,比0小的都要舍掉。同理,比结尾大的也要舍掉。

我们可以处理一下:

a24e1df7fea0b926df4d2b85c81736eb

m,n为边界。

还需要注意下标的映射关系。

1d82daaab5fd2d21d9be1878eecb6d35

ma矩阵是以(0,0)开始的,前缀和dp矩阵是以(1,1)开始的。

6ca737f4671d0559511a25969611aff1

dp里面找(x,y)的时候,要(x-1,y-1)才是mat里面的前缀和

answer里面找(x,y)的时候,要(x+1,y+1)才是dp里面的前缀和

所以我们要么改矩阵的面积公式,要么在这里改:

eba9253b8f9a8c06f70797a7eadb4450

这样求到的就是dp表里面的坐标了。

前缀和矩阵 dp[i][j] 表示 mat 中从 (0,0)(i-1,j-1) 矩形区域内的元素之和。

下面的结果矩阵ret就是answer


C++ 算法代码:

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));// 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];// 2. 使用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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/486047.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】树和森林

树的存储结构 双亲表示法 定义结构数组&#xff0c;存放树的结点&#xff0c;每个结点含两个域&#xff1a; ​ 数据域&#xff1a;存放结点信息 ​ 双亲域&#xff1a;指示结点的双亲结点在数组中的位置 typedef struct PTNode{TElemType data;int parent; }PTNode;#defi…

Thonny IDE + MicroPython + ESP32 + GY-302 测量环境中的光照强度

GY-302是一款基于BH1750FVI光照强度传感器芯片的模块。该模块能够直接测量出环境中的光照强度&#xff0c;并将光照强度转换为数字信号输出。其具体参数如下表所示。 参数名称 参数特性 测量范围 0-65535 LX 测量精度 在环境光下误差小于20%&#xff0c;能够自动忽略50/60…

智创 AI 新视界 -- AI 时代的数据隐私保护挑战与应对(16 - 3)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

网上图书购物管理系统|Java|SSM|VUE| 前后端分离

【一】可以提供远程部署安装&#xff0c;包扩环境 【二】提供软件相关的安装包 【三】如果需要提供java入门资料可咨询 【技术栈】 1⃣️&#xff1a;架构: B/S、MVC 2⃣️&#xff1a;系统环境&#xff1a;Windowsh/Mac 3⃣️&#xff1a;开发环境&#xff1a;IDEA、JDK1.8、M…

双子气膜:科技与艺术的璀璨交融—轻空间

在城市的繁华一隅&#xff0c;即将崛起一座令人叹为观止的未来地标——双子气膜项目。这是由轻空间与国内知名企业强强联手打造的全新气膜球幕建筑&#xff0c;集合了尖端科技与视觉艺术&#xff0c;成为现代建筑领域的一次创意突破。 双子气膜&#xff1a;双球对称的震撼设计…

【全面】上市公司企业能源消耗数据(水、电、汽油、天然气、钢材等)2008-2022年

一、数据范围&#xff1a;包括水、电、汽油、天然气、钢材等3000多类能源&#xff0c;1.4万个样本。 二、资源类型&#xff1a;电 水 人均用电 人均用水 公务用车汽油 办公用水 办公用电 总行物业管理大楼办公用水 总…

双绞线直连两台电脑的方法及遇到的问题

文章目录 前言一、步骤二、问题总结&#xff1a;问题1:遇到ping不通的问题。问题2:访问其他电脑上的共享文件时提示输入网络凭证问题3:局域网共享文件时提示“没有权限访问&#xff0c;请与网络管理员联系请求访问权限” 前言 办公室里有两台电脑&#xff0c;一台装了显卡用于…

windows文件下换行, linux上不换行 解决CR换行符替换为LF notepad++

html文件是用回车换行的&#xff0c;在windows电脑上&#xff0c;显示正常。 文件上传到linux服务器后&#xff0c;文件不换行了。只有一行。而且相关js插件也没法正常运行。 用notepad查看&#xff0c;显示尾部换行符&#xff0c;是CR&#xff0c;这就是原因。CR是不被识别的。…

Android -- [SelfView] 自定义多行歌词滚动显示器

Android – [SelfView] 自定义多行歌词滚动显示器 流畅、丝滑的滚动歌词控件* 1. 背景透明&#xff1b;* 2. 外部可控制进度变化&#xff1b;* 3. 支持屏幕拖动调节进度&#xff08;回调给外部&#xff09;&#xff1b;效果 歌词文件&#xff08;.lrc&#xff09; 一. 使用…

Android APP自学笔记

摘抄于大学期间记录在QQ空间的一篇自学笔记&#xff0c;当前清理空间&#xff0c;本来想直接删除掉的&#xff0c;但是感觉有些舍不得&#xff0c;因此先搬移过来。 Android导入已有外部数据库 2015.06.26在QQ空间记录&#xff1a;在Android中不能直接打开res aw目录中的数据…

python进阶-05-利用Selenium来实现动态爬虫

python进阶-05-利用Selenium来实现动态爬虫 一.说明 这是python进阶部分05&#xff0c;我们上一篇文章学习了Scrapy来爬取网站&#xff0c;但是很多网站需要登录才能爬取有用的信息&#xff0c;或者网站的静态部分是一个空壳&#xff0c;内容是js动态加载的,或者人机验证&…

网安瞭望台第10期:开源机器学习框架存在漏洞、GammaDrop 恶意软件

研究人员发现流行开源机器学习框架存在漏洞 网络安全研究人员披露了多个影响开源机器学习&#xff08;ML&#xff09;工具和框架&#xff08;如 MLflow、H2O、PyTorch 和 MLeap&#xff09;的安全漏洞&#xff0c;这些漏洞可能导致代码执行。这些漏洞由 JFrog 发现&#xff0c;…

Onchain 正在蚕食 Offchain

目录 未来在链上 价值创造 技术加速 机构采用 小队&#xff1a;加速链上经济 我们正在进入一个代码就是货币、信任被编程、全球接入打破传统经济界限的时代。这种新兴模式就是我们所说的链上经济。 在此领域&#xff0c;Solana 因其在基础设施和应用程序方面的持续创新而脱颖而…

brpc的二次封装以及brpc与etcd的联合

目的&#xff1a; 搭配etcd的注册中心管理能知道谁能提供什么服务&#xff0c;并用rpc进行服务调用 封装思想&#xff1a; 信道管理&#xff0c;将不同服务主机的通信信道管理起来 封装&#xff1a; 1.指定的信道管理类 一个服务通常会有多个节点&#xff0c;每个节点都会…

Adminer源码编译 精简语言中英文和基本使用方法

Adminer是一个小而强悍的基于web的数据库管理工具&#xff0c; 官方默认支持几十种语言&#xff0c;但是对于中国的用户而言只需要有中文和英文就够了&#xff0c;其他语言基本无用。这就需要我们下载Adminer源码自己编译 Adminer.php , 如下图所示 adminer 中英文语言精简版本…

OpenStack-Glance组件

Glance Glance使用磁盘格式和容器格式基础配置镜像转换 Glance 是 OpenStack 的镜像服务&#xff0c;负责存储、发现和管理虚拟机镜像。它允许用户创建和共享镜像&#xff0c;用于启动虚拟机实例。 Glance 的主要功能 &#xff08;1&#xff09;虚拟机镜像的管理 支持镜像的上…

Leetcode 每日一题 56.合并区间

目录 问题描述 示例 示例 1 示例 2 问题分析 算法设计 步骤 1&#xff1a;排序 步骤 2&#xff1a;合并区间 步骤 3&#xff1a;返回结果 过题图片 代码实现 复杂度分析 题目链接 结语 问题描述 给定一个区间数组 intervals&#xff0c;其中每个区间由两个整数 s…

Oceanbase离线集群部署

准备工作 两台服务器 服务器的配置参照官网要求来 服务器名配置服务器IPoceanbase116g8h192.168.10.239oceanbase216g8h192.168.10.239 这里选oceanbase1作为 obd机器 oceanbase安装包 选择社区版本的时候自己系统的安装包 ntp时间同步rpm包 联网机器下载所需的软件包 …

Bert的Transformer原理

多义词如何应对&#xff1a; 答&#xff1a;通过Self attention&#xff0c;不同的上下文&#xff0c;对同一个"苹果"&#xff0c;得到截然不同的embedding激活值&#xff1b; Multi-head的作用&#xff1a; 有些类似CNN里用的多个卷积核得到多个Channel的特征图&…

AIDD-人工智能药物设计-化学自然语言引导的扩散式类药分子编辑:DiffIUPAC的魔法之旅

J. Pharm. Anal. | 化学自然语言引导的扩散式类药分子编辑&#xff1a;DiffIUPAC的魔法之旅 AIDD药研. 制药工程和生命科学背景&#xff0c;重点关注于计算机辅助药物设计&#xff08;CADD&#xff09;/药物筛选、分子动力学模拟MD&#xff0c;兽药信息学VetInformatics&…