LeetCode 2906. 构造乘积矩阵【前后缀分解,数组】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
给你一个下标从 0 开始、大小为 n * m
的二维整数矩阵 grid
,定义一个下标从 0 开始、大小为 n * m
的的二维矩阵 p
。如果满足以下条件,则称 p
为 grid
的 乘积矩阵 :
- 对于每个元素
p[i][j]
,它的值等于除了grid[i][j]
外所有元素的乘积。乘积对12345
取余数。
返回 grid
的乘积矩阵。
示例 1:
输入:grid = [[1,2],[3,4]]
输出:[[24,12],[8,6]]
解释:p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。
示例 2:
输入:grid = [[12345],[2],[1]]
输出:[[2],[0],[0]]
解释:p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ,所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ,所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。
提示:
1 <= n == grid.length <= 10^5
1 <= m == grid[i].length <= 10^5
2 <= n * m <= 10^5
1 <= grid[i][j] <= 10^9
前后缀分解(右边的数字为难度分)
- 238. 除自身以外数组的乘积 和本题几乎一样
- 剑指Offer66. 构建乘积数组 和本题几乎一样
- 2256. 最小平均差 1395
- 2483. 商店的最少代价 1495
- 2420. 找到所有好下标 1695
- 2167. 移除所有载有违禁货物车厢所需的最少时间 2219
- 2484. 统计回文子序列数目 2223
- 2565. 最少得分子序列 2432
- 2552. 统计上升四元组 2433
- 42. 接雨水
解法 前后缀分解
核心思想:把矩阵拉成一维的,我们需要算出每个数左边所有数的乘积,以及右边所有数的乘积,这都可以用递推得到。
先算出从 g r i d [ i ] [ j ] grid[i][j] grid[i][j] 的下一个元素开始,到最后一个元素 g r i d [ n − 1 ] [ m − 1 ] grid[n−1][m−1] grid[n−1][m−1] 的乘积,记作 s u f [ i ] [ j ] suf[i][j] suf[i][j] 。这可以从最后一行最后一列开始,倒着遍历得到。
然后算出从第一个元素 g r i d [ 0 ] [ 0 ] grid[0][0] grid[0][0] 开始,到 g r i d [ i ] [ j ] grid[i][j] grid[i][j] 的上一个元素的乘积,记作 p r e [ i ] [ j ] pre[i][j] pre[i][j] 。这可以从第一行第一列开始,正着遍历得到。
那么: p [ i ] [ j ] = p r e [ i ] [ j ] ⋅ s u f [ i ] [ j ] p[i][j]=pre[i][j]⋅suf[i][j] p[i][j]=pre[i][j]⋅suf[i][j]
代码实现时,可以先初始化 p [ i ] [ j ] = s u f [ i ] [ j ] p[i][j]=suf[i][j] p[i][j]=suf[i][j] ,然后把 p r e [ i ] [ j ] pre[i][j] pre[i][j] 乘到 p [ i ] [ j ] p[i][j] p[i][j] 中,就得到了答案。这样 p r e pre pre 和 s u f suf suf 就可以压缩成一个变量。
class Solution {
public:vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {const int MOD = 12345;int n = grid.size(), m = grid[0].size();vector<vector<int>> p(n, vector<int>(m));long long suf = 1; // 后缀乘积for (int i = n - 1; i >= 0; --i) {for (int j = m - 1; j >= 0; --j) {p[i][j] = suf; // p[i][j]先初始化为后缀乘积suf = suf * grid[i][j] % MOD;}}long long pre = 1; // 前缀乘积for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {p[i][j] = p[i][j] * pre % MOD; // 然后再乘上前缀乘积pre = pre * grid[i][j] % MOD;}}return p;}
};
复杂度分析:
- 时间复杂度: O ( n m ) \mathcal{O}(nm) O(nm) ,其中 n n n 和 m m m 分别为 grid \textit{grid} grid 的行数和列数。
- 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1) 。返回值不计入。
相关文章:
LeetCode 2906. 构造乘积矩阵【前后缀分解,数组】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

vue3+koa+axios实现前后端通信
vue3koaaxios实现前后端通信 写了一个小demo来实现前后端通信,涉及跨域问题,非常简单可以给大家平时开发的时候参考 服务端: 目录结构如下: router index.js // router的入口文件 // 引入路由 const Router require("koa-router&quo…...

Required MultipartFile parameter ‘file‘ is not present
出现这个原因我们首先想到的是加一个RequestParam("file"),但是还有可能的原因是因为我们的名字有错误 <span class"input-group-addon must">模板上传 </span> <input id"uploadFileUpdate" name"importFileU…...

vue3后台管理系统之layout组件的搭建
1.1静态布局 <template><div class"layout_container"><!-- 左侧导航 --><div class"layout_slider"></div><!-- 顶部导航 --><div class"layout_tabbar"></div><!-- 内容展示区 --><…...

Minio 文件上传(后端处理同文件判断,同一文件秒传)
记录minio 文件上传 MinIO提供多个语言版本SDK的支持,下边找到java版本的文档: 地址:https://docs.min.io/docs/java-client-quickstart-guide.html maven依赖如下: XML <dependency><groupId>io.minio</groupId…...

模拟IIC通讯协议(stm32)(硬件iic后面在补)
一、IIC基础知识总结。 1、IIC通讯需要两条线就可以,SCL、SDA。 2、IIC的数据传输的速率,不同的ic是不同的,根据电平维持的延时函数的时间来确定IIC数据传输的速率. 3、IIC的延时函数可以使用延时函数,延时函数一般使用系统滴答时…...
使用注解读取properties配置文件
文章目录 1、背景2、注解方式2.1 PropertySource 、 ConfigurationProperties2.2 读取properties中全部字段值ConfigurationProperties2.3 读取properties中部分字段值:value("${自定义key}") 1、背景 服务中使用到了redis,需要配置redis连接…...

Python---练习:求世界杯小组赛的总成绩(涉及:布尔类型转换为整型)
案例 世界杯案例 需求: 世界杯案例,世界杯小组赛的比赛规则是我们的球队与其他三支球队进行比赛,然后根据总成绩(积分)确定出线资格。小组赛球队实力已知(提示用户输入各球队实力),我们通过一个数字表示。如果我们赢…...

vue3学习源码笔记(小白入门系列)------KeepAlive 原理
目录 说明组件是如何被缓存的,什么时候被激活对于KeepAlive 中组件 如何完成激活的对于KeepAlive 中组件 如何完成休眠的 总结 说明 Vue 内置了 KeepAlive 组件,实现缓存多个组件实例切换时,完成对卸载组件实例的缓存,从而使得组…...

边写代码边学习之mlflow
1. 简介 MLflow 是一个多功能、可扩展的开源平台,用于管理整个机器学习生命周期的工作流程和工件。 它与许多流行的 ML 库内置集成,但可以与任何库、算法或部署工具一起使用。 它被设计为可扩展的,因此您可以编写插件来支持新的工作流程、库和…...

基于吉萨金字塔建造优化的BP神经网络(分类应用) - 附代码
基于吉萨金字塔建造优化的BP神经网络(分类应用) - 附代码 文章目录 基于吉萨金字塔建造优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.吉萨金字塔建造优化BP神经网络3.1 BP神经网络参数设置3.2 吉萨金字…...
axios的post请求所有传参方式
Axios支持多种方式来传递参数给POST请求。以下是一些常见的方式: 作为请求体: 你可以将参数作为请求体的一部分,通常用于发送表单数据或JSON数据。例如: const data { key1: value1, key2: value2 }; axios.post(/api/endpoint, …...
【c++】向webrtc学比较2: IsNewerSequenceNumber 用于NackTracker及测试
LatestSequenceNumber inline uint16_t LatestSequenceNumber(uint16_t sequence_number1,uint16_t sequence_number2) {return IsNewerSequenceNumber(sequence_number1, sequence_number2)? sequence_number1: sequen...

PRCV 2023:语言模型与视觉生态如何协同?合合信息瞄准“多模态”技术
近期,2023年中国模式识别与计算机视觉大会(PRCV)在厦门成功举行。大会由中国计算机学会(CCF)、中国自动化学会(CAA)、中国图象图形学学会(CSIG)和中国人工智能学会&#…...
深度学习硬件配置推荐(kaggle学习)
目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比?3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大,可能需要更多的 GPU 显存,请推荐显存4. GDDR6和HBM25. HDD 或 SATA SSD 1. 基础推荐 假设您作为一个深度学习入门学者的…...

1019hw
登录窗口头文件 #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QToolBar> #include <QMenuBar> #include <QPushButton> #include <QStatusBar> #include <QLabel> #include <QDockWidget>//浮动窗口…...

两分钟搞懂UiAutomator自动化测试框架
1. UiAutomator简介 UiAutomator是谷歌在Android4.1版本发布时推出的一款用Java编写的UI测试框架,基于Accessibility服务。其最大的特点就是可以跨进程操作,可以使用UiAutomator框架提供的一些方便的API来对安卓应用进行一系列的自动化测试操作…...

Fast DDS之Subscriber
目录 SubscriberSubscriberQosSubscriberListener创建Subscriber DataReaderSampleInfo读取数据 Subscriber扮演容器的角色,里面可以有很多DataReaders,它们使用Subscriber的同一份SubscriberQos配置。Subscriber可以承载不同Topic和数据类型的DataReade…...
测试PySpark
文章最前: 我是Octopus,这个名字来源于我的中文名--章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的…...
C语言- 原子操作
基本概念 在C语言(尤其是C11标准之后)中,原子操作提供了一种机制,使得程序员可以在并发环境中,不使用互斥或其他同步原语,而直接对数据进行操作,同时确保数据的完整性和一致性。 原子变量和原子操作的核心思想是:无论什么时候,只有一个线程能够看到变量的修改操作。…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...