矩阵区域和 ---- 二维前缀和

news/2024/7/22 13:24:37/文章来源:https://blog.csdn.net/m0_73992740/article/details/139235446

题目链接

题目:

分析:

  • 题目的题意是:
  • 矩阵和的问题, 应该使用二维前缀和来解决 
  • 先预处理一个前缀和, 但是题目中下标是从0开始的, 为了不处理边界情况, 我么预处理出来的矩阵, 要从下标为1的位置开始, 所以前缀和矩阵的大小为m+1 * n+1
  • 预处理前缀和:
    dp[i][j] 表示: 从[1,1] 位置到[i,j] 位置, 这段区间里面所有元素的和

    dp[i][j] 就等于A+B+C+D, A好求, 就是dp[i-1][j-1], 但BC不好求, 所以我们AB一起求,AC一起求
    但是前缀和数组和原数组下标不对应, 所以arr[i][j] 应该对应 arr[i-1][j-1]
  •  计算区间的面积, 假设是红色区域


    所以我们只需要直到要求面积的左上下标x1y1 右下下标x2y2 即可

  • 计算x1应该等于i-k, 但是如果越界, 只能按0算, 所以应该取i-k和0的最大值, y2同理
    计算x1应该等于i+k, 但是如果越界, 只能按m-1算, 所以应该取i+k和m-1的最小值, y2同理

  • 使用前缀和数组, 需要重新创建一个矩阵ret, 存放结果, 大小为m * n, 和前缀和矩阵又不对应, x1y1x2y2对应的是前缀和的下标, 那么带入结果时, 只需要每个+1即可, 即
     int x1 = Math.max(0, i - k) + 1;
     int y1 = Math.max(0, j - k) + 1;
     int x2 = Math.min(m - 1, i + k) + 1;
     int y2 = Math.min(n - 1, j + k) + 1;

代码:

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length;int n = mat[0].length;int[][] dp = new int[m + 1][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];}}int[][] ret = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int x1 = Math.max(0, i - k) + 1;int y1 = Math.max(0, j - k) + 1;int x2 = Math.min(m - 1, i + k) + 1;int y2 = Math.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.luyixian.cn/news_show_1052473.aspx

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

相关文章

React 其他 Hooks

其他 Hooks useRef 可用于获取 DOM 元素 const ScrollRef useRef(null)ScrollRef.current useContext &#xff08;先回顾一下之前的 Context 知识&#xff0c;借用之前 ppt 和源码&#xff09; Hooks 中使用 useContext 来获取 context 的值 // 父组件创建 contextexpor…

使用YOLOv9训练和测试自己的数据集

任务&#xff1a;检测舌头上的裂纹和齿痕 已经有了labelme标注的数据集&#xff0c;并且转为了coco格式 参考&#xff1a; 详细&#xff01;正确&#xff01;COCO数据集&#xff08;.json&#xff09;训练格式转换成YOLO格式&#xff08;.txt&#xff09;_coco数据集的train…

多态(难的起飞)

注意 virtual关键字&#xff1a; 1、可以修饰原函数&#xff0c;为了完成虚函数的重写&#xff0c;满足多态的条件之一 2、可以菱形继承中&#xff0c;去完成虚继承&#xff0c;解决数据冗余和二义性 两个地方使用了同一个关键字&#xff0c;但是它们互相一点关系都没有 虚函…

Python | Leetcode Python题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; class Solution:def connect(self, root: Node) -> Node:if not root:return root# 从根节点开始leftmost rootwhile leftmost.left:# 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next 指针head leftmostwhile head:#…

JVM-之GC日志

一、 开启gc 日志 在项目中开启GC 日志打印后会查看gc 日志如下 nohup java -Xms768m -Xmx768m -XX:HeapDumpOnOutOfMemoryError -XX:HeapDumpPath./dumplog/dumplog.log -Xloggc:./dumplog/gc.log -XX:PrintGCDetails -XX:PrintGCDateStamps -XX:PrintHeapAtGC -jar xxxx…

PPT大珩助手新功能-生成迷宫

大珩助手是一款功能丰富的办公软件插件&#xff0c;它主要分为两个版本&#xff1a;PPT大珩助手和Word大珩助手。这两个版本都旨在提高用户在处理演示文稿和文档时的效率。 PPT大珩助手 这是一款专门为Microsoft PowerPoint设计的插件。它提供了多种功能&#xff0c;例如素材…

CSS学习笔记:flex布局(弹性布局)

设置flex布局 父元素添加display: flex 使用justify-content调节元素在主轴的对齐方式 给父元素添加justify-content属性&#xff0c;取值如下 用于调节子元素在主轴方向&#xff08;水平方向&#xff09;的对齐方式 使用align-items调节元素在侧轴的对齐方式 给父元素添加…

卸载/删除 Maxask.com,最简单的方法

被绑架的浏览器&#xff0c;太恶心了。 Maxask伪装成了插件&#xff0c;在你搜索网页的时候利用了重定向&#xff0c;导致出现的界面时Maxask的界面&#xff0c;很恶心。 只需要排查正在使用的&#xff0c;如下图有颜色的图表。 删除一个插件&#xff0c;浏览器搜索一下看看有…

数据结构——红黑树

红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但是在每个结点上会多出一个存储位来表示结点的颜色&#xff0c;可以是红色(RED)或者黑色(BLACK),通过任何一条根到叶子的路径上各个结点着色方式的限制&#xff0c;确保红黑树没有一条路径会比其他路径长出两倍&…

前端开发工程师——数据可视化

canvas canvas绘制线段 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthd…

Web安全:SQL注入之时间盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…

Golang | Leetcode Golang题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; func connect(root *Node) *Node {if root nil {return root}// 每次循环从该层的最左侧节点开始for leftmost : root; leftmost.Left ! nil; leftmost leftmost.Left {// 通过 Next 遍历这一层节点&#xff0c;为下一层的节点更新 Next …

帝国CMS验证码不显示怎么回事呢?

帝国CMS验证码有时候会不显示或打叉&#xff0c;总结自己的解决方法。 1、检查服务器是否开启GD库 测试GD库是否开启的方法&#xff1a;浏览器访问&#xff1a;/e/showkey/index.php&#xff0c;如果出现一堆乱码或报错&#xff0c;证明GD库没有开启&#xff0c;开启即可。 2…

深度学习-转置卷积

转置卷积 转置卷积&#xff08;Transposed Convolution&#xff09;&#xff0c;也被称为反卷积&#xff08;Deconvolution&#xff09;&#xff0c;是深度学习中的一种操作&#xff0c;特别是在卷积神经网络&#xff08;CNN&#xff09;中。它可以将一个低维度的特征图&#x…

echarts学习篇

一、使用echarts 1.引入 Apache ECharts <!DOCTYPE html> <html> <head> <meta charset"utf-8" /> <!-- 引入刚刚下载的 ECharts 文件 --> <script src"echarts.js"></script> </head> </html> 2.…

数据结构---链表

1、链表分类 对于链表可以分为几种&#xff0c;不同的分类对应不同的应用场景&#xff0c;其中&#xff0c;双向循环链表和单向链表最常用。 1.1链表按照有头无头分类 也就是说有无哨兵位&#xff0c;哨兵位&#xff0c;是一个开辟的空间&#xff0c;但是不放置数据&#xf…

AURIX TC3xx单片机介绍-启动过程介绍1

从各个域控制器硬件解决方案来看,MPU可能来自多个供应商,有瑞萨,有NXP等,但对于MCU来说,基本都采用英飞凌TC3xx。 今天我们就来看一下TC3xx的启动过程,主要包含如下内容: uC上电过程中,会经过一个上电时序,从复位状态“脱离”出来;Boot Firmware是复位后第一个执行的…

金职优学:分析央国企面试如何通关?

在当今竞争激烈的就业市场中&#xff0c;中央和国有企业&#xff08;以下简称“央国企”&#xff09;的面试机会对求职者来说是非常有吸引力的。这些企业通常拥有稳定的发展前景、良好的薪酬福利和广阔的职业发展空间。但是&#xff0c;要想成功通过央国企的面试&#xff0c;求…

YOLOv8+PyQt5西红柿成熟度检测系统完整资源集合(yolov8模型,从图像、视频和摄像头三种路径识别检测,包含登陆页面、注册页面和检测页面)

西红柿成熟度检测&#xff08;https://mbd.pub/o/bread/mbd-ZpWbk5ly&#xff09;_哔哩哔哩_bilibili 资源包含可视化的西红柿成熟度检测系统&#xff0c;基于最新的YOLOv8训练的西红柿成熟度检测模型&#xff0c;和基于PyQt5制作的可视化西红柿成熟度检测系统&#xff0c;包含…

加速模型训练 GPU cudnn

GPU的使用 在定义模型时&#xff0c;如果没有特定的GPU设置&#xff0c;会使用 torch.nn.DataParallel 将模型并行化&#xff0c;充分利用多GPU的性能&#xff0c;这在加速训练上有显著影响。 model torch.nn.DataParallel(model).cuda() cudnn 的配置&#xff1a; cudnn.…