高端网站建设 选择磐石网络,公司网络推广方法,搜索引擎下载,宁波seo网络推广公司排名基础知识点
C算法#xff1a;前缀和基础
题目
给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid #xff0c;定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件#xff0c;则称 p 为 grid 的 乘积矩阵 #xff1a; 对于每个元素 p[i][j] …基础知识点
C算法前缀和基础
题目
给你一个下标从 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]] 。
感悟
原以为和MOD 1000000007一样直接使用封装好的此类发现错误。赛场上时间紧急来不及分析是两个不同的问题还是我封装错误。只好使用笨办法。我记得1000000007是质数才能转除为乘。考虑过12345是否是质数当时觉判断烦恼所以没判断。现在觉得很简单以5结尾就是5的倍数不是质数。
分析
前缀和后缀和。第一轮的preRow记录[0,r) 所有元素的乘积vLeft[r][c] 记录本行左边各元素的乘积vRight[r][c]记录本行右边各元素的乘积。vRet[r][c]记录这三个的乘积。第二轮preRow记录[r1,m_r)所有元素的乘积。第二轮vRet[r][c]乘以preRow就是结果。
测试用例
123456789
结果
当前数前面行的乘积前面行的乘积左边乘积右边乘积114…916214…913314…921467…9130567…946667…920171…6117281…617991…61561
解释
对{4,5,6}而言第一轮preRow是1236第二轮preRow是789。对4而言left是1,right是30。对5而言left是4,right是6。对6而言left是20,right是1。
时间复杂度
O(n^2) 2轮每轮2层循环每层循环是O(n)。
代码
class Solution { public: vectorvector constructProductMatrix(vectorvector grid) { m_r grid.size(); m_c grid.front().size(); //vLeft记录当前行左边的成绩 vectorvector vLeft(m_r, vector(m_c)), vRight(m_r, vector(m_c)), vRet(m_r, vector(m_c)); int iPreRow 1; for (int r 0; r m_r; r) { int pre 1; for (int c 0; c m_c; c) { vLeft[r][c] pre; MulSelf(pre, grid[r][c]); } pre 1; for (int c m_c-1 ; c 0 ; c-- ) { vRight[r][c] pre; MulSelf(pre, grid[r][c]); } for (int c 0; c m_c; c) { vRet[r][c] 1; MulSelf(vRet[r][c], iPreRow); MulSelf(vRet[r][c], vLeft[r][c]); MulSelf(vRet[r][c], vRight[r][c]); } MulSelf(iPreRow, pre); } iPreRow 1; for (int r m_r-1; r 0 ; r-- ) { int pre 1; for (int c 0; c m_c; c) { MulSelf(vRet[r][c], iPreRow); MulSelf(pre, grid[r][c]); } MulSelf(iPreRow, pre); } return vRet; } void MulSelf(int self, int other) { const int MOD 12345; self ((long long)self * other) % MOD; } int m_r, m_c; };
一维化降低复杂度
分析
vLeft[r][c]记录 [0,r)行所有元素及r行[0,c)列元素的乘积第二轮的pre记录(r,m_c)行所有元素及r行c,m_c)列元素的乘积。 vLeft[1][1] 1234 第二轮的pre 9876
代码
class Solution { public: vectorvector constructProductMatrix(vectorvector grid) { m_r grid.size(); m_c grid.front().size(); vector vector vLeft(m_r, vector(m_c)); int pre 1; for (int r 0; r m_r; r) { for (int c 0; c m_c; c) { vLeft[r][c] pre; MulSelf(pre, grid[r][c]); } } vectorvector vRet(m_r, vector(m_c)); pre 1; for (int r m_r-1 ; r 0 ;r–) { for (int c m_c-1 ; c 0 ; c-- ) { const int index m_c * r c; vRet[r][c] pre; MulSelf(vRet[r][c], vLeft[r][c]); MulSelf(pre, grid[r][c]); } } return vRet; } void MulSelf(int self, int other) { const int MOD 12345; self ((long long)self * other) % MOD; } int m_r, m_c; };
测试用例
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { assert(v1[i] v2[i]); } }
template void Assert(const T t1, const T t2) { assert(t1 t2); } int main() { vectorvectorgrid { {1,2,3},{4,5,6} }; vectorvector ans { {720,360,240},{180,144,120} }; auto res Solution().constructProductMatrix(grid); Assert(res, ans); grid { {1,2,},{3,4},{5,6 }}; ans { {720,360},{240,180},{144,120} }; res Solution().constructProductMatrix(grid); Assert(res, ans); grid { { 1,2,3,4,5,6 } }; ans { { 720,360,240,180,144,120} }; res Solution().constructProductMatrix(grid); Assert(res, ans); grid { { 1},{2},{3},{4},{5},{6} }; ans { { 720},{360},{240},{180},{144},{120} }; res Solution().constructProductMatrix(grid); Assert(res, ans); CConsole::Out(res); }
其它
视频课程
要是你认为本篇难道较大不好入手推荐你先学习基础算法的课程我已完成部分余下部分持续更新中就在CSDN学院。 https://edu.csdn.net/course/detail/38771
C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17
相关下载
如果你想观其大略建设下载《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
博主想队大家说的话墨家名称的来源有所得以墨记之。闻缺陷则喜的来由早发现早修改问题成本更低程序是龙算法是睛
