上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int maxTrailingZeros(vector<vector<int>>& grid) {
}
};
golang 解法, 执行用时: 172 ms, 内存消耗: 17.4 MB, 提交时间: 2023-09-06 23:25:33
var c25 [1001][2]int
func init() {
// 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数
for i := 2; i <= 1000; i++ {
if i%2 == 0 { c25[i][0] = c25[i/2][0] + 1 }
if i%5 == 0 { c25[i][1] = c25[i/5][1] + 1 }
}
}
func maxTrailingZeros(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
s := make([][][2]int, m)
for i, row := range grid {
s[i] = make([][2]int, n+1)
for j, v := range row {
s[i][j+1][0] = s[i][j][0] + c25[v][0] // 每行的因子 2 的前缀和
s[i][j+1][1] = s[i][j][1] + c25[v][1] // 每行的因子 5 的前缀和
}
}
for j := 0; j < n; j++ {
s2, s5 := 0, 0
for i, row := range grid { // 从上往下，枚举左拐还是右拐
s2 += c25[row[j]][0]
s5 += c25[row[j]][1]
ans = max(ans, max(min(s2+s[i][j][0], s5+s[i][j][1]),
min(s2+s[i][n][0]-s[i][j+1][0], s5+s[i][n][1]-s[i][j+1][1])))
}
s2, s5 = 0, 0
for i := m - 1; i >= 0; i-- { // 从下往上，枚举左拐还是右拐
s2 += c25[grid[i][j]][0]
s5 += c25[grid[i][j]][1]
ans = max(ans, max(min(s2+s[i][j][0], s5+s[i][j][1]),
min(s2+s[i][n][0]-s[i][j+1][0], s5+s[i][n][1]-s[i][j+1][1])))
}
}
return
}
func max(a, b int) int { if a < b { return b }; return a }
func min(a, b int) int { if a > b { return b }; return a }
java 解法, 执行用时: 55 ms, 内存消耗: 68.5 MB, 提交时间: 2023-09-06 23:25:19
class Solution {
static int[][] c25 = new int[1001][2];
static {
// 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数
for (var i = 2; i <= 1000; i++) {
if (i % 2 == 0) c25[i][0] = c25[i / 2][0] + 1;
if (i % 5 == 0) c25[i][1] = c25[i / 5][1] + 1;
}
}
public int maxTrailingZeros(int[][] grid) {
int m = grid.length, n = grid[0].length, ans = 0;
var s = new int[m][n + 1][2];
for (var i = 0; i < m; i++)
for (var j = 0; j < n; j++) {
s[i][j + 1][0] = s[i][j][0] + c25[grid[i][j]][0]; // 每行的因子 2 的前缀和
s[i][j + 1][1] = s[i][j][1] + c25[grid[i][j]][1]; // 每行的因子 5 的前缀和
}
for (var j = 0; j < n; j++) {
for (int i = 0, s2 = 0, s5 = 0; i < m; i++) { // 从上往下，枚举左拐还是右拐
s2 += c25[grid[i][j]][0];
s5 += c25[grid[i][j]][1];
ans = Math.max(ans, Math.max(Math.min(s2 + s[i][j][0], s5 + s[i][j][1]),
Math.min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1])));
}
for (int i = m - 1, s2 = 0, s5 = 0; i >= 0; i--) { // 从下往上，枚举左拐还是右拐
s2 += c25[grid[i][j]][0];
s5 += c25[grid[i][j]][1];
ans = Math.max(ans, Math.max(Math.min(s2 + s[i][j][0], s5 + s[i][j][1]),
Math.min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1])));
}
}
return ans;
}
}
python3 解法, 执行用时: 1804 ms, 内存消耗: 53.2 MB, 提交时间: 2023-09-06 23:25:05
'''
尾零的个数就是路径上的数的因子 2 的个数和，与因子 5 的个数之和的较小值。
那么数越多越好，路径的起点和终点都应该在边界上。
预处理每一行的因子的前缀和，然后枚举所有的路径：
从上往下走，枚举左拐/右拐；
从下往上走，枚举左拐/右拐。
所有路径上的 min(s2, s5) 的最大值即为答案，这里 s2 为路径上的因子 2 的个数之和，
s5 为路径上的因子 5 的个数之和。
'''
c2, c5 = [0] * 1001, [0] * 1001
for i in range(2, 1001): # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数
if i % 2 == 0: c2[i] = c2[i // 2] + 1
if i % 5 == 0: c5[i] = c5[i // 5] + 1
class Solution:
def maxTrailingZeros(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
s = [[None] * (n + 1) for _ in range(m)]
for i, row in enumerate(grid):
s[i][0] = (0, 0)
for j, v in enumerate(row): # 计算 grid 每行因子 2 和 5 的前缀和
s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])
ans = 0
for j, col in enumerate(zip(*grid)):
s2 = s5 = 0
for i, v in enumerate(col): # 从上往下，枚举左拐还是右拐
s2 += c2[v]
s5 += c5[v]
ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),
min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))
s2 = s5 = 0
for i in range(m - 1, -1, -1): # 从下往上，枚举左拐还是右拐
s2 += c2[col[i]]
s5 += c5[col[i]]
ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),
min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))
return ans
