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

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...