详细介绍：力扣2245. 转角路径的乘积中最多能有几个尾随零

这一题的大意是给出一个矩阵，让我们找到转角路径，使得路径上的乘积中尾随0尽可能的多。
我们把所有的转角路径都枚举一下，然后找到最大值。就是很容易想到的途径就
那么什么是转角路径呢？
向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。就是转角路径 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 向水平方向 或者 向竖直方向 移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 另一个 方向行进：假设之前
这看起来很麻烦，
我们要求枚举所有的点，把这些点都当作转角路径的拐点，然后对于每一个点就会有四种情况，上左，上右，下左，下右。
对于对于每一个点的这四种情况，我们需要需要取最大值。
因为数据范围为O（m*n）=10^5，只能支撑双重for循环
现在重点就在于如何快速的找到一条路径上的乘积中最多能有几个尾随零，
我们不能把路径上的每一个元素相乘，这样会溢出。
我们可以先提前找到每一个数中有多少个因数2和因数5，统计一下，因为每一个0的产生都是由一个因数2和一个因数5相乘得到的。因此在转角路径上的因数2和因数5的个数就决定了尾随0的个数，只需统计出转角路径上因数2和因数5两者个数的最小值即为尾随0的个数。
而统计路径上的因数，可以用前缀和来优化，可以分别用一个列前缀和和行前缀和来表示路径上的尾随0的个数。
因此，题目思路清晰：
1.先统计每一个点上的因数2和因数5的个数
2.再用前缀和计算出每一列和每一行上的因数2和因数5的个数。
3.枚举每一个点充当拐点，从而引出四种情况：上左，上右，下左，下右。用列前缀和行前缀和计算以该点作为拐点的路径的尾随零的个数。四种情况取最大值。
4.返回ans

int maxTrailingZeros(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();vector<vector<int>> cnt2(m+1,vector<int>(n+1,0));vector<vector<int>> cnt5(m+1,vector<int>(n+1,0));vector<vector<int>> col2(m+1,vector<int>(n+1,0));vector<vector<int>> col5(m+1,vector<int>(n+1,0));vector<vector<int>> row2(m+1,vector<int>(n+1,0));vector<vector<int>> row5(m+1,vector<int>(n+1,0));int ans=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){//看一个数里面有多少个2或者5的因子 int x=grid[i][j];while(x!=0){if(x%2==0){cnt2[i][j]++;x/=2;}else{break;}}x=grid[i][j];while(x!=0){if(x%5==0){cnt5[i][j]++;x/=5;}else{break;}}}}//统计出来了每一个点的2和5的数量现在让我们来算前缀和 for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){row2[i][j]=row2[i][j-1]+cnt2[i-1][j-1];row5[i][j]=row5[i][j-1]+cnt5[i-1][j-1];col2[i][j]=col2[i-1][j]+cnt2[i-1][j-1];col5[i][j]=col5[i-1][j]+cnt5[i-1][j-1];}}//现在我们需要找拐点for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){//先右后下//先下后右 //先下往左int down2= col2[i][j]-cnt2[i-1][j-1];int down5= col5[i][j]-cnt5[i-1][j-1];int left2= row2[i][j];int left5= row5[i][j];ans= max(ans,min(down2+left2,down5+left5));// 从下往右int  right2 = row2[i][n]-row2[i][j-1];int right5 = row5[i][n]- row5[i][j-1];ans=max(ans,min(down2+right2,down5+right5));//先上后左int  up2 = col2[m][j]-col2[i][j];int  up5 = col5[m][j]-col5[i][j];ans= max(ans,min(up2+left2,up5+left5));//先上后右 ans= max(ans,min(up2+right2,up5+right5));}}return ans;}

总结：这一题的难点我觉得不止一个：
1.将计算乘积的尾随0转换成计算路径上5和2因子的个数。
2.如何找到每一条路径，手段是枚举每一个点作为拐点，然后分四种情况讨论。
3.用前缀和优化，要能熟练计算列前缀和和行前缀和。
需要对这些知识点很熟练才能快速写出无bug的代码，不然调试也不好调试。
时间复杂度O（n^5)