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

【C++前缀和数论贪心】2245. 转角路径的乘积中最多能有几个尾随零|2036

news 2025/7/5 10:33:01

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
质数、最大公约数、菲蜀定理
贪心（决策包容性)

LeetCode2245. 转角路径的乘积中最多能有几个尾随零

给你一个二维整数数组 grid ，大小为 m x n，其中每个单元格都含一个正整数。
转角路径定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全向水平方向或者向竖直方向移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝另一个方向行进：如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。
一条路径的乘积定义为：路径上所有值的乘积。
请你从 grid 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。
注意：
水平移动是指向左或右移动。
竖直移动是指向上或下移动。
示例 1：
输入：grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
输出：3
解释：左侧的图展示了一条有效的转角路径。
其乘积为 15 * 20 * 6 * 1 * 10 = 18000 ，共计 3 个尾随零。
可以证明在这条转角路径的乘积中尾随零数目最多。
中间的图不是一条有效的转角路径，因为它有不止一个弯。
右侧的图也不是一条有效的转角路径，因为它需要重复访问已经访问过的单元格。
示例 2：
输入：grid = [[4,3,2],[7,6,1],[8,8,8]]
输出：0
解释：网格如上图所示。
不存在乘积含尾随零的转角路径。

前缀和+贪心

某条最优解路径的起点（终点）没有到达网格边缘则延长到网格，仍然是最优解。故只需要枚举起点和终点都在边缘。
路径的乘积0的数量 $\iff$ 路径的质因数中2的数量和5的数量中的较小者。
通过grid[r][c]枚举拐弯处，分别枚举左上、左下，右上、右下。

代码

核心代码

template<class T = int>
class CPreSum2 {
public:template<class _Pr>CPreSum2(int rowCnt, int colCount, _Pr pr) :m_iRowCnt(rowCnt), m_iColCnt(colCount) {m_vSum.assign(rowCnt + 1, vector<int>(colCount + 1));for (int r = 0; r < rowCnt; r++) {for (int c = 0; c < colCount; c++) {m_vSum[r + 1][c + 1] = m_vSum[r][c + 1] + m_vSum[r + 1][c] - m_vSum[r][c] + pr(r, c);}}}T Get(int left, int top, int right, int bottom)const {return m_vSum[bottom + 1][right + 1] - m_vSum[top][right + 1] - m_vSum[bottom + 1][left] + m_vSum[top][left];}T GetTopLeft(int bottom, int right) { return m_vSum[bottom+1][right+1]; }T GetBottomRight(int top, int left) { return Get(left, top, m_iColCnt - 1, m_iRowCnt - 1); }vector<vector<T>> m_vSum;const int m_iRowCnt, m_iColCnt;
};class Solution {public:int maxTrailingZeros(vector<vector<int>>& grid) {m_iR = grid.size();m_iC = grid[0].size();auto Cnt2 = [&](int r, int c) {int tmp = grid[r][c];int cnt = 0;for (; (0 == tmp % 2); tmp /= 2, cnt++);return cnt;};auto Cnt5 = [&](int r, int c) {int tmp = grid[r][c];int cnt = 0;for (; (0 == tmp % 5); tmp /= 5, cnt++);return cnt;};int ret = 0;CPreSum2<int> preSum2(m_iR, m_iC, Cnt2);CPreSum2<int> preSum5(m_iR, m_iC, Cnt5);for (int r = 0; r < m_iR; r++) {for (int c = 0; c < m_iC; c++) {if( (r > 0 )&&( c > 0 )){//左上 const int ctn2 = preSum2.Get(0, r, c, r) + preSum2.Get(c,0,c,r-1);const int ctn5 = preSum5.Get(0, r, c, r) + preSum5.Get(c, 0, c, r - 1);ret = max(ret, min(ctn2, ctn5));}if ((r + 1 != m_iR) && (c > 0)) {//左下const int ctn2 = preSum2.Get(0, r, c, r) + preSum2.Get(c, r+1, c, m_iR-1);const int ctn5 = preSum5.Get(0, r, c, r) + preSum5.Get(c, r + 1, c, m_iR - 1);ret = max(ret, min(ctn2, ctn5));}if ((r > 0) && (c+1 != m_iC )){//右上 const int ctn2 = preSum2.Get(c, r, m_iC-1, r) + preSum2.Get(c, 0, c, r - 1);const int ctn5 = preSum5.Get(c, r, m_iC - 1, r) + preSum5.Get(c, 0, c, r - 1);ret = max(ret, min(ctn2, ctn5));}if ((r + 1 != m_iR) && (c + 1 != m_iC)) {//右下const int ctn2 = preSum2.Get(c, r, m_iC - 1, r) + preSum2.Get(c, r + 1, c, m_iR - 1);const int ctn5 = preSum5.Get(c, r, m_iC - 1, r) + preSum5.Get(c, r + 1, c, m_iR - 1);ret = max(ret, min(ctn2, ctn5));}{//水平const int ctn2 = preSum2.Get(0, r, m_iC - 1, r) ;const int ctn5 = preSum5.Get(0, r, m_iC - 1, r);;ret = max(ret, min(ctn2, ctn5));}{//竖直const int ctn2 = preSum2.Get(c, 0, c, m_iR-1);const int ctn5 = preSum5.Get(c, 0, c, m_iR - 1);ret = max(ret, min(ctn2, ctn5));}}}return ret;}int m_iR, m_iC;};

单元测试

vector<vector<int>> grid;TEST_METHOD(TestMethod11){grid = { {23,17,15,3,20},{8,1,20,27,11},{9,4,6,2,21},{40,9,1,10,6},{22,7,4,5,3} };auto res = Solution().maxTrailingZeros(grid);AssertEx(3, res);}TEST_METHOD(TestMethod12){grid = { {4,3,2},{7,6,1},{8,8,8} };auto res = Solution().maxTrailingZeros(grid);AssertEx(0, res);}TEST_METHOD(TestMethod13){grid = { {1,5,2,4,25} };auto res = Solution().maxTrailingZeros(grid);AssertEx(3, res);}TEST_METHOD(TestMethod14){grid = { {2},{5},{10} };auto res = Solution().maxTrailingZeros(grid);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功