本文涉及的基础知识点
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);
}
