本文共 1162 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到将给定的正整数 n 化简为 1 所需的最少操作次数。我们可以执行以下操作：如果 n 是偶数，则将其除以 2；如果 n 是奇数，则可以选择将其加 1 或减 1。目标是通过这些操作以最少的步骤将 n 化简为 1。

方法思路

这种方法的核心在于优先选择能将 n 化简为偶数的操作，从而减少后续步骤。通过检查 n+1 和 n-1 是否是 2 的幂，我们可以快速找到最优操作方向。

解决代码

class Solution:
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0
        steps = 0
        while n != 1:
            if n % 2 == 0:
                n = n // 2
                steps += 1
            else:
                # 判断n-1是否是2的幂
                if (n - 1) & (n - 2) == 0:
                    n -= 1
                    steps += 1
                # 判断n+1是否是2的幂
                elif (n + 1) & n == 0:
                    n += 1
                    steps += 1
                else:
                    # 两者都不是，随便选一个
                    n -= 1
                    steps += 1
        return steps

代码解释

这种方法确保了我们在每一步都选择最优操作，从而保证最少步骤数。

转载地址：http://qkxx.baihongyu.com/