0397. Integer Replacement¶
题目信息¶
- 题号:
0397
- 难度:
Medium
- 主题:
正整数、允许替换、最少操作、32 位上界
- 原题:
- 重点:
偶数只能除以 2、奇数可加一或减一、每次算一步、输入上界的加一中间值可能超过 32 位
题目重述¶
给定正整数 n。一次操作中,若当前整数为偶数,只能把它替换为其一半;若当前整数为奇数,可以选择把它替换为 n + 1 或 n - 1。重复执行操作直到整数变为 1,返回所需的最少操作次数。
输入 n 位于 [1, 2^31-1]。对奇数加一是题目允许的合法操作,因此当当前值等于 32 位有符号整数上界时,中间值可能暂时达到 2^31;这不改变操作规则。初始值已经是 1 时答案为 0。
自建示例¶
先增加再连续减半更短:
输入:n = 15
输出:5
解释:可以执行 15 -> 16 -> 8 -> 4 -> 2 -> 1,共五次操作。
初始值已经达到目标:
输入:n = 1
输出:0
解释:无需进行任何替换。
奇数时让下一步尽快产生更多二进制零位¶
偶数只能除以 2。奇数若不是 3,比较 n - 1 和 n + 1 的二进制末两位:以 01 结尾时减一会产生更多可连续除以 2 的零位;以 11 结尾时加一会产生这一效果。3 是特例,3 -> 2 -> 1 比 3 -> 4 -> 2 -> 1 更短。
使用 long long 保存当前值,因为 2^31 - 1 加一会超出有符号 32 位范围,但仍在 64 位范围内。
C++ 实现¶
class Solution {
public:
int integerReplacement(int n) {
long long value = n;
int steps = 0;
while (value > 1) {
if ((value & 1) == 0) {
value /= 2;
} else if (value == 3 || (value & 2) == 0) {
--value;
} else {
++value;
}
++steps;
}
return steps;
}
};
代码分析¶
奇数选择使后继值尽可能多地暴露二进制尾部的零,随后可连续使用除二操作;特例 3 修正了“多零位”规则在最小奇数处的例外。每轮显著减少数值,时间复杂度为 O(log n),额外空间为 O(1)。