LeetCode-每日一题 397. 整数替换 [Java实现] [极速]

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

1. 如果 n 是偶数，则用 n / 2替换 n 。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。

n 变为 1 所需的最小替换次数是多少？

示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

分析所有的可能我们能列出如下情况

• 传入 n 是偶数 -> 计数+1，n /= 2
• n 是奇数
  • n % 4 == 1，通过分析我们可知将 n -= 1 所得结果不会比 n+= 1 更坏，故可将 n -= 1，计数+1
  • n % 4 == 3
    • n == 3，此时无需继续运算，计数+2 即为正确答案
    • n != 3，通过分析我们可知将 n += 1 所得结果不会比 n -= 1 更坏，故可将 n += 1，计数+1

    public static int integerReplacement(long n) {
        int times = 0;
        while (n > 1) {
            if ((n & 1) != 0) { // 奇数
                if (n % 4 == 1) {
                    ++ times;
                } else { // == 3
                    if (n == 3) {
                        times += 2;
                        break;
                    } else {
                        ++ times;
                        ++ n;
                    }
                }
            }
            n >>= 1;
            ++ times;
        }
        return times;
    }