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

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

题解

题目：只能转一次，求路径中每个元素相乘的结果有几个零

思路：

1. 正数的乘积结果中尾 0 的个数由乘数中 因子 2，5 的个数中较小的决定,即 尾随零=min(num2,num5)
2. 路径要么是横，竖，要么是UL，UR，DL，DR
3. 用前缀和维护每一行和每一列因子 22 与因子 55 的数量
4. 枚举拐点（i,j）计算答案

代码

func maxTrailingZeros(grid [][]int) int {
    
	//初始化
	n := len(grid)
	m := len(grid[0])
	factor := make([][]pair, n+1) //2和5的数量
	x := make([][]pair, n+1)      //列 x
	y := make([][]pair, n+1)      //行 y
	for i := 0; i <= len(grid); i++ {
    
		factor[i] = make([]pair, m+1)
		x[i] = make([]pair, m+1)
		y[i] = make([]pair, m+1)
	}
	//计算前缀和
	for i := 1; i <= n; i++ {
    
		for j := 1; j <= m; j++ {
    
			factor[i][j] = getRes(grid[i-1][j-1])
			x[i][j].two = x[i-1][j].two + factor[i][j].two
			x[i][j].five = x[i-1][j].five + factor[i][j].five
			y[i][j].two = y[i][j-1].two + factor[i][j].two
			y[i][j].five = y[i][j-1].five + factor[i][j].five
		}
	}
	//计算答案
	ans := 0
	for i := 1; i <= n; i++ {
    
		for j := 1; j <= m; j++ {
    
			upAndLeft := min(x[i][j].two+y[i][j].two-factor[i][j].two, x[i][j].five+y[i][j].five-factor[i][j].five)
			upAndRight := min(x[i][j].two+y[i][m].two-y[i][j].two, x[i][j].five+y[i][m].five-y[i][j].five)
			downAndLeft := min(x[n][j].two+y[i][j].two-x[i][j].two, x[n][j].five+y[i][j].five-x[i][j].five)
			downAndRight := min(x[n][j].two+y[i][m].two-x[i-1][j].two-y[i][j].two, x[n][j].five+y[i][m].five-x[i-1][j].five-y[i][j].five)
			ans = max(ans, upAndLeft)
			ans = max(ans, upAndRight)
			ans = max(ans, downAndLeft)
			ans = max(ans, downAndRight)
		}
	}
	return ans
}
func getRes(val int) pair {
    
	two, five := 0, 0
	a, b := val, val
	for a%2 == 0 && a != 0 {
    
		a /= 2
		two++
	}
	for b%5 == 0 && b != 0 {
    
		b /= 5
		five++
	}
	return pair{
    two: two, five: five}
}
func min(i, j int) int {
    
	if i > j {
    
		return j
	}
	return i
}
func max(i, j int) int {
    
	if i > j {
    
		return i
	}
	return j
}