算法小知识—-11.20—-整数替换

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战

整数替换

该题出自力扣的397题——整数替换（中等题），题解消化于评论区

审题

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

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

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1
复制代码

• 简单概括就是，一个整数， 计算需要 / 2 多少次才能成为1

• 有几个小技巧，例如 / 2 可以直接写成 >> 1(右移位)，毕竟 /2 的底层也是右移位

• 方法挺多：

  • 递归：

    • 判断是否为1，为1则返回

    • 判断是否为偶数，偶数直接 右移位 + 1

    • 判断是否奇数，奇数 = 2+Math.min（递归 n/2，递归 n-1 / 2）

    • 偶数+1是因为本身的这次方法；奇数+2是因为有两步操作，一个是+1/-1，另一个是移位

    • class Solution {
          public int integerReplacement(int n) {
              if (n == 1) {
                  return 0;
              }
              if (n % 2 == 0) {
                  return 1 + integerReplacement(n / 2);
              }
              return 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
          }
      }
      复制代码

• 贪心:

  • 们可以从二进制的角度进行分析：以二进制的最低位0以及1去对比
  • 偶数直接移位
  • 奇数判断，奇数+1 的话，可以消除二进制的一连串1，所以这就需要次低位为1，优先使用n++会更好；反之就-1
  • 因此，对于 n 为奇数所能执行的两种操作:
    • +1 :+1的前提是能够消除连续一段的 1，需要确保次低位为 1（存在连续段），应当优先使用 +1 操作。有个例外就是，需要额外对 n = 3去判断，因为 0011的话 - 1会比 +1更好
  • 时间复杂度 O（logn）
  • 空间复杂度 O(1)

编码

总的来说，移位二进制是需要掌握的，但是相对而言，用递归会更好理解一些

    public static int integerReplacement(int n) {
        int num = 0;
        long max = n;
        while (max != 1){
            if (max % 2 == 0){
                max = max >>1;
            }else if (max != 3 && ((max >> 1) & 1) == 1 ){
                max++;
            }else {
                max--;
            }
            num++;
        }
        return num;
    }
复制代码