前缀和(八)矩阵区域和

 1314. 矩阵区域和

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

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {// 1、初始化前缀和dp数组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前缀和数组定义为从[1,1]->[i,j]位置的和dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];// for(int i = 1; i <= m; i++)//     for(int j = 1; j <= n; j++)//         cout<<dp[i][j]<<" ";// 2、使用前缀和进行更新answervector<vector<int>> ans(m, vector<int> (n));int x1,y1,x2,y2;for(int i = 1; i <= m; i++){for(int j  = 1; j <= n; j++){x1 = i-k < 1 ? 1 : i-k;y1 = j-k < 1 ? 1 : j-k;x2 = i+k > m ? m : i+k;y2 = j+k > n ? n : j+k;ans[i-1][j-1] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];// cout<<ans[i-1][j-1];}}return ans;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

不一样的CSS(4)--icon图标系列之svg

序言 上一节内容我们讲解了如何利用css去画一个五角星&#xff0c;其中包括了使用svg的方法&#xff0c;有些小伙伴们对svg的使用不是很了解&#xff0c;那么本节内容我们主要来讲一下&#xff0c;关于svg标签的的使用。 目录 序言一、svg的介绍二、安装SVG扩展插件三、SVG基…

读取文件进度条

一、widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMenuBar> #include <QFileDialog> #include <QFile> #include <QDebug> #include <QTimer> QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NA…

js this

<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>this</title> </head> <body> <script>let fengfeng "枫枫"console.log(this)// alert("123")funct…

wordpress网站安装了Linux宝塔面板,限制IP地址访问网站,只能使用域名访问网站

一、Linux服务器安装Linux宝塔面板 这个步骤参考网上其他教程。 二、Linux宝塔面板部署wordpress网站 这个步骤参考网上其他教程&#xff0c;保证网站能够正常访问&#xff0c;并且使用Linux宝塔面板申请并部署了SSL证书&#xff0c;使用https协议默认443端口正常访问。 三…

软考高级架构-9.4.4-双机热备技术 与 服务器集群技术

一、双机热备 1、特点&#xff1a; 软硬件结合&#xff1a;系统由两台服务器&#xff08;主机和备机&#xff09;、一个共享存储&#xff08;通常为磁盘阵列柜&#xff09;、以及双机热备软件&#xff08;提供心跳检测、故障转移和资源管理功能的核心软件&#xff09;组成。 …

电子商务人工智能指南 1/6 - 搜索、广告和发现

介绍 81% 的零售业高管表示&#xff0c; AI 至少在其组织中发挥了中等至完全的作用。然而&#xff0c;78% 的受访零售业高管表示&#xff0c;很难跟上不断发展的 AI 格局。 近年来&#xff0c;电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…

论文 | EfficientRAG: Efficient Retriever for Multi-Hop Question Answering

1. 论文介绍与研究动机 本文提出了一个新的检索增强生成&#xff08;RAG&#xff09;方法——EfficientRAG&#xff0c;它专门用于解决复杂的多跳问题。在多跳问答中&#xff0c;问题的答案需要从多个信息源中检索并结合起来&#xff0c;远比单跳问题复杂&#xff0c;因此也更加…

超详细搭建PhpStorm+PhpStudy开发环境

刚开始接触PHP开发&#xff0c;搭建开发环境是第一步&#xff0c;网上下载PhpStorm和PhpStudy软件&#xff0c;怎样安装和激活就不详细说了&#xff0c;我们重点来看一看怎样搭配这两个开发环境。 前提&#xff1a;现在假设你已经安装完PhpStorm和PhpStudy软件。 我的PhpStor…

Linux U-Boot 启动流程详解

目录 一、引言 二、U-Boot 启动前的准备 三、U-Boot 的启动流程 1.第一阶段&#xff1a;SPL&#xff08;Secondary Program Loader&#xff09;启动 2.第二阶段&#xff1a;U-Boot 主程序初始化 3.第三阶段&#xff1a;内核加载 4.第四阶段&#xff1a;参数传递 5.第五阶…

[Redis#16] 事务 | vs Mysql | 命令 | WATCH的实现

目录 什么是事务 实现事务的方式 Redis 事务与 MySQL 事务的对比 应用场景&#xff1a;防止超卖 Lua 脚本增强 事务操作 MULTI & EXEC DISCARD WATCH WATCH 的实现原理 什么是事务 [MySQL#12] 事务(1) | ACID | commit | 回滚 | 常见操作 Redis 的事务和 MySQL…

day03-分析产品原型-课程

1. 开发流程 2. 分析产品原型 2.1 业务流程 产品原型图&#xff1a; 两个业务模块之间使用异步通信 2.2 查询课程列表-接口 https://apifox.com/apidoc/shared-3076deb7-ecde-4519-8e57-390d336aef4c 2.2.1 课表VO 前端课表的相关参数&#xff1a; 现在还不能一步到位&a…

电子商务人工智能指南 2/6 - 需求预测和库存管理

介绍 81% 的零售业高管表示&#xff0c; AI 至少在其组织中发挥了中等至完全的作用。然而&#xff0c;78% 的受访零售业高管表示&#xff0c;很难跟上不断发展的 AI 格局。 近年来&#xff0c;电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…

CANoe IG实现信号遍历

CANoe IG也可以实现信号遍历的功能&#xff0c;设置如下&#xff1a; 注意事项&#xff1a; 选择 Range of values&#xff0c;是实现信号设定值范围内&#xff08;6&#xff09;的遍历 Hold time 要设置成和周期一致&#xff0c;如果不一致&#xff0c;则信号变化和周期不一…

AI大模型驱动数据分析:利用自然语言实现数据查询与可视化(1)

在当今AI驱动的时代&#xff0c;数据分析已成为各行各业不可或缺的能力。然而&#xff0c;传统的数据分析流程通常需要掌握SQL、数据处理和可视化等多项专业技能&#xff0c;这对非技术背景的业务人员来说是一个不小的挑战。 想象一下&#xff0c;当数据中心的负责人打开手机时…

蓝桥杯训练15——穿越雷区

from collections import deque def bfs(leiqu): n len(leiqu) # 定义四个方向&#xff1a;右、下、左、上 directions[(0,1),(0,-1),(1,0),(-1,0)] # 初始化访问标记矩阵 visited [[False] * n for _ in range(n)] queue deque() #…

【STL】用一张哈希表封装unordered_set和unordered_map

哈希表源代码 这里是使用开散列实现的哈希表&#xff0c;为了和库里的哈希表进行区分&#xff0c;我将哈希表放入到了命名空间中 //确保取余运算符两边是正整数&#xff0c;下标不能是负整数 template<class K> struct DefaultHashFunc {size_t operator()(const K&…

搜索二维矩阵 II

搜索二维矩阵 II 编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9…

嵌入式入门Day24

数据结构Day5 树形结构相关概念二叉树相关概念二叉树的状态二叉树性质二叉树的存储二叉树根据已有序列推出树的结构练习 算法相关概念算法特性算法的设计要求时间复杂度排序算法冒泡排序&#xff08;改良版&#xff09;选择排序&#xff08;O(n^2)&#xff09;直接插入排序&…

百度网盘qzxing-master.zip

qzxing 这是一个针对 ZXing 条形码图像处理库的 Qt/QML 封装库。 支持以下类型的条形码解码&#xff1a; UPC-AUPC-EEAN-8EAN-13ITFCode 39Code 93Code 128&#xff08;GS1&#xff09;Codabar二维码数据矩阵Aztec&#xff08;测试版&#xff09;PDF 417 支持以下类型的条形…

Ping32与天锐绿盾加密软件对比:哪款防泄密软件适合您的企业?

企业数据泄漏事故层出不穷&#xff0c;为了有效防止机密信息的泄露&#xff0c;选择一款合适的防泄密软件显得尤为重要。Ping32和天锐绿盾加密软件都是市场上比较受欢迎的防泄密工具&#xff0c;那么它们各自的优势和差异是什么呢&#xff1f;让我们一起来了解。 1. 安全性&…