这题的核心思路很直接：偶数直接除以 2，奇数时在 n + 1 和 n - 1 之间选一个能让后续步骤更少的方向。
贪心 + 位运算（推荐）
class Solution {
public int integerReplacement(int n) {
long m = n;
int count = 0;
while (m != 1) {
if ((m & 1) == 0) {
m >>= 1;
} else if (m == 3 || (m & 3) == 1) {
m–;
} else {
m++;
}
count++;
}
return count;
}
}
要点：
- m & 1 == 0：偶数，直接右移一位，相当于 / 2。
- m == 3：特殊处理，减 1 更优，因为 3 -> 2 -> 1 比 3 -> 4 -> 2 -> 1 少一步。
- (m & 3) == 1：末尾两位是 01，减 1 后能更快出现连续 0，优先减。
- (m & 3) == 3：末尾两位是 11，加 1 能产生更多低位 0，优先加。
- 用 long 是为了避免 n = Integer.MAX_VALUE 时 n + 1 溢出。
时间复杂度：O(log n)
空间复杂度：O(1)
记忆化递归
class Solution {
Map<Integer, Integer> memo = new HashMap<>();
public int integerReplacement(int n) { if (n == 1) return 0; if (!memo.containsKey(n)) { if (n % 2 == 0) { memo.put(n, 1 + integerReplacement(n / 2)); } else { memo.put(n, 2 + Math.min( integerReplacement(n / 2), integerReplacement(n / 2 + 1) )); } } return memo.get(n); }}
这里奇数时把 n + 1、n - 1 后的下一步 / 2 合并成两次操作，所以是 2 + min(…)。
时间复杂度：O(log n)
空间复杂度：O(log n)
面试里如果追求简洁和性能，优先写第一种；如果想体现递归和剪枝思路，可以补上第二种。
需要我帮你把这道题和 LeetCode 375（猜数字大小）放在一起对比，说说两道题在状态压缩思路上的异同吗？
