整数替换

[xiwenAndlejian]

397.整数替换

题目

给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。 n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1

示例 2:

输入:
7

输出:
4

解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1

解答

循环对数进行处理：

如图所示：

• 对于偶数我们仅需进行n / 2 或者 n >> 1 操作

• 对于奇数，有n+1与n-1两种方式，这就需要做出抉择选择最佳方案，使得n变为1所需的次数最小

流程分析

第一步：如果 n 为1则返回 0，反之执行第二步。

第二步：分辨数的奇偶，由偶数二进制表达式为0，而奇数为1 => 当 n & 1 == 0时，n为偶数。偶数进行第三步，奇数进行第四步。

第三步：n >>> 1，计数加一，将得到的数带入第一步中执行。PS：注意这里使用的是逻辑右移（LSR），即无符号右移，左侧补0。

第四步：对奇数进行处理，选择最佳方案。

如何选择对数的处理方式使得替换次数最少？

分析奇数的二进制表达式，根据上文末尾一位为1：

• 连续的1，eg：XXX0111
• 非连续的1，eg：XXX01

:warning:：这里由于通过第一步的校验（n != 1），因此前置位XXX中一定有一位为1

分别对上述两类奇数进行+1和-1操作：

• 对连续的1进行+1：多个1合并为一个。eg：0111 + 1 = 1000，后续仅需三次移位替换
• 对连续的1进行-1：1的个数减一。eg：0111 - 1 = 0110，后续至少需要两次移位替换，以及额外的-1操作
• 对非连续的1进行+1：将末尾1往左移动一位，1的个数不变。eg：0101 + 1 = 0110，后续同上
• 对非连续的1进行-1：1的个数减一，eg：0101 - 1 = 0100，后续仅需两次移位替换

所以可以看出，对于奇数处理的最优替换：

• 连续的1：执行+1操作
• 非连续的1：执行-1操作

:memo:对于末尾仅连续两位1的数（除 3 以外），两个操作后续后续所需要的替换次数是一致的。

:memo:对数 3 ，执行-1操作会优于+1操作。

回到流程修改第四步内容：

1. 判断末尾1是非连续：n & 3 == 1，取最后两位，如果为1表示非连续。
   1. 非连续且n==3：-1操作
   2. 连续：+1操作
2. 计数加一

代码

public int integerReplacement(int n) {
    // 校验 n 为正整数
    if (n <= 0) return 0;
    int count = 0;
    while (n != 1) {
        if ((n & 1) == 0) {
            n >>>= 1;
        } else {
            if (n == 3 || (n & 3) == 1) {
                n -= 1;
            } else {
                n += 1;
            }
        }
        count++;
    }
    return count;
}

:memo:处理0x7fff_ffff（Integer.MAX_VALUE）时，由于末尾为连续1，会执行加一操作变为0x8000_0000（Integer.MIN_VALUE），符号位为1，如果此时执行算术右移（ASR），左侧会补符号位1产生异常。因此这里只能使用逻辑右移。