【C++算法】32.前缀和_矩阵区域和
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
题目链接:
1314. 矩阵区域和
题目描述:

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

二维前缀和思想:
使用前缀和矩阵

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]?

这里要注意:是坐标,不是坐标系。
如果是(0,0)的话,比0小的都要舍掉。同理,比结尾大的也要舍掉。
我们可以处理一下:

m,n为边界。
还需要注意下标的映射关系。

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

从dp里面找(x,y)的时候,要(x-1,y-1)才是mat里面的前缀和
从answer里面找(x,y)的时候,要(x+1,y+1)才是dp里面的前缀和
所以我们要么改矩阵的面积公式,要么在这里改:

这样求到的就是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;}
};
相关文章:
【C++算法】32.前缀和_矩阵区域和
文章目录 题目链接:题目描述:解法C 算法代码: 题目链接: 1314. 矩阵区域和 题目描述: 解法 防止有人看不明白题目,先解释一下题目 二维前缀和思想: 使用前缀和矩阵 ret [x1,y1]~[x2,y2] D …...
使用堆栈(Stack)
集合类型(Collection)下篇_xml collection-CSDN博客 以上是堆栈的简单介绍,下方是堆栈的使用 题目:给定一个逆波兰表达式(后缀表达式)的字符串数组tokens,其中每个元素是一个操作数(数字&…...
雨晨 2610(2)0.2510 Windows 11 24H2 Iot 企业版 LTSC 2024 极简 2in1
文件: 雨晨 2610(2)0.2510 Windows 11 24H2 Iot 企业版 LTSC 2024 极简 2in1 install.esd 索引: 1 名称: Windows 11 IoT 企业版 LTSC 极简 26100.2510 描述: Windows 11 IoT 企业版 LTSC 极简 26100.2510 By YCDISM RTM 2025 24-12-07 大小: 8,176,452,990 个字节 索引: 2 …...
HDD 2025年技术趋势深度分析报告
随着数据量的指数级增长以及人工智能(AI)、物联网(IoT)、云计算和视频监控等领域的需求激增,硬盘驱动器(HDD)行业正面临着前所未有的挑战与机遇。本报告旨在深入剖析2025年HDD技术的发展方向&am…...
算法-字符串-22.括号生成
一、题目 二、思路解析 1.思路: 生成所有可能并且有效的括号组合——回溯方法 2.常用方法: a.数组,因为需要增删元素,所以选择LinkedList LinkedList<String> resnew LinkedList<>(); b.StringBuilder创建࿰…...
Free-RTOS实现LED闪烁
开发板:正点原子探索者 F407 LED定时定时闪烁 本次实验验证: 配置文件 1、打开CubeMX 2、选择芯片型号,然后点击开始项目 3、配置时钟 配置烧录引脚,与FreeRTOS系统时钟 选择FreeRTOS 这里已经默认有一个任务ÿ…...
NLP论文速读(斯坦福大学)|使用Tree将语法隐藏到Transformer语言模型中正则化
论文速读|Sneaking Syntax into Transformer Language Models with Tree Regularization 论文信息: 简介: 本文的背景是基于人类语言理解的组合性特征,即语言处理本质上是层次化的:语法规则将词级别的意义组合成更大的成分的意义&…...
再谈多重签名与 MPC
目录 什么是 MPC 钱包以及它们是如何出现的 多重签名和智能合约钱包已经成熟 超越 MPC 钱包 关于小队 多重签名已经成为加密货币领域的一部分,但近年来,随着 MPC(多方计算)钱包的出现,多重签名似乎被掩盖了。MPC 钱包之…...
CTF学习24.11.19[音频隐写]
MISC07[音频隐写] 隐写术 隐写术是一门关于信息隐藏的技巧与科学,所谓信息隐藏指的是不让除预期的接收者之外的任何人知晓信息的传递事件或者信息的内容。隐写术的英文叫做Steganography,来源于特里特米乌斯的一本讲述密码学与隐写术的著作Steganograp…...
vue的watch是否可以取消? 怎么取消?
发现宝藏 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。【宝藏入口】。 Vue 可以通过 watch API 返回的一个 取消函数,可以在需要时取消该监听。 如何取消 watch? 当你使用 Vu…...
23、枚举
1、枚举 罗列一些标识符,当做整型数据使用。为了代码的易读性 1.1、枚举定义 enum 枚举名{大写标识符,大写标识符....}; 枚举类型名:enum 枚举名 枚举里面如果不给标识符赋值,默认从0开始,依次增1 如果里面的标识符有赋值…...
Java基本概念
Java特点 简单性。容易使用,比如没有C复杂的指针 面向对象。将对象属性剥离,当属性需要大量调用时节省代码,比如把大象装进冰箱,JAVA将大象分成跑、睡觉等不同功能,当需要就调用 分布式。 健壮性 安全性 体系结构…...
C++学习——如何析构派生类
C——继承关系中的虚函数 析构派生类纯虚构函数和抽象类 析构派生类 先看一段简单的代码: #include <iostream>using namespace std;class AA { public:AA() {cout << "调用了基类构造" << endl;}virtual void func() {cout <<…...
SpringCloud与Dubbo的区别
在构建分布式系统时,SpringCloud和Dubbo是两个常用的框架。虽然它们都能帮助开发者实现服务之间的通信和治理,但在设计理念、使用场景和技术实现上,两者存在明显的区别。本文将详细探讨SpringCloud与Dubbo的不同之处,以帮助开发者…...
C# 设计模式--建造者模式 (Builder Pattern)
定义 建造者模式是一种创建型设计模式,它允许你逐步构建复杂对象,而无需使用多个构造函数或重载。建造者模式将对象的构建过程与表示分离,使得相同的构建过程可以创建不同的表示。 正确写法 假设我们有一个复杂的 Car 对象,需要…...
leetcode 23. 合并 K 个升序链表
给你一个链表数组,每个链表都已经按升序排列。 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [1->4->5,1->3->4,2->6 ] 将它们合并到一个有序链表中得到。 1->…...
【Redis】深入解析Redis缓存机制:全面掌握缓存更新、穿透、雪崩与击穿的终极指南
文章目录 一、Redis缓存机制概述1.1 Redis缓存的基本原理1.2 常见的Redis缓存应用场景 二、缓存更新机制2.1 缓存更新的策略2.2 示例代码:主动更新缓存 三、缓存穿透3.1 缓存穿透的原因3.2 缓解缓存穿透的方法3.3 示例代码:使用布隆过滤器 四、缓存雪崩4…...
SQL语法——DQL查询
1.查询: 基础查询: select 列名1,列名2 from 表名; # 输入列名为*时为全查 条件查询: select 列名 from 表名 where 条件; #条件中含字符串时为字符串...
云计算.运维.面试题
1、计算机能直接识别的语言( C )。 A、汇编语言 B、自然语言 C、机器语言 D、高级语言 2、应用软件是指( D )。 A、所有能够使用的软件 B、能被各应用单位共同使用的某种软件 C、所有计算机上都应使用的基本软件D、专门为某一应用目的而编制的软件 3、计算机的显示器是一…...
基于vue和vite的计算器
实现思路:1.撰写方案三次迭代(得到方案、项目结构、提问的prompt) 2. 功能实现 3. 优化迭代 计算器项目方案设计(阶段一) 一、项目基本信息 项目名称:基于 Vue 和 Vite 的计算器项目 技术栈: 前…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
