What is the key concept for solving the Maximum Trailing Zeros in a Cornered Path problem?

The key concept is understanding how trailing zeros are created by the factors of 2 and 5 in the product of path values. Efficiently calculating the product of these factors in a cornered path is critical.

How can I optimize the calculation of trailing zeros in a grid?

Optimizing the calculation can be achieved by using prefix sums to precompute the factors of 2 and 5 in rows and columns, reducing redundant calculations for each path.

What patterns are involved in solving the Maximum Trailing Zeros in a Cornered Path problem?

This problem involves Array and Matrix patterns, particularly using dynamic programming or prefix sums to efficiently handle large grids.

What is the time complexity of solving this problem?

The time complexity can vary depending on the approach, with a brute-force solution being O(m * n), but optimizations with prefix sums can significantly reduce this.

What are common pitfalls to avoid when solving this problem?

Common pitfalls include failing to account for both 2 and 5 factors in the product, not optimizing the path calculations, and revisiting cells during the corner turn.

#2245

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

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

给你一个二维整数数组 grid ，大小为 m x n ，其中每个单元格都含一个正整数。转角路径定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全向水平方向或者向竖直方向移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝另一个方向行进：如果之前是…

数组矩阵前缀和

题目描述

给你一个二维整数数组 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

lightbulb

解题思路

方法一：前缀和 + 枚举拐点

首先我们要明确，对于一个乘积，尾随零的个数取决于因子中 $2$ 和 $5$ 的个数的较小值。另外，每一条转角路径应该覆盖尽可能多的数，因此，它一定是从某个边界出发，到达某个拐点，再到达另一个边界。

因此，我们可以创建四个二维数组 $r2$ , $c2$ , $r5$ , $c5$ 来记录每一行和每一列中 $2$ 和 $5$ 的个数。其中：

r2[i][j] 表示第 $i$ 行中从第 $1$ 列到第 $j$ 列的 $2$ 的个数；
c2[i][j] 表示第 $j$ 列中从第 $1$ 行到第 $i$ 行的 $2$ 的个数；
r5[i][j] 表示第 $i$ 行中从第 $1$ 列到第 $j$ 列的 $5$ 的个数；
c5[i][j] 表示第 $j$ 列中从第 $1$ 行到第 $i$ 行的 $5$ 的个数。

接下来，我们遍历二维数组 grid，对于每个数，我们计算它的 $2$ 和 $5$ 的个数，然后更新四个二维数组。

然后，我们枚举拐点 $(i, j)$ ，对于每个拐点，我们计算四个值，其中：

a 表示从 $(i, 1)$ 右移到 $(i, j)$ ，再从 $(i, j)$ 拐头向上移动到 $(1, j)$ 的路径中 $2$ 的个数和 $5$ 的个数的较小值；
b 表示从 $(i, 1)$ 右移到 $(i, j)$ ，再从 $(i, j)$ 拐头向下移动到 $(m, j)$ 的路径中 $2$ 的个数和 $5$ 的个数的较小值；
c 表示从 $(i, n)$ 左移到 $(i, j)$ ，再从 $(i, j)$ 拐头向上移动到 $(1, j)$ 的路径中 $2$ 的个数和 $5$ 的个数的较小值；
d 表示从 $(i, n)$ 左移到 $(i, j)$ ，再从 $(i, j)$ 拐头向下移动到 $(m, j)$ 的路径中 $2$ 的个数和 $5$ 的个数的较小值。

每一次枚举，我们取这四个值的最大值，然后更新答案。

最后，我们返回答案即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组 grid 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r2 = [[0] * (n + 1) for _ in range(m + 1)]
        c2 = [[0] * (n + 1) for _ in range(m + 1)]
        r5 = [[0] * (n + 1) for _ in range(m + 1)]
        c5 = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                s2 = s5 = 0
                while x % 2 == 0:
                    x //= 2
                    s2 += 1
                while x % 5 == 0:
                    x //= 5
                    s5 += 1
                r2[i][j] = r2[i][j - 1] + s2
                c2[i][j] = c2[i - 1][j] + s2
                r5[i][j] = r5[i][j - 1] + s5
                c5[i][j] = c5[i - 1][j] + s5
        ans = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                a = min(r2[i][j] + c2[i - 1][j], r5[i][j] + c5[i - 1][j])
                b = min(r2[i][j] + c2[m][j] - c2[i][j], r5[i][j] + c5[m][j] - c5[i][j])
                c = min(r2[i][n] - r2[i][j] + c2[i][j], r5[i][n] - r5[i][j] + c5[i][j])
                d = min(
                    r2[i][n] - r2[i][j - 1] + c2[m][j] - c2[i][j],
                    r5[i][n] - r5[i][j - 1] + c5[m][j] - c5[i][j],
                )
                ans = max(ans, a, b, c, d)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently handle large grid sizes and optimize the computation of trailing zeros?
question_mark
Does the candidate demonstrate an understanding of how factors of 2 and 5 affect trailing zeros?
question_mark
Is the candidate able to think critically about how to manage path direction and avoid redundant calculations?

warning

常见陷阱

外企场景

error
Forgetting to consider the factorization of both 2 and 5 when calculating trailing zeros.
error
Failing to optimize the solution with dynamic programming or prefix sums, leading to redundant calculations.
error
Not properly tracking the path direction and revisiting cells during the corner turn.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum number of trailing zeros for paths with multiple turns.
arrow_right_alt
Modify the grid to allow diagonal paths and calculate trailing zeros for these new paths.
arrow_right_alt
Add constraints to limit the grid size, challenging the optimization of the solution.

help

常见问题

外企场景

继续练习

#2132 用邮票贴满网格图 #2428 沙漏的最大总和 #2017 网格游戏