2245. 拐弯路径的最大尾随零数

Medium

题目描述

给你一个大小为 m x n 的二维整数数组 grid，其中每个单元格都包含一个正整数。

拐弯路径定义为一组相邻的单元格，最多有一次转弯。更具体地说，路径应该专门沿水平或垂直方向移动，直到转弯处（如果有的话），而不返回先前访问过的单元格。转弯后，路径将专门沿替代方向移动：如果之前是水平移动，则垂直移动，反之亦然，同样不返回先前访问过的单元格。

路径的乘积定义为路径上所有值的乘积。

返回在 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^5
1 <= m * n <= 10^5
1 <= grid[i][j] <= 1000

解题思路

乘积的尾随零数量取决于该乘积中因子2和因子5的个数，取两者的最小值。因此，我们需要统计路径上所有数字中2和5的指数之和。

核心观察：

拐弯路径最多只有一次转弯，可以分解为两段：一段水平，一段垂直
我们可以枚举每个位置作为拐弯点，计算通过该点的所有可能拐弯路径
对于每个拐弯点，有4种可能的路径组合：上+左、上+右、下+左、下+右

算法步骤：

预处理：计算每个位置的2和5的指数
使用前缀和技术，计算每行和每列的累积2和5的指数
枚举每个位置作为拐弯点，计算4个方向的前缀和
对于每种路径组合，计算2和5指数的最小值，更新答案
特殊处理：考虑无拐弯的纯水平或垂直路径

通过前缀和优化，我们可以在O(1)时间内计算任意方向上的指数和，总时间复杂度为O(mn)。

代码实现

class Solution {
public:
    int maxTrailingZeros(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 计算每个数的2和5的指数
        vector<vector<int>> twos(m, vector<int>(n)), fives(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = grid[i][j];
                while (num % 2 == 0) {
                    twos[i][j]++;
                    num /= 2;
                }
                num = grid[i][j];
                while (num % 5 == 0) {
                    fives[i][j]++;
                    num /= 5;
                }
            }
        }
        
        // 计算前缀和
        vector<vector<int>> rowTwos(m, vector<int>(n + 1)), rowFives(m, vector<int>(n + 1));
        vector<vector<int>> colTwos(m + 1, vector<int>(n)), colFives(m + 1, vector<int>(n));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowTwos[i][j + 1] = rowTwos[i][j] + twos[i][j];
                rowFives[i][j + 1] = rowFives[i][j] + fives[i][j];
            }
        }
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colTwos[i + 1][j] = colTwos[i][j] + twos[i][j];
                colFives[i + 1][j] = colFives[i][j] + fives[i][j];
            }
        }
        
        int maxZeros = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 4种拐弯路径：上左，上右，下左，下右
                vector<pair<int, int>> paths = {
                    {colTwos[i][j] + rowTwos[i][j], colFives[i][j] + rowFives[i][j]}, // 上+左
                    {colTwos[i][j] + (rowTwos[i][n] - rowTwos[i][j]), colFives[i][j] + (rowFives[i][n] - rowFives[i][j])}, // 上+右
                    {(colTwos[m][j] - colTwos[i][j]) + rowTwos[i][j], (colFives[m][j] - colFives[i][j]) + rowFives[i][j]}, // 下+左
                    {(colTwos[m][j] - colTwos[i][j]) + (rowTwos[i][n] - rowTwos[i][j]), (colFives[m][j] - colFives[i][j]) + (rowFives[i][n] - rowFives[i][j])} // 下+右
                };
                
                for (auto& path : paths) {
                    maxZeros = max(maxZeros, min(path.first, path.second));
                }
                
                // 纯水平路径
                maxZeros = max(maxZeros, min(rowTwos[i][n], rowFives[i][n]));
                // 纯垂直路径
                maxZeros = max(maxZeros, min(colTwos[m][j], colFives[m][j]));
            }
        }
        
        return maxZeros;
    }
};

class Solution:
    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 计算每个数的2和5的指数
        twos = [[0] * n for _ in range(m)]
        fives = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                num = grid[i][j]
                while num % 2 == 0:
                    twos[i][j] += 1
                    num //= 2
                num = grid[i][j]
                while num % 5 == 0:
                    fives[i][j] += 1
                    num //= 5
        
        # 计算前缀和
        row_twos = [[0] * (n + 1) for _ in range(m)]
        row_fives = [[0] * (n + 1) for _ in range(m)]
        col_twos = [[0] * n for _ in range(m + 1)]
        col_fives = [[0] * n for _ in range(m + 1)]
        
        for i in range(m):
            for j in range(n):
                row_twos[i][j + 1] = row_twos[i][j] + twos[i][j]
                row_fives[i][j + 1] = row_fives[i][j] + fives[i][j]
        
        for j in range(n):
            for i in range(m):
                col_twos[i + 1][j] = col_twos[i][j] + twos[i][j]
                col_fives[i + 1][j] = col_fives[i][j] + fives[i][j]
        
        max_zeros = 0
        
        for i in range(m):
            for j in range(n):
                # 4种拐弯路径：上左，上右，下左，下右
                paths = [
                    (col_twos[i][j] + row_twos[i][j], col_fives[i][j] + row_fives[i][j]),
                    (col_twos[i][j] + (row_twos[i][n] - row_twos[i][j]), col_fives[i][j] + (row_fives[i][n] - row_fives[i][j])),
                    ((col_twos[m][j] - col_twos[i][j]) + row_twos[i][j], (col_fives[m][j] - col_fives[i][j]) + row_fives[i][j]),
                    ((col_twos[m][j] - col_twos[i][j]) + (row_twos[i][n] - row_twos[i][j]), (col_fives[m][j] - col_fives[i][j]) + (row_fives[i][n] - row_fives[i][j]))
                ]
                
                for two_count, five_count in paths:
                    max_zeros = max(max_zeros, min(two_count, five_count))
                
                # 纯水平路径
                max_zeros = max(max_zeros, min(row_twos[i][n], row_fives[i][n]))
                # 纯垂直路径
                max_zeros = max(max_zeros, min(col_twos[m][j], col_fives[m][j]))
        
        return max_zeros

public class Solution {
    public int MaxTrailingZeros(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 计算每个数的2和5的指数
        int[,] twos = new int[m, n];
        int[,] fives = new int[m, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = grid[i][j];
                while (num % 2 == 0) {
                    twos[i, j]++;
                    num /= 2;
                }
                num = grid[i][j];
                while (num % 5 == 0) {
                    fives[i, j]++;
                    num /= 5;
                }
            }
        }
        
        // 计算前缀和
        int[,] rowTwos = new int[m, n + 1];
        int[,] rowFives = new int[m, n + 1];
        int[,] colTwos = new int[m + 1, n];
        int[,] colFives = new int[m + 1, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowTwos[i, j + 1] = rowTwos[i, j] + twos[i, j];
                rowFives[i, j + 1] = rowFives[i, j] + fives[i, j];
            }
        }
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colTwos[i + 1, j] = colTwos[i, j] + twos[i, j];
                colFives[i + 1, j] = colFives[i, j] + fives[i, j];
            }
        }
        
        int maxZeros = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 4种拐弯路径：上左，上右，下左，下右
                var paths = new[] {
                    (colTwos[i, j] + rowTwos[i, j], colFives[i, j] + rowFives[i, j]),
                    (colTwos[i, j] + (rowTwos[i, n] - rowTwos[i, j]), colFives[i, j] + (rowFives[i, n] - rowFives[i, j])),
                    ((colTwos[m, j] - colTwos[i, j]) + rowTwos[i, j], (colFives[m, j] - colFives[i, j]) + rowFives[i, j]),
                    ((colTwos[m, j] - colTwos[i, j]) + (rowTwos[i, n] - rowTwos[i, j]), (colFives[m, j] - colFives[i, j]) + (rowFives[i, n] - rowFives[i, j]))
                };
                
                foreach (var path in paths) {
                    maxZeros = Math.Max(maxZeros, Math.Min(path.Item1, path.Item2));
                }
                
                // 纯水平路径
                maxZeros = Math.Max(maxZeros, Math.Min(rowTwos[i, n], rowFives[i, n]));
                // 纯垂直路径
                maxZeros = Math.Max(maxZeros, Math.Min(colTwos[m, j], colFives[m, j]));
            }
        }
        
        return maxZeros;
    }
}

var maxTrailingZeros = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // Count factors of 2 and 5 in each cell
    const twos = Array(m).fill().map(() => Array(n).fill(0));
    const fives = Array(m).fill().map(() => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let val = grid[i][j];
            while (val % 2 === 0) {
                twos[i][j]++;
                val /= 2;
            }
            val = grid[i][j];
            while (val % 5 === 0) {
                fives[i][j]++;
                val /= 5;
            }
        }
    }
    
    // Prefix sums for rows and columns
    const rowTwos = Array(m).fill().map(() => Array(n + 1).fill(0));
    const rowFives = Array(m).fill().map(() => Array(n + 1).fill(0));
    const colTwos = Array(m + 1).fill().map(() => Array(n).fill(0));
    const colFives = Array(m + 1).fill().map(() => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            rowTwos[i][j + 1] = rowTwos[i][j] + twos[i][j];
            rowFives[i][j + 1] = rowFives[i][j] + fives[i][j];
        }
    }
    
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            colTwos[i + 1][j] = colTwos[i][j] + twos[i][j];
            colFives[i + 1][j] = colFives[i][j] + fives[i][j];
        }
    }
    
    let maxZeros = 0;
    
    // For each cell as corner
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Path going left then up
            for (let k = 0; k <= j; k++) {
                for (let l = i; l < m; l++) {
                    const t2 = rowTwos[i][j + 1] - rowTwos[i][k] + colTwos[l + 1][k] - colTwos[i][k];
                    const t5 = rowFives[i][j + 1] - rowFives[i][k] + colFives[l + 1][k] - colFives[i][k];
                    maxZeros = Math.max(maxZeros, Math.min(t2, t5));
                }
            }
            
            // Path going right then up
            for (let k = j; k < n; k++) {
                for (let l = i; l < m; l++) {
                    const t2 = rowTwos[i][k + 1] - rowTwos[i][j] + colTwos[l + 1][k] - colTwos[i][k];
                    const t5 = rowFives[i][k + 1] - rowFives[i][j] + colFives[l + 1][k] - colFives[i][k];
                    maxZeros = Math.max(maxZeros, Math.min(t2, t5));
                }
            }
            
            // Path going left then down
            for (let k = 0; k <= j; k++) {
                for (let l = 0; l <= i; l++) {
                    const t2 = rowTwos[i][j + 1] - rowTwos[i][k] + colTwos[i + 1][k] - colTwos[l][k];
                    const t5 = rowFives[i][j + 1] - rowFives[i][k] + colFives[i + 1][k] - colFives[l][k];
                    maxZeros = Math.max(maxZeros, Math.min(t2, t5));
                }
            }
            
            // Path going right then down
            for (let k = j; k < n; k++) {
                for (let l = 0; l <= i; l++) {
                    const t2 = rowTwos[i][k + 1] - rowTwos[i][j] + colTwos[i + 1][k] - colTwos[l][k];
                    const t5 = rowFives[i][k + 1] - rowFives[i][j] + colFives[i + 1][k] - colFives[l][k];
                    maxZeros = Math.max(maxZeros, Math.min(t2, t5));
                }
            }
        }
    }
    
    return maxZeros;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

代码实现

复杂度分析

相关题目