本文共 1140 字，大约阅读时间需要 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/