0397. Integer Replacement ========================= 题目信息 -------- :题号: 0397 :难度: Medium :主题: 正整数、允许替换、最少操作、32 位上界 :原题: `LeetCode 0397 `_ :重点: 偶数只能除以 2、奇数可加一或减一、每次算一步、输入上界的加一中间值可能超过 32 位 题目重述 -------- 给定正整数 ``n``。一次操作中,若当前整数为偶数,只能把它替换为其一半;若当前整数为奇数,可以选择把它替换为 ``n + 1`` 或 ``n - 1``。重复执行操作直到整数变为 ``1``,返回所需的最少操作次数。 输入 ``n`` 位于 ``[1, 2^31-1]``。对奇数加一是题目允许的合法操作,因此当当前值等于 32 位有符号整数上界时,中间值可能暂时达到 ``2^31``;这不改变操作规则。初始值已经是 ``1`` 时答案为 ``0``。 自建示例 -------- 先增加再连续减半更短: .. code-block:: text 输入:n = 15 输出:5 解释:可以执行 15 -> 16 -> 8 -> 4 -> 2 -> 1,共五次操作。 初始值已经达到目标: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp 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)``。