class Solution {
public:
int minimumSplits(vector<int>& nums) {
}
};
2436. 使子数组最大公约数大于一的最小分割数
给定一个由正整数组成的数组 nums。
将数组拆分为 一个或多个 不相连的子数组，如下所示:
1。返回拆分后可获得的子数组的最小数目。
注意:
子数组 是数组的连续部分。
示例 1:
输入: nums = [12,6,3,14,8] 输出: 2 解释: 我们可以把数组分成子数组:[12,6,3] 和 [14,8]。 - 12、6、3 的最大公约数是 3，严格大于 1。 - 14 和 8 的最大公约数是 2，严格来说大于 1。 可以看出，如果不拆分数组将使最大公约数 = 1。
示例 2:
输入: nums = [4,12,6,14] 输出: 1 解释: 我们可以将数组拆分为一个子数组，即整个数组。
提示:
1 <= nums.length <= 20002 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-16 23:20:30
func gcd(a, b int) int {
if a%b == 0 {
return b
}
return gcd(b, a%b)
}
func minimumSplits(nums []int) int {
ans := 0
g := nums[0]
for i := 1; i < len(nums); i++ {
g = gcd(g, nums[i])
if g == 1 {
ans++
g = nums[i]
}
}
return ans + 1
}
java 解法, 执行用时: 1 ms, 内存消耗: 40.1 MB, 提交时间: 2023-10-16 23:20:15
class Solution {
// 求最大公约数
public int minimumSplits(int[] nums) {
int length = nums.length;
int ans = 1;
int a = 0;
for (int i = 0; i < length; i++) {
int num = nums[i];
a = gcd(a, num);
if (1 == a) {
a = 0;
i--;
ans++;
}
}
return ans;
}
public int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-16 23:19:57
impl Solution {
pub fn minimum_splits(nums: Vec<i32>) -> i32 {
let mut ans = 1;
let mut g = nums[0];
for n in &nums {
g = Self::gcd(g, *n);
if g == 1 {
ans += 1;
g = *n;
}
}
ans
}
fn gcd(mut n: i32, mut m: i32) -> i32 {
assert!(n != 0 && m != 0);
while m != 0 {
if m < n {
let t = m;
m = n;
n = t;
}
m = m % n;
}
n
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 8.5 MB, 提交时间: 2023-10-16 23:19:28
class Solution {
public:
int minimumSplits(vector<int>& nums) {
int cnts = 1;
int g = nums[0];
for (auto& val: nums) {
g = gcd(g,val);
if (g == 1) {
cnts += 1;
g = val;
}
}
return cnts;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-16 23:19:18
class Solution:
def minimumSplits(self, nums: List[int]) -> int:
# 只有当目前gcd为1的时候，才切割开，并且重新计算gcd
cnts = 1
g = nums[0]
for val in nums:
g = math.gcd(g,val)
if g == 1:
cnts += 1
g = val
return cnts