太原市给企业做网站,erp企业管理系统软件开发,三把火科技专业提供企业信息化服务,数据库网站本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服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^51 m grid[i].length 10^52 n * m 10^51 grid[i][j] 10^9 前后缀分解右边的数字为难度分
238. 除自身以外数组的乘积 和本题几乎一样剑指Offer66. 构建乘积数组 和本题几乎一样2256. 最小平均差 13952483. 商店的最少代价 14952420. 找到所有好下标 16952167. 移除所有载有违禁货物车厢所需的最少时间 22192484. 统计回文子序列数目 22232565. 最少得分子序列 24322552. 统计上升四元组 243342. 接雨水
解法 前后缀分解
核心思想把矩阵拉成一维的我们需要算出每个数左边所有数的乘积以及右边所有数的乘积这都可以用递推得到。
先算出从 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:vectorvectorint constructProductMatrix(vectorvectorint grid) {const int MOD 12345;int n grid.size(), m grid[0].size();vectorvectorint p(n, vectorint(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) 。返回值不计入。
