LeetCode 397. 整数替换
题目描述
题意分析
从正整数
n出发，偶数只能除以 2，奇数可以加 1 或减 1，每次操作计一步，求到达 1 的最少步数。难点是奇数的方向选择：暂时变大，也可能换来更多次除以 2。
解法：贪心 + 位运算
核心思路
[!blue]
偶数没有选择，直接右移一位。奇数加减 1 后都会变成偶数，下一步都必须除以 2，因此可以比较这两步之后的剩余状态，选择后续代价不更大的方向。
记
f(x)为从x到 1 的最少步数，f(1) = 0、f(2) = 1。由操作规则，f(2k) = 1 + f(k)，而f(2k + 1) = 2 + min(f(k), f(k + 1))，后式适用于大于 1 的奇数。这两个式子还说明：大于 1 的奇数，其最少步数不小于相邻两个偶数。可以从
f(1)、f(2)归纳：若f(k)与f(k + 1)相差至多 1，代入两式后，f(2k + 1)与f(2k)、f(2k + 2)的差都只可能为 0 或 1。于是相邻状态的差仍至多 1，并得到上述奇偶比较结论。对
x = 4k + 1，减一再除二到2k，加一再除二到2k + 1，前者是偶数，因此选减一不劣。对x = 4k + 3且x > 3，两条路分别到2k + 1和2k + 2，所以选加一不劣。对应二进制规则就是：低两位为01时减一，为11时加一，优先创造可继续右移的末尾 0。唯一要单独处理的是 3：减一再除二就已到终点 1，只需两步；加一后还要经过 4、2、1，需要三步。输入为 1 时则无需操作。
解题步骤
- 把输入转为
long或int64，令操作次数为 0。- 只要当前值大于 1，偶数就右移一位。
- 奇数等于 3，或低两位满足
(x & 3) == 1时减一；其余奇数加一。- 每轮累加一次操作，达到 1 时返回次数。
最大输入为
2^31 - 1，选择加一会产生2^31，所以必须先提升类型再运算。虽然加一步会暂时增大数值，但随后必定除以 2，常数次操作后规模就会缩小。
代码实现
// 奇数时，若 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+1))$，调整后可以右移，常数次操作使数值规模缩小。
- 空间复杂度：$O(1)$，当前值与计数。
关键点总结
[!green]
- 贪心选择不必唯一，目标是最少步数而非唯一操作序列。
- 两条奇数分支先各花两步，再用剩余状态的最优步数比较，不是只比较加减后的大小。
- 3 的例外来自减一分支直接到达终点，不能套用一般奇偶比较。
易错点总结
[!yellow]
- 用窄整数承载最大值加一，会回绕成负数。
- 忽略三的例外，会多走一步。
- 奇数一律减一，会错过进位消除末尾连续 1 后，多次直接除以 2 的机会。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 991. 坏了的计算器 | 中等 | 同样可通过反向观察操作减少分支，本题偶数除2、奇数加减1，原题倍增与减1的方向不同。 |
| 1342. 将数字变成 0 的操作次数 | 简单 | 原题奇数只能减1，本题还能加1，因此需要比较后续能连续除2的机会。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！