0数组中等 LeetCode6072. 转角路径的乘积中最多能有几个尾随零

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

描述

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

转角路径 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 向水平方向 或者 向竖直方向 移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 另一个 方向行进：如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。

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

请你从 grid 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。

注意：

水平 移动是指向左或右移动。
竖直 移动是指向上或下移动。

分析

• 题目求尾随零最多的路径，起始就是找那个路径的因子5，2数量更多。
• 路径不会因为延伸到边界而变少，所以默认转弯路径两头都是到边界的。
• 以某一点为转弯点，那么围绕这个转弯点的路径有四条：左上、左下、右上、右下。
• 题目可以理解为遍历二维数组，找出以每个结点为转弯结点的四条路径的因子5，2最大公共数量，记录全局的因子5，2最大公共数量。
• 为了防止越界，方便计算每条路径的因子5，2的数量，建造的数组要比原数组大一圈，这样后面的计算不要考虑[i-1],[j-1]等这样的边界条件。

class Solution {public int maxTrailingZeros(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] fh = new int[m+1][n+1];int[][] fv = new int[m+1][n+1];int[][] th = new int[m+1][n+1];int[][] tv = new int[m+1][n+1];for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){int five = 0;int two = 0;int tmp = grid[i-1][j-1];while(tmp % 5 == 0){five++;tmp /= 5;}tmp = grid[i-1][j-1];while(tmp % 2 == 0){two++;tmp /= 2;}fh[i][j] = fh[i][j-1] + five;fv[i][j] = fv[i-1][j] + five;th[i][j] = th[i][j-1] + two;tv[i][j] = tv[i-1][j] + two;}}int ans = 0;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){//左上ans = Math.max(ans,Math.min(fh[i][j]+fv[i-1][j],th[i][j]+tv[i-1][j]));//左下ans = Math.max(ans,Math.min(fh[i][j]+fv[m][j]-fv[i][j],th[i][j]+tv[m][j]-tv[i][j]));//右上ans = Math.max(ans,Math.min(fh[i][n]-fh[i][j]+fv[i][j],th[i][n]-th[i][j]+tv[i][j]));//右下ans = Math.max(ans,Math.min(fh[i][n]-fh[i][j]+fv[m][j]-fv[i-1][j],th[i][n]-th[i][j]+tv[m][j]-fv[i-1][j]));}}return ans;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！