当前位置: 首页 > 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标准之后)中,原子操作提供了一种机制,使得程序员可以在并发环境中,不使用互斥或其他同步原语,而直接对数据进行操作,同时确保数据的完整性和一致性。 原子变量和原子操作的核心思想是:无论什么时候,只有一个线程能够看到变量的修改操作。…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...