class Solution {
public:
int minOperations(vector<int>& nums) {
}
};
2654. 使数组所有元素变成 1 的最少操作次数
给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：
0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。
两个正整数的最大公约数指的是能整除这两个数的最大正整数。
示例 1：
输入：nums = [2,6,3,4] 输出：4 解释：我们可以执行以下操作： - 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。 - 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。 - 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。 - 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2：
输入：nums = [2,10,6,14] 输出：-1 解释：无法将所有元素都变成 1 。
提示：
2 <= nums.length <= 501 <= nums[i] <= 106原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-05-05 17:01:09
class Solution:
def minOperations(self, nums: List[int]) -> int:
if gcd(*nums) > 1:
return -1
n = len(nums)
cnt1 = sum(x == 1 for x in nums)
if cnt1:
return n - cnt1
min_size = n
a = [] # [GCD，相同 GCD 闭区间的右端点]
for i, x in enumerate(nums):
a.append([x, i])
# 原地去重，因为相同的 GCD 都相邻在一起
j = 0
for p in a:
p[0] = gcd(p[0], x)
if a[j][0] != p[0]:
j += 1
a[j] = p
else:
a[j][1] = p[1]
del a[j + 1:]
if a[0][0] == 1:
# 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中
min_size = min(min_size, i - a[0][1])
return min_size + n - 1
java 解法, 执行用时: 2 ms, 内存消耗: 40.2 MB, 提交时间: 2023-05-05 17:00:54
class Solution {
public int minOperations(int[] nums) {
int n = nums.length, gcdAll = 0, cnt1 = 0;
for (int x : nums) {
gcdAll = gcd(gcdAll, x);
if (x == 1) ++cnt1;
}
if (gcdAll > 1) return -1;
if (cnt1 > 0) return n - cnt1;
int minSize = n;
var g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点]
for (int i = 0; i < n; ++i) {
g.add(new int[]{nums[i], i});
// 原地去重，因为相同的 GCD 都相邻在一起
var j = 0;
for (var p : g) {
p[0] = gcd(p[0], nums[i]);
if (g.get(j)[0] == p[0])
g.get(j)[1] = p[1]; // 合并相同值，下标取最小的
else g.set(++j, p);
}
g.subList(j + 1, g.size()).clear();
if (g.get(0)[0] == 1)
// 这里本来是 i-g.get(0)[1]+1，把 +1 提出来合并到 return 中
minSize = Math.min(minSize, i - g.get(0)[1]);
}
return minSize + n - 1;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-05-05 17:00:39
func minOperations(nums []int) int {
n, gcdAll, cnt1 := len(nums), 0, 0
for _, x := range nums {
gcdAll = gcd(gcdAll, x)
if x == 1 {
cnt1++
}
}
if gcdAll > 1 {
return -1
}
if cnt1 > 0 {
return n - cnt1
}
minSize := n
type result struct{ gcd, i int }
a := []result{}
for i, x := range nums {
for j, r := range a {
a[j].gcd = gcd(r.gcd, x)
}
a = append(a, result{x, i})
// 去重
j := 0
for _, q := range a[1:] {
if a[j].gcd != q.gcd {
j++
a[j] = q
} else {
a[j].i = q.i // 相同 gcd 保存最右边的位置
}
}
a = a[:j+1]
if a[0].gcd == 1 {
// 这里本来是 i-a[0].i+1，把 +1 提出来合并到 return 中
minSize = min(minSize, i-a[0].i)
}
}
return minSize + n - 1
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-05-05 17:00:16
func minOperations(nums []int) int {
n, gcdAll, cnt1 := len(nums), 0, 0
for _, x := range nums {
gcdAll = gcd(gcdAll, x)
if x == 1 {
cnt1++
}
}
if gcdAll > 1 {
return -1
}
if cnt1 > 0 {
return n - cnt1
}
minSize := n
for i := range nums {
g := 0
for j, x := range nums[i:] {
g = gcd(g, x)
if g == 1 {
// 这里本来是 j+1，把 +1 提出来合并到 return 中
minSize = min(minSize, j)
break
}
}
}
return minSize + n - 1
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.9 MB, 提交时间: 2023-05-05 17:00:00
class Solution {
public int minOperations(int[] nums) {
int n = nums.length, gcdAll = 0, cnt1 = 0;
for (int x : nums) {
gcdAll = gcd(gcdAll, x);
if (x == 1) ++cnt1;
}
if (gcdAll > 1) return -1;
if (cnt1 > 0) return n - cnt1;
int minSize = n;
for (int i = 0; i < n; ++i) {
int g = 0;
for (int j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g == 1) {
// 这里本来是 j-i+1，把 +1 提出来合并到 return 中
minSize = Math.min(minSize, j - i);
break;
}
}
}
return minSize + n - 1;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-05-05 16:59:45
# 计算最短的gcd=1的子数组
class Solution:
def minOperations(self, nums: List[int]) -> int:
if gcd(*nums) > 1:
return -1
n = len(nums)
cnt1 = sum(x == 1 for x in nums)
if cnt1:
return n - cnt1
min_size = n
for i in range(n):
g = 0
for j in range(i, n):
g = gcd(g, nums[j])
if g == 1:
# 这里本来是 j-i+1，把 +1 提出来合并到 return 中
min_size = min(min_size, j - i)
break
return min_size + n - 1