2245.转角路径的乘积中最多能有几个尾随零
2245.转角路径的乘积中最多能有几个尾随零
题解
题目：只能转一次，求路径中每个元素相乘的结果有几个零
思路：
- 正数的乘积结果中尾 0 的个数由乘数中 因子 2，5 的个数中较小的决定,即 尾随零=min(num2,num5)
- 路径要么是横，竖，要么是UL，UR，DL，DR
- 用前缀和维护每一行和每一列因子 22 与因子 55 的数量
- 枚举拐点（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 }
