当前位置: 首页 > news >正文

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[n1][m1] 的乘积,记作 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」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

vue3+koa+axios实现前后端通信

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

Required MultipartFile parameter ‘file‘ is not present

出现这个原因我们首先想到的是加一个RequestParam("file")&#xff0c;但是还有可能的原因是因为我们的名字有错误 <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的支持&#xff0c;下边找到java版本的文档&#xff1a; 地址&#xff1a;https://docs.min.io/docs/java-client-quickstart-guide.html maven依赖如下&#xff1a; XML <dependency><groupId>io.minio</groupId…...

模拟IIC通讯协议(stm32)(硬件iic后面在补)

一、IIC基础知识总结。 1、IIC通讯需要两条线就可以&#xff0c;SCL、SDA。 2、IIC的数据传输的速率&#xff0c;不同的ic是不同的&#xff0c;根据电平维持的延时函数的时间来确定IIC数据传输的速率. 3、IIC的延时函数可以使用延时函数&#xff0c;延时函数一般使用系统滴答时…...

使用注解读取properties配置文件

文章目录 1、背景2、注解方式2.1 PropertySource 、 ConfigurationProperties2.2 读取properties中全部字段值ConfigurationProperties2.3 读取properties中部分字段值&#xff1a;value("${自定义key}") 1、背景 服务中使用到了redis&#xff0c;需要配置redis连接…...

Python---练习:求世界杯小组赛的总成绩(涉及:布尔类型转换为整型)

案例 世界杯案例 需求&#xff1a; 世界杯案例&#xff0c;世界杯小组赛的比赛规则是我们的球队与其他三支球队进行比赛&#xff0c;然后根据总成绩(积分)确定出线资格。小组赛球队实力已知(提示用户输入各球队实力&#xff09;&#xff0c;我们通过一个数字表示。如果我们赢…...

vue3学习源码笔记(小白入门系列)------KeepAlive 原理

目录 说明组件是如何被缓存的&#xff0c;什么时候被激活对于KeepAlive 中组件 如何完成激活的对于KeepAlive 中组件 如何完成休眠的 总结 说明 Vue 内置了 KeepAlive 组件&#xff0c;实现缓存多个组件实例切换时&#xff0c;完成对卸载组件实例的缓存&#xff0c;从而使得组…...

边写代码边学习之mlflow

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

基于吉萨金字塔建造优化的BP神经网络(分类应用) - 附代码

基于吉萨金字塔建造优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于吉萨金字塔建造优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.吉萨金字塔建造优化BP神经网络3.1 BP神经网络参数设置3.2 吉萨金字…...

axios的post请求所有传参方式

Axios支持多种方式来传递参数给POST请求。以下是一些常见的方式&#xff1a; 作为请求体&#xff1a; 你可以将参数作为请求体的一部分&#xff0c;通常用于发送表单数据或JSON数据。例如&#xff1a; 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:语言模型与视觉生态如何协同?合合信息瞄准“多模态”技术

近期&#xff0c;2023年中国模式识别与计算机视觉大会&#xff08;PRCV&#xff09;在厦门成功举行。大会由中国计算机学会&#xff08;CCF&#xff09;、中国自动化学会&#xff08;CAA&#xff09;、中国图象图形学学会&#xff08;CSIG&#xff09;和中国人工智能学会&#…...

深度学习硬件配置推荐(kaggle学习)

目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比&#xff1f;3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大&#xff0c;可能需要更多的 GPU 显存&#xff0c;请推荐显存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测试框架&#xff0c;基于Accessibility服务。其最大的特点就是可以跨进程操作&#xff0c;可以使用UiAutomator框架提供的一些方便的API来对安卓应用进行一系列的自动化测试操作&#xf…...

Fast DDS之Subscriber

目录 SubscriberSubscriberQosSubscriberListener创建Subscriber DataReaderSampleInfo读取数据 Subscriber扮演容器的角色&#xff0c;里面可以有很多DataReaders&#xff0c;它们使用Subscriber的同一份SubscriberQos配置。Subscriber可以承载不同Topic和数据类型的DataReade…...

测试PySpark

文章最前&#xff1a; 我是Octopus&#xff0c;这个名字来源于我的中文名--章鱼&#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github &#xff1b;这博客是记录我学习的点点滴滴&#xff0c;如果您对 Python、Java、AI、算法有兴趣&#xff0c;可以关注我的…...

C语言- 原子操作

基本概念 在C语言(尤其是C11标准之后)中,原子操作提供了一种机制,使得程序员可以在并发环境中,不使用互斥或其他同步原语,而直接对数据进行操作,同时确保数据的完整性和一致性。 原子变量和原子操作的核心思想是:无论什么时候,只有一个线程能够看到变量的修改操作。…...

手游刚开服就被攻击怎么办?如何防御DDoS?

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

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; 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相关知识

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

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...