LeetCode 397. 整数替换
目录
题目描述
题意分析
给一个正整数，每一步可以做两件事之一：如果它是偶数就必须除以 $2$，如果它是奇数就可以选择加 $1$ 或减 $1$。问最少几步能把它变成 $1$。
值得注意的是，偶数时没有选择余地，唯一的操作就是除以 $2$；只有在奇数时才存在分叉。所以整个决策空间其实只有「每次碰到奇数，往上还是往下」这一串二元选择。
数据范围是 $1 \le n \le 2^{31}-1$，上界正好是
int的最大值。这是一个明确的溢出信号：当 $n$ 取到 $2^{31}-1$ 时，如果选择加 $1$，结果会超出int表示范围，必须用更宽的整型（或者改写成除法形式）来承载中间值。边界方面：$n = 1$ 时已经是目标，答案为 $0$；$n = 2$ 只需一步；$n = 3$ 是个需要单独看待的小数，稍后会解释原因。
解法：贪心 + 位运算
核心思路
最直接的做法是搜索：写一个递归函数，偶数时唯一递归，奇数时对加 $1$ 和减 $1$ 各递归一次取较小值。这样是正确的，配上记忆化后规模也能接受，但每次奇数分叉都要展开两条分支，实现上还要处理哈希表和溢出。
换成位运算的视角看，这个问题的本质是「把二进制表示消到只剩最高位的 $1$」。除以 $2$ 就是右移一位，只要末位是 $0$ 就是白赚的一步；加一或减一则是在调整末尾的比特形态，目的是制造更多可以连续右移的 $0$。这样一来问题就变成：每次碰到奇数，怎么调整才能让末尾出现最多的连续 $0$。
观察奇数的低两位就够了。任何奇数模 $4$ 只能是 $1$ 或 $3$。若 $n \equiv 1 \pmod 4$，二进制末两位是
01，减 $1$ 后末两位变成00，能连着右移两次；而加 $1$ 只会让末两位变成10，右移一次后又是奇数。若 $n \equiv 3 \pmod 4$，末两位是11，加 $1$ 会产生向上的进位，至少把末两位清成00（进位还可能继续向上传播、清掉更多位）；而减 $1$ 只得到10，同样只能移一次。所以贪心规则是：末两位为01就减，为11就加。这条规则有唯一一处例外。$n = 3$ 的二进制是
11，按规则应当加 $1$ 得到 $4$，再走三步到 $1$，共 $3$ 步；但直接减 $1$ 得到 $2$，再一步到 $1$，只要 $2$ 步。原因是 $3$ 太小，加 $1$ 带来的进位收益还没来得及兑现就撞到了终点。因此把 $n = 3$ 单独特判成减 $1$。循环的不变量是：
steps始终等于从原始 $n$ 走到当前值 $x$ 所用的最少步数，而 $x$ 每一轮都严格向 $1$ 靠近。用 64 位整型承载 $x$，即可安全处理 $n = 2^{31}-1$ 时的加一。
解题步骤
- 把输入拓宽成 64 位整型再开始迭代。这不是洁癖，而是必要的：$n$ 可以取到
int上界，而贪心在该值处恰好会选择加 $1$，用 32 位会直接溢出成负数导致死循环。- 用
while (x > 1)驱动循环，计数器steps每轮加一。以 $x > 1$ 而非 $x \ne 1$ 作条件，语义更稳；$n = 1$ 时循环体不执行，自然返回 $0$。- 每轮先用
x & 1判断奇偶。偶数直接x >>= 1，因为题目规定偶数没有别的选项，也不存在更优解可谈。- 奇数时先看是不是 $3$，是则减 $1$。这是全题唯一的特判，来源是「进位收益兑现不了」这一小数例外。
- 其余奇数用
x & 3取低两位。结果为 $1$（即 $x \equiv 1 \pmod 4$）时减 $1$，让末两位归零从而连移两次；结果为 $3$ 时加 $1$，触发进位以清出至少两个末尾零、且进位越长收益越大。- 循环结束返回
steps。由于每轮要么直接右移，要么调整后下一轮必定能右移，$x$ 的量级持续下降，循环必然终止。以
n = 11走一遍：初始 $x = 11$（二进制1011），steps = 0。第一轮 $x$ 为奇数且不等于 $3$，x & 3等于 $3$（末两位11），执行加一得 $x = 12$（1100），steps = 1。第二轮 $x$ 为偶数，右移得 $x = 6$（110），steps = 2。第三轮仍是偶数，右移得 $x = 3$（11），steps = 3。第四轮 $x$ 为奇数且恰好等于 $3$，命中特判执行减一得 $x = 2$，steps = 4；若这里不特判而按x & 3 == 3加一，会得到 $4$ 并额外多走一步。第五轮 $x$ 为偶数，右移得 $x = 1$，steps = 5。此时 $x$ 不再大于 $1$，循环结束返回 $5$。核对路径 $11 \to 12 \to 6 \to 3 \to 2 \to 1$ 恰好五步，另一条最优路径 $11 \to 10 \to 5 \to 4 \to 2 \to 1$ 同样是五步，说明最优解不唯一但步数一致。
代码实现
// 奇数时，若 n == 3 或 n % 4 == 1，选择 n - 1。
class Solution {
public int integerReplacement(int n) {
long x = n;
int steps = 0;
while (x > 1) {
if ((x & 1) == 0) {
x >>= 1;
} else {
if (x == 3 || (x & 3) == 1) {
x--;
} else {
x++;
}
}
steps++;
}
return steps;
}
}
// 奇数时，若 n == 3 或 n % 4 == 1，选择 n - 1。
func integerReplacement(n int) int {
x := int64(n)
steps := 0
for x > 1 {
if x&1 == 0 {
x >>= 1
} else {
if x == 3 || x&3 == 1 {
x--
} else {
x++
}
}
steps++
}
return steps
}
复杂度分析
- 时间复杂度：$O(\log n)$。每两轮循环至少发生一次右移——奇数轮调整后必定得到偶数，下一轮必定右移——所以 $x$ 的二进制位数每两步至少减少一位，循环轮数不超过 $2\log_2 n$，每轮只做常数次位运算。
- 空间复杂度：$O(1)$。整个过程只维护一个 64 位的当前值和一个步数计数器，没有递归栈也没有记忆化表。
关键点总结
- 判断「加一还是减一」不需要看整个数，只看二进制低两位就够了。把决策所需的信息压缩到最小范围，是位运算类贪心的通用套路。
- 贪心的收益要能量化。这里的量化标准是「本次调整后能连续右移几次」，
01减一得两次、11加一得至少两次且进位越长越多，比较清晰，因此贪心站得住。- 小规模例外必须单独枚举验证。$n = 3$ 之所以破例，是因为它离终点太近，进位带来的长期收益没有兑现窗口；这类「渐近最优但小数失效」的现象在贪心题里很常见。
- 数据范围贴着类型上界时要立刻警惕溢出。本题上界 $2^{31}-1$ 恰好会走加一分支，是出题人刻意埋的坑。
- 面试视角：先给出记忆化搜索版本证明思路正确，再给出位运算贪心版本展示优化能力，是这题最稳妥的作答顺序。直接上贪心而说不清 $n=3$ 的来历，容易被追问卡住。
- 面试视角：面试官常问「怎么证明贪心正确」。可以用「奇数只有两种模 $4$ 余数，逐一比较两种选择后续能省的右移次数」这套穷举式论证作答，比空谈「让末尾零更多」有说服力。
易错点总结
- 错误写法：用
int承载中间值 → 输入 $2^{31}-1$ 时低两位是11会走加一分支，结果溢出成 $-2^{31}$，while (x > 1)立刻退出并返回错误的小步数。- 错误写法：漏掉 $n = 3$ 的特判 → $3$ 的低两位是
11会被加成 $4$，走 $3 \to 4 \to 2 \to 1$ 共 $3$ 步，正确答案是 $3 \to 2 \to 1$ 的 $2$ 步。- 错误写法：把贪心规则记反，即 $x \equiv 1 \pmod 4$ 时加一、$x \equiv 3 \pmod 4$ 时减一 → 对 $n = 7$ 会走 $7 \to 6 \to 3 \to 2 \to 1$ 共 $4$ 步，虽与最优步数相同，但对 $n = 5$ 会走 $5 \to 6 \to 3 \to 2 \to 1$ 共 $4$ 步，正确答案是 $3$ 步。
- 错误写法：奇数时一律减一 → 对 $n = 7$ 得到 $7 \to 6 \to 3 \to 2 \to 1$ 共 $4$ 步恰好正确，但对 $n = 15$ 会走 $15 \to 14 \to 7 \to 6 \to 3 \to 2 \to 1$ 共 $6$ 步，最优是 $15 \to 16 \to 8 \to 4 \to 2 \to 1$ 的 $5$ 步。
- 错误写法：奇数时一律加一 → 对 $n = 5$ 会走 $5 \to 6 \to 3 \to 4 \to 2 \to 1$ 共 $5$ 步，最优是 $5 \to 4 \to 2 \to 1$ 的 $3$ 步。
- 错误写法：用
x % 2 == 1判断奇偶且x为有符号类型时未排除负值 → 一旦发生溢出，负奇数的取模结果是 $-1$ 而非 $1$，奇偶分支判断失效，进入不可预期的分支。- 错误写法：循环条件写成
x != 1且中途允许 $x$ 变成 $0$ → 若误在 $x = 1$ 时执行减一，$x$ 变成 $0$ 后永远碰不到 $1$，程序死循环。- 错误写法：
x & 3写成x & 2或x % 4 == 1时忘记x已是奇数的前提 → 前者取到的是次低位而非低两位，判定条件整体错位；后者若对偶数也套用会误判分支。- 错误写法：递归写法中不加记忆化且对奇数双向展开 → 对接近 $2^{31}$ 的输入，递归树在每个奇数处分叉，重复子问题极多，运行时间不可接受。
- 错误写法：把答案定义成「操作次数不含最后一次」或返回
steps - 1→ 对 $n = 8$ 会返回 $2$，正确答案是 $3$；每一次除以 $2$ 都算一步，不存在免费的收尾。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 991. 坏了的计算器 | 中等 | 同为加减与倍数的最少操作，但正推分叉过多需倒推化为确定过程 |
| 650. 两个键的键盘 | 中等 | 最少操作次数与质因数分解相关，贪心依据来自因子而非比特 |
| 191. 位1的个数 | 简单 | 低位比特的观察与消除，n & (n-1) 是同一类技巧的起点 |
| 231. 2 的幂 | 简单 | 判断二进制中是否只有一个 $1$，是本题终止条件的极简形态 |
| 342. 4的幂 | 简单 | 需要额外约束 $1$ 所在位的奇偶性，考察对低两位掩码的运用 |