LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.12
• 题目：2654. 使数组所有元素变成1的最少操作次数
• 难度：中等
• 标签: 数组、数学、贪心、最大公约数

1. 题目理解

问题描述

给你一个下标从 0 开始的正整数数组 nums。你可以对数组执行以下操作任意次： 选择一个满足 0 <= i < n - 1 的下标 i，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数（GCD）。 请返回使数组 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. 解题思路

核心观察

• 存在1的情况：若数组中已有1，每个非1元素可通过与相邻1的GCD操作变为1，操作次数为“数组长度 - 1的个数”。
• 整体GCD>1的情况：若所有元素的公共GCD大于1（如[2,4,6]的GCD为2），则无法通过操作得到1，直接返回-1。
• 无1但整体GCD=1的情况：需先找到最短的“GCD为1的子数组”（通过该子数组生成1），再将1扩散到整个数组。

算法步骤

1. 统计1的个数与整体GCD：遍历数组，统计1的数量num1，并迭代计算所有元素的公共GCD。
2. 快速判断特殊情况：
   • 若num1 > 0，返回n - num1；
   • 若整体GCD > 1，返回-1。
3. 寻找最短GCD为1的子数组：枚举所有可能的子数组，计算其累积GCD，找到长度最小且GCD为1的子数组minLen。
4. 计算最终操作次数：生成1的操作次数（minLen - 1） + 扩散1的操作次数（n - 1），即minLen + n - 2。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int remainder = a % b; 
            a = b; 
            b = remainder; 
        }
        return a; 
    }
    public int minOperations(int[] nums) {
        int res=0;
        int count1=0;
        for(int i:nums){
            if(i==1){count1++;}
        }
        if(count1==nums.length){return 0;}
        if(nums.length==1){
          return -1;
        }
        int[] arr = new int[nums.length-1];
        for(int i=0;i<nums.length-1;i++){
            int temp=gcd(nums[i],nums[i+1]);
            arr[i]=temp;
            if(temp==1){return nums.length-count1;}
        }
        return -1;
    }
}

4. 代码优化说明

官方最优解通过贪心+最短GCD子数组实现更全面的逻辑覆盖：

class lc3600_lc3699.lc3660.Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int num1 = 0;
        int g = 0;
        for (int x : nums) {
            if (x == 1) {
                num1++;
            }
            g = gcd(g, x);
        }
        if (num1 > 0) {
            return n - num1;
        }
        if (g > 1) {
            return -1;
        }

        int minLen = n;
        for (int i = 0; i < n; i++) {
            int currentGcd = 0;
            for (int j = i; j < n; j++) {
                currentGcd = gcd(currentGcd, nums[j]);
                if (currentGcd == 1) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }
        return minLen + n - 2;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

• 优化点：
  • 新增“无1但整体GCD=1”的处理逻辑，通过枚举子数组找到最短GCD为1的区间；
  • 时间复杂度优化为O(n² log M)（n为数组长度，M为元素最大值），能覆盖所有场景。

5. 复杂度分析

• 时间复杂度：
  • 统计1和整体GCD：O(n)；
  • 枚举子数组并计算累积GCD：O(n² log M)（n为数组长度，M为元素最大值，log M为GCD计算的时间复杂度）；
  • 整体为O(n² log M)，可处理题目约束下的所有用例。
• 空间复杂度：O(1)（仅用常数额外空间）。

6. 总结

本题的核心是利用最大公约数（GCD）的性质和贪心策略，分三类场景处理：

• 存在1时，直接计算扩散操作次数；
• 整体GCD>1时，直接返回-1；
• 无1但整体GCD=1时，先找最短GCD为1的子数组生成1，再扩散到全数组。

通过“先判断特殊情况，再处理一般情况”的思路，结合GCD的迭代计算和子数组枚举，可高效得到最少操作次数。该题体现了数学性质在算法题中的关键作用，以及贪心策略对“最小操作次数”类问题的适配性。