mirror of
https://github.com/lWolvesl/leetcode.git
synced 2026-01-12 18:08:38 +08:00
39 lines
562 B
Go
39 lines
562 B
Go
package L12
|
||
|
||
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
|
||
}
|