---

0397. 整数替换

• 标签：贪心、位运算、记忆化搜索、动态规划
• 难度：中等

题目链接

• 0397. 整数替换 - 力扣

题目大意

描述：

给定一个正整数 $n$ ，你可以做如下操作：

1. 如果 $n$ 是偶数，则用 $n / 2$ 替换 $n$。
2. 如果 $n$ 是奇数，则可以用 $n + 1$ 或 $n - 1$ 替换 $n$。

要求：

返回 $n$ 变为 $1$ 所需的「最小替换次数」。

说明：

• $1 \le n \le 2^{31} - 1$。

示例：

• 示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

• 示例 2：

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

解题思路

思路 1：贪心算法

这道题的核心思想是：对于奇数 $n$，选择能更快减少二进制表示中 $1$ 的个数的操作。

解题步骤：

1. 偶数处理：如果 $n$ 是偶数，直接除以 $2$，即 $n = n / 2$。
2. 奇数处理：如果 $n$ 是奇数，需要选择 $n + 1$ 或 $n - 1$：
   • 如果 $n = 1$，直接返回 $0$（已经到达目标）。
   • 如果 $n = 3$，选择 $n - 1$（特殊情况）。
   • 如果 $n$ 的二进制表示末尾是 $11$（即 $n \bmod 4 = 3$），选择 $n + 1$。
   • 否则选择 $n - 1$。

关键点：

• 对于偶数，除以 $2$ 是最优选择，因为能直接减少一位。
• 对于奇数，我们希望尽可能快地减少二进制表示中 $1$ 的个数。
• 当 $n \bmod 4 = 3$ 时，$n + 1$ 会产生更多的连续 $0$，有利于后续的除法操作。
• 特殊情况：$n = 3$ 时，$3 \to 2 \to 1$ 比 $3 \to 4 \to 2 \to 1$ 更优。

算法正确性：

设 $f(n)$ 表示将 $n$ 变为 $1$ 的最小操作次数：

• 当 $n$ 为偶数时：$f(n) = 1 + f(n/2)$。
• 当 $n$ 为奇数时：
  • 如果 $n = 1$：$f(1) = 0$。
  • 如果 $n = 3$：$f(3) = 1 + f(2) = 2$。
  • 如果 $n \bmod 4 = 3$：选择 $n + 1$ 能更快地减少 $1$ 的个数。
  • 否则：选择 $n - 1$ 是更优的。

思路 1：代码

class Solution:
    def integerReplacement(self, n: int) -> int:
        count = 0
        
        while n != 1:
            if n % 2 == 0:
                # 偶数：直接除以2
                n //= 2
            else:
                # 奇数：根据情况选择+1或-1
                if n == 3:
                    # 特殊情况：3 -> 2 -> 1 比 3 -> 4 -> 2 -> 1 更优
                    n -= 1
                elif n % 4 == 3:
                    # 如果n mod 4 = 3，选择+1能产生更多连续的0
                    n += 1
                else:
                    # 否则选择-1
                    n -= 1
            count += 1
        
        return count

思路 1：复杂度分析

• 时间复杂度：$O(\log n)$，每次操作至少将 $n$ 减半，最多需要 $O(\log n)$ 次操作。
• 空间复杂度：$O(1)$，只使用了常数额外空间。