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

难度: Medium

给你一个二维整数数组 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
解释：网格如上图所示。
不存在乘积含尾随零的转角路径。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= grid[i][j] <= 1000

Submission

运行时间: 1143 ms

内存: 52.4 MB

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

Explain

题解通过预处理每个数字的2和5的因子个数，并利用这些预处理的数据来计算二维网格每个位置的累计因子数，最终以此来找出转角路径乘积中尾随零的最大数目。具体步骤为：1. 对所有可能的数字值从2到1000，计算并存储每个数字分解中2和5的个数。2. 为了有效计算乘积的尾随零数目，使用前缀和的方法存储网格中每一行从开始到当前列的2和5的因子的总数。3. 遍历网格的每一列，计算从当前列向左或向右拐弯时2和5的因子总数，使用上述前缀和加速这一计算。4. 从每个网格点考虑所有可能的转角路径（向上、向下、向左、向右），并更新尾随零的最大数目。这种方法有效地利用了动态规划的思想和前缀和技术，避免了重复计算。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

# 预处理数字的2和5因子
c2, c5 = [0] * 1001, [0] * 1001
for i in range(2, 1001):
    if i % 2 == 0: c2[i] = c2[i // 2] + 1  # 递推计算2的因子个数
    if i % 5 == 0: c5[i] = c5[i // 5] + 1  # 递推计算5的因子个数

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):  # 计算前缀和
                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

Explore

在预处理每个数字的2和5的因子时，使用递归的方法来确保每个数字的因子被正确计算。对于数字i，如果它能被2整除，则它的2的因子个数等于`i // 2`的2的因子个数再加1；同理，如果它能被5整除，则它的5的因子个数等于`i // 5`的5的因子个数再加1。通过这种递推方式，可以从小到大依次计算出每个数字的2和5的因子个数，从而确保计算的正确性。

使用一个二维数组存储前缀和，并且每个元素是一个元组（存储2和5的因子数），主要是为了方便计算任意子区域中数字的2和5因子的总数。二维数组的每一行代表一个网格行的前缀和，元组中分别记录该行到当前列为止的2和5因子的累计数。这种结构使得在遍历网格并计算转角路径的尾随零时，能够快速获取任意水平或垂直段的2和5因子总数，从而快速计算出尾随零的数量。此外，这种方法避免了重复计算，提高了效率。

在计算尾随零的最大数目时，算法考虑了从每个网格点出发的所有可能的转角路径（包括向上、向下、向左、向右转弯的路径）。通过遍历每一列，分别计算从该列的顶部到底部和从底部到顶部的累积2和5因子的总数，并结合该列对应行的前缀和，计算出从该网格点向左或向右拐弯的2和5因子总数。然后，算法计算并更新可能的最大尾随零数目。这种全方位考虑确保了不同方向的转角路径都被充分计算，从而找出可能的最大尾随零数目。