题目链接：2654. 使数组所有元素变成 1 的最少操作次数
方法一：计算最短的gcd为1的子数组
解题思路
- 本题目标：使得所有的数组元素都变为 \(1\)，通过求相邻元素 \(gcd\) 将其赋值给一方的方式；
- 思路：
- 若想操作数最少，那么就是不为 \(1\) 的数 \(x\) 和 1 求 \(gcd\)，即 \(x = gcd(x, 1)\)，这样一次就可以将 \(x\) 变为 \(1\)；
- 因此现在至于要找最短的 \(gcd\) 为 \(1\) 的子数组，先将其中一个数转换为 \(1\) ，然后将其他不等于 \(1\) 的元素通过一次操作变为 \(1\)；
- 特殊情况：
- 数组整体的 \(gcd\) 不为 \(1\)，说明不管怎么操作都不能出现 \(1\)，那么一定不能变为 \(1\)；
- 数组中已经存在 \(1\)，那么对于已经是 \(1\) 的元素就不需要多余操作。
代码
class Solution {
public:
int minOperations(vector<int>& nums) {
int cnt = 0, g = 0, n = nums.size();
for (int i = 0; i < n; i ++ ) {
if (nums[i] == 1) cnt ++ ;
g = gcd(g, nums[i]);
}
if (g != 1) return -1;
if (cnt > 0) return n - cnt; // 特殊情况
int mn = n;
for (int i = 0; i < n; i ++ ) {
g = nums[i], cnt = 1; // 暴力查找 gcd = 1 的最短子数组
for (int j = i + 1; j < n; j ++ ) {
g = gcd(g, nums[j]);
cnt ++ ;
if (g == 1) {
mn = min(mn, cnt);
break;
}
}
}
return n + mn - 2;
}
};
复杂度分析
时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(1)\)。
方法二：通过gcd性质优化
解题思路
通过迭代的方式计算子数组的 \(gcd\) 并进行去重优化（保持数组的连续性），注意 \(g\) 数组存储的元素含义。
class Solution {
public:
int minOperations(vector<int>& nums) {
int cnt = 0, res = 0, n = nums.size();
for (auto &x : nums) {
if (x == 1) cnt ++ ;
res = gcd(res, x);
}
if (res != 1) return -1;
if (cnt > 0) return n - cnt;
vector<pair<int, int>> g; // {gcd, 相同的gcd的子数组最靠右边的左端点}
int mn = n;
for (int i = 0; i < n; i ++ ) {
g.emplace_back(nums[i], i); // 添加
int j = 0;
for (auto &p : g) {
p.first = gcd(p.first, nums[i]); // 相当于求 [p.second, i] 的 gcd
if (p.first == g[j].first) { // 说明出现相同的 gcd，那么将靠右的左端点复制到 g[j]，跳过 p
g[j].second = p.second;
} else { // 说明出现不相同的 gcd 那么将 P move 到 ++ j 的位置，弥补数组空缺
g[ ++ j ] = move(p);
}
}
g.resize(j + 1);
if (g[0].first == 1) mn = min(mn, i - g[0].second + 1); // 第一个元素的 gcd 值一定最小，因为其结果是从开始到当前位置所有元素的 gcd
}
return n + mn - 2;
}
};
复杂度分析
时间复杂度：\(O(nlogU)\)，\(U = max(nums[0, n - 1])\)；
空间复杂度：\(O(logU)\)。