Skip to content

Latest commit

 

History

History
141 lines (104 loc) · 4.87 KB

README.md

File metadata and controls

141 lines (104 loc) · 4.87 KB

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

English Version

题目描述

给你一个二维整数数组 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 <= 105
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 1000

解法

Python3



Java





TypeScript


function maxTrailingZeros(grid: number[][]): number {
    let m = grid.length,
        n = grid[0].length;
    let r2 = Array.from({ length: m + 1 }, v => new Array(n + 1).fill(0)),
        c2 = Array.from({ length: m + 1 }, v => new Array(n + 1).fill(0)),
        r5 = Array.from({ length: m + 1 }, v => new Array(n + 1).fill(0)),
        c5 = Array.from({ length: m + 1 }, v => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            let cur = grid[i - 1][j - 1];
            let two = 0,
                five = 0;
            while (cur % 2 == 0) two++, (cur /= 2);
            while (cur % 5 == 0) five++, (cur /= 5);
            r2[i][j] = r2[i - 1][j] + two;
            c2[i][j] = c2[i][j - 1] + two;
            r5[i][j] = r5[i - 1][j] + five;
            c5[i][j] = c5[i][j - 1] + five;
        }
    }
    let ans = 0;
    function getMin(i0, j0, i1, j1, i3, j3, i4, j4): number {
        // 横向开始、结束，竖向开始、结束
        const two = c2[i1][j1] - c2[i0][j0] + r2[i4][j4] - r2[i3][j3];
        const five = c5[i1][j1] - c5[i0][j0] + r5[i4][j4] - r5[i3][j3];
        return Math.min(two, five);
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            const leftToTop = getMin(i, 0, i, j, 0, j, i - 1, j),
                leftToBotton = getMin(i, 0, i, j, i, j, m, j),
                rightToTop = getMin(i, j, i, n, 0, j, i, j),
                rightToBotton = getMin(i, j, i, n, i - 1, j, m, j);
            ans = Math.max(
                leftToTop,
                leftToBotton,
                rightToTop,
                rightToBotton,
                ans,
            );
        }
    }
    return ans;
}


...