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。

自建示例

先增加再连续减半更短:

输入: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)。