2654. 使数组所有元素变成 1 的最少操作次数给你一个下标从 0 开始的正整数数组 nums。你可以对数组执行以下操作任意次选择一个满足 0 i n - 1 的下标 i将 nums[i] 或者 nums[i1] 两者之一替换成它们的最大公约数。请你返回使数组 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] 10^6问题分析本题要求通过不断替换相邻元素为它们的最大公约数GCD最终将整个数组变为全 1。操作允许任意次数但需要找到最小操作步数或判断无解。关键点在于• 如果数组中已存在 1则可以利用 1 与相邻数字的 GCD 操作快速将其他元素变为 1。• 若数组中无 1则需先通过若干操作生成一个 1。解题思路情况一数组中已有 1若数组内已有至少一个 1则只需将每个非 1 元素依次变为 1。具体操作是用 1 与相邻元素求 GCD由于 GCD(1, x) 1每次操作可将一个非 1 元素变为 1。因此最少操作次数为 数组长度 n - 1 的个数。情况二数组中无 1若数组中没有 1则需要先通过操作产生一个 1。这里需判断是否有解• 无解条件若整个数组所有元素的最大公约数大于 1则无论进行多少次操作都无法得到 1因为所有数共享一个大于 1 的公因子。• 有解条件若整个数组的 GCD 为 1则一定存在某个连续子数组其所有元素的 GCD 也为 1。我们的目标是找到长度最小的此类子数组。为什么找最小连续子数组因为操作仅限于相邻元素生成 1 的过程相当于将某个连续子数组通过 GCD 操作逐步收缩最终得到一个 1。最小长度的子数组意味着生成 1 所需操作次数最少。设最小子数组长度为 min_length则生成 1 需要 min_length - 1 次操作。生成 1 后再利用该 1 将剩余元素变为 1需要 n - 1 次操作。因此总操作次数为{总操作次数} (min_length - 1) (n - 1)算法步骤统计数组中 1 的个数 cnt。计算整个数组的最大公约数 gcd_all。若 gcd_all 1返回 -1无解。若 cnt 0返回 n - cnt。否则枚举所有连续子数组计算每个子数组的 GCD记录 GCD 为 1 的最短子数组长度 min_length。返回 min_length - 1 n - 1。代码如下↓classSolution{public:intminOperations(vectorintnums){intnnums.size();intcnt0;// 统计1的个数intgcd_allnums[0];// 整个数组的GCDfor(inti0;in;i){if(nums[i]1){cnt;}gcd_allgcd(gcd_all,nums[i]);}// 若整个数组GCD大于1无解if(gcd_all1){return-1;}// 若已有1直接返回n - cntif(cnt0){returnn-cnt;}// 寻找GCD为1的最短连续子数组长度intmin_lengthn;for(inti0;in;i){intcurrent_gcdnums[i];for(intji;jn;j){current_gcdgcd(current_gcd,nums[j]);if(current_gcd1){min_lengthmin(min_length,j-i1);break;// 找到更短子数组后可以提前结束内层循环}}}returnmin_length-1n-1;}};复杂度分析• 时间复杂度O(n²)其中 n 为数组长度。主要开销在于枚举所有连续子数组并计算 GCD。• 空间复杂度O(1)仅使用常数额外空间。总结本题的关键在于识别有解条件并通过寻找最短连续子数组来最小化操作次数。暴力枚举在 n ≤ 50 的约束下是可行的。若数组已含 1则问题简化为线性操作否则需通过子数组 GCD 计算快速定位生成 1 的最优路径。