2023-03-26:给定一个二维数组matrix, 每个格子都是正数,每个格子都和上、下、左、右相邻。 你可以从任何一个格子出发,走向相邻的格子, 把沿途的数字乘起来,希望得到的最终数字中,结尾的0

本文主要是介绍2023-03-26:给定一个二维数组matrix, 每个格子都是正数,每个格子都和上、下、左、右相邻。 你可以从任何一个格子出发,走向相邻的格子, 把沿途的数字乘起来,希望得到的最终数字中,结尾的0,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2023-03-26:给定一个二维数组matrix,
每个格子都是正数,每个格子都和上、下、左、右相邻。
你可以从任何一个格子出发,走向相邻的格子,
把沿途的数字乘起来,希望得到的最终数字中,结尾的0最多,
走的过程中,向左走或者向右走的拐点,最多只能有一次。
返回结尾最多的0,能是多少。
1 <= 行、列 <= 400。

答案2023-03-26:

解题思路

本题需要求出从任意位置出发,最多能有多少个结尾0。为了方便计算,可以先将矩阵中每个数分解成2和5的因子,然后通过前缀和预处理出每个位置上、左方向的2和5的因子数量之和,以便快速计算6个方向上的因子数量之和。接着遍历每个位置,分别计算6个方向上的因子数量之和,并取其中的最小值,最后返回所有最小值中的最大值即可。

具体来说,对于一个位置(i,j),可以计算它的左、右、上、下4个方向的2和5的因子数量之和,以及两个斜方向的2和5的因子数量之和共6个值。然后取这6个值中的最小值,就是从该位置出发,在该方向上能够得到的最多结尾0的数量。遍历所有位置,取最大值即可。

需要注意的是,由于只能有一次向左或向右的拐点,因此在计算左和右方向上的因子数量之和时,需要分别计算到该行左边界和右边界的因子数量之和,然后再通过减法计算出中间部分的因子数量之和。

时间复杂度

本算法需要对矩阵中每个数进行分解质因数,时间复杂度为O(n ^ 2log(max(matrix)));两层循环分别对n和m进行遍历,时间复杂度为O(nm);因此总时间复杂度为O(n^2log(max(matrix))+nm)。

空间复杂度

本算法需要维护4个二维数组,每个数组的大小均为n×m,因此空间复杂度为O(nm)。

rust代码

fn most_trailing_zeros(matrix: &Vec<Vec<i32>>) -> i32 {let n = matrix.len(); // 矩阵行数let m = matrix[0].len(); // 矩阵列数// f2[i][j] : matrix[i][j]自己有几个2的因子let mut f2 = vec![vec![0; m]; n];// f5[i][j] : matrix[i][j]自己有几个5的因子let mut f5 = vec![vec![0; m]; n];// 预处理每个位置的2和5的因子数量for i in 0..n {for j in 0..m {f2[i][j] = factors(matrix[i][j], 2);f5[i][j] = factors(matrix[i][j], 5);}}// 计算每个位置上、左方向的2和5的因子数量之和let mut left_f2 = vec![vec![0; m]; n];let mut left_f5 = vec![vec![0; m]; n];let mut up_f2 = vec![vec![0; m]; n];let mut up_f5 = vec![vec![0; m]; n];for i in 0..n {for j in 0..m {left_f2[i][j] = f2[i][j] + if j > 0 { left_f2[i][j - 1] } else { 0 };left_f5[i][j] = f5[i][j] + if j > 0 { left_f5[i][j - 1] } else { 0 };up_f2[i][j] = f2[i][j] + if i > 0 { up_f2[i - 1][j] } else { 0 };up_f5[i][j] = f5[i][j] + if i > 0 { up_f5[i - 1][j] } else { 0 };}}let mut ans = 0;for i in 0..n {for j in 0..m {// 来到(i,j),计算6个方向上的因子数量之和let l2 = if j == 0 { 0 } else { left_f2[i][j - 1] }; // 左边的2因子数量之和 let l5 = if j == 0 { 0 } else { left_f5[i][j - 1] }; // 左边的5因子数量之和let r2 = left_f2[i][m - 1] - left_f2[i][j]; // 右边的2因子数量之和let r5 = left_f5[i][m - 1] - left_f5[i][j]; // 右边的5因子数量之和let u2 = if i == 0 { 0 } else { up_f2[i - 1][j] }; // 上面的2因子数量之和let u5 = if i == 0 { 0 } else { up_f5[i - 1][j] }; // 上面的5因子数量之和let d2 = up_f2[n - 1][j] - up_f2[i][j]; // 下面的2因子数量之和let d5 = up_f5[n - 1][j] - up_f5[i][j]; // 下面的5因子数量之和// 计算6个方向上因子数量之和最小的值let p1 = std::cmp::min(l2 + u2 + f2[i][j], l5 + u5 + f5[i][j]);let p2 = std::cmp::min(l2 + r2 + f2[i][j], l5 + r5 + f5[i][j]);let p3 = std::cmp::min(l2 + d2 + f2[i][j], l5 + d5 + f5[i][j]);let p4 = std::cmp::min(u2 + r2 + f2[i][j], u5 + r5 + f5[i][j]);let p5 = std::cmp::min(u2 + d2 + f2[i][j], u5 + d5 + f5[i][j]);let p6 = std::cmp::min(r2 + d2 + f2[i][j], r5 + d5 + f5[i][j]);// 取6个方向上的最小值中的最大值作为答案ans = std::cmp::max(ans,std::cmp::max(std::cmp::max(p1, p2),std::cmp::max(std::cmp::max(p3, p4), std::cmp::max(p5, p6)),),);}}ans
}// 计算num有几个f的因子
fn factors(num: i32, f: i32) -> i32 {let mut ans = 0;let mut num = num;while num % f == 0 {ans += 1;num /= f;}ans
}fn main() {let matrix1 = vec![vec![5, 8, 3, 1],vec![4, 15, 12, 1],vec![6, 7, 10, 1],vec![9, 1, 2, 1],];println!("{}", most_trailing_zeros(&matrix1)); // 输出:2let matrix2 = vec![vec![7500, 10, 11, 12],vec![6250, 13, 14, 15],vec![134, 17, 16, 1],vec![5500, 2093, 5120, 238],];println!("{}", most_trailing_zeros(&matrix2)); // 输出:13
}

运行结果

在这里插入图片描述

这篇关于2023-03-26:给定一个二维数组matrix, 每个格子都是正数,每个格子都和上、下、左、右相邻。 你可以从任何一个格子出发,走向相邻的格子, 把沿途的数字乘起来,希望得到的最终数字中,结尾的0的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/832252

相关文章

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

Linux下MySQL8.0.26安装教程

《Linux下MySQL8.0.26安装教程》文章详细介绍了如何在Linux系统上安装和配置MySQL,包括下载、解压、安装依赖、启动服务、获取默认密码、设置密码、支持远程登录以及创建表,感兴趣的朋友... 目录1.找到官网下载位置1.访问mysql存档2.下载社区版3.百度网盘中2.linux安装配置1.

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统