难度: Medium
给定一个正整数 n ，你可以做如下操作：
n 是偶数，则用 n / 2替换 n 。n 是奇数，则可以用 n + 1或n - 1替换 n 。返回 n 变为 1 所需的 最小替换次数 。
示例 1：
输入：n = 8 输出：3 解释：8 -> 4 -> 2 -> 1
示例 2：
输入：n = 7 输出：4 解释：7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1
示例 3：
输入：n = 4 输出：2
提示：
1 <= n <= 231 - 1运行时间: 24 ms
内存: 0.0 MB
class Solution:
def integerReplacement(self, n: int) -> int:
count = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
if n & 2 and n != 3:
n += 1
else:
n -= 1
count += 1
return count
这个题解采用迭代的方式求解整数替换问题。通过循环对给定的整数 n 进行操作，每次循环根据 n 的奇偶性选择不同的操作。当 n 为偶数时，直接除以2；当 n 为奇数时，判断 n 的二进制表示的次低位是否为1（即 n&2 是否为真），如果是的话（排除 n=3 的特殊情况），就给 n 加1，否则就给 n 减1。循环进行直到 n 变为1，记录操作次数并返回。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def integerReplacement(self, n: int) -> int:
count = 0
while n != 1:
if n % 2 == 0:
n //= 2 # 如果 n 是偶数，直接除以2
else:
if n & 2 and n != 3: # 如果 n 的二进制表示次低位是1，且不等于3
n += 1 # 给 n 加1
else:
n -= 1 # 否则给 n 减1
count += 1 # 操作次数加1
return count # 返回最终的操作次数
在处理奇数时检查二进制表示的次低位是否为1是为了选择最优的操作以最快达到偶数，进而实现除以2的操作。如果次低位为1（除了n=3的特例），这意味着n+1会导致连续的两个位变为0（例如，从'11'变为'100'），从而在后续操作中减少必要的加减操作。相反，如果次低位为0，n-1直接移除一个低位的1，也能更快地达到偶数。这种策略在多数情况下能减少总的操作次数，尽管不能保证每一步都是全局最优解。
对于n=3的特殊情况，如果选择加1变为4，之后的操作需要两步（4->2->1），而选择减1变为2，只需要一步（2->1）。因此，选择减1可以立即减少操作次数，加快算法的执行效率。这个特例处理显示了算法设计中针对具体数值的优化考虑，以减少特定情境下的操作次数。
在每次操作时，对n进行加1或减1的决策依据是尽快将n转变为偶数以便执行除以2的操作。决策的原则是，如果n为奇数且次低位为1（n&2为真），则n+1能够消除低位的1并可能产生更多的0，从而在之后的操作中减少次数。如果次低位为0，n-1直接去除一个1，更快达到偶数。这种策略通常能快速减少操作次数，尽管它依赖于局部最优而不是全局最优决策。
这种迭代方法主要基于局部最优决策，并不保证全局最小操作次数。要改进算法以确保全局最优，可以考虑使用动态规划或记忆化递归，这样可以在每个步骤中考虑多种可能的操作（加1或减1），并保存中间结果以避免重复计算。这种方法可以评估所有可能的路径，并选择实际上导致最小操作次数的路径。