骗外包有机会转正，从那天以后他每天主动加班到2点

今天我们来聊一个有趣的算法题：整数替换。如果你刚好也在刷题，那么你可能已经见过这个题目，或者说它已经成为了面试中比较常见的考点。好了，废话不多说，我们直接进入正题。

问题是这样的：给定一个整数 n，我们需要不断地将 n 替换为两个数的差，直到 n 变成 1。每次替换的操作是：

• 如果 n 是偶数，那么就将 n 替换为 n / 2。
• 如果 n 是奇数，那么就将 n 替换为 n + 1 或者 n - 1，然后选择哪个更合适。

问题其实就是考察我们如何将这个数“削减”到 1。看似简单，但其中的策略和算法的选择，可就有一点技巧了。

我在看到这个题目时，脑袋里第一个反应是——递归？？？

思路解析

首先，我们需要弄清楚这道题最重要的两点：奇偶性判断和优化。这两者会影响我们的算法设计。

1. 奇数的处理：对于奇数来说，我们面临的两个选择是：

   那么问题就来了，什么时候选择 n + 1，什么时候选择 n - 1 呢？

   这是一个经典的博弈问题，最常见的做法是判断 n 的二进制形式来决定。举个例子，假如 n 是一个奇数，我们首先看它的二进制表示。如果它末尾是 11（也就是二进制末尾有两个连续的1），那就倾向于选择 n - 1，因为这样会把一个大的 1 拿掉，剩下的位数可能减少得更快。而如果末尾是 01 或 00，就倾向于选择 n + 1，因为这样可以通过加一让高位的进位操作消除。

• n + 1
• n - 1

算法实现

说了这么多，我们就来实现一下这个算法。实现过程中，可以采用 贪心算法，每一步选择最优的操作来减少 n，同时我们使用 位运算 来优化 n 的判断和更新。至于复杂度嘛，可以证明这个算法的时间复杂度是 O(log n)。

代码如下：

def integerReplacement(n: int) -> int:
    # 用一个变量记录替换次数
    steps = 0
        while n != 1:
        # 如果 n 是偶数
        if n % 2 == 0:
            n //= 2  # 直接除以 2
        else:
            # 如果 n 是奇数
            if (n == 3) or (n & 2 == 0):  # 3 是特殊情况，直接减一比较好
                n -= 1
            else:
                n += 1
        steps += 1
        return steps

代码讲解

1. 奇偶性判断：首先通过 n % 2 == 0 判断 n 是偶数还是奇数。如果是偶数，直接除以 2。

2. 对于奇数的优化处理：

• 特殊情况：当 n == 3 时，直接减 1 会更好，因为 3 的二进制形式 11 直接减 1 就能变成 2。
• 其他奇数时，通过位运算 n & 2 == 0 判断当前 n 的二进制末尾是 01 还是 11，根据这个来选择加一还是减一。

性能分析

这个算法的时间复杂度是 O(log n)，因为每次我们通过除 2 或者加减 1 操作都会大大减小 n，最多需要 log n 次操作。看似有点复杂的操作，实际上通过巧妙的选择和优化，每次替换都能最大程度减少计算量。

总结

这道题的核心在于对奇数如何处理的优化，特别是对于如何选择 n + 1 或 n - 1 这个决策过程。通过位运算，我们能够更快速地判断出哪种方式能更高效地将 n 缩小到 1。

通过这种贪心的思路，我们每一步都选择最优的操作来减少 n，最终确保能在最短的步数内达到目标。

在解决这类问题时，不仅要考虑最基本的操作，还要用一些技巧来优化，避免不必要的重复计算。