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;
    }

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

上一篇:主流的四种限流策略,我都可以通过redis实现


下一篇:11.17 模拟赛