2022

2023-05-11 19:58| 来源: 网络整理| 查看: 265

2022-09-07：给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个原创

福大大架构师每日一题 2023-05-11 16:57:36 博主文章分类：福大大架构师每日一题 ©著作权

文章标签 rust 开发语言后端数组最大公约数文章分类 Python 后端开发

©著作权归作者所有：来自51CTO博客作者福大大架构师每日一题的原创作品，请联系作者获取转载授权，否则将追究法律责任

2022-09-07：给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个子序列本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。计算并返回 nums 的所有非空子序列中不同最大公约数的数目。输入：nums = [5,15,40,5,6]；输出：7。

答案2022-09-07：

n/1 + n/2 + n/3 + n/4 + … + n/n 收敛于 O(N * logN)，N是最大值，当做结论记住。

代码用rust编写。代码如下：

fn main() { let mut arr = vec![5, 15, 40, 5, 6]; let ans = count_different_subsequence_gcds(&mut arr); println!("ans = {}", ans); } const MIN_VALUE: i32 = -1 O(N * logN) fn count_different_subsequence_gcds(nums: &mut Vec) -> i32 { // 找到数组中的最大数！max let mut max = MIN_VALUE; for num in nums.iter() { max = get_max(max, *num); } // 1~max，哪个数有哪个数没有 let mut set: Vec = vec![]; for _ in 0..max + 1 { set.push(false); } for num in nums.iter() { set[*num as usize] = true; } let mut ans = 0; // a是当前想确定，是不是某个子序列的最大公约数，有a！ let mut a = 1; while a b { a } else { b } }

执行结果如下：

2022-09-07：给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个_数组

左神java代码

打赏赞收藏评论分享举报

上一篇：2022-09-14:以下go语言代码输出什么？A：0 0；B：0 1；C：1 1；D：1 0。 package main func main() { println(f(1)) } func

下一篇：2022-09-28：以下go语言代码输出什么？A：1 1；B：1 2；C：2 2；D：不确定。 package main import ( “fmt“ ) func main() { var

【本文地址】

公司简介

联系我们