算法小知识----11.20----整数替换
整数替换
该题出自力扣的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)); } } 复制代码递归：
贪心:
+1 :+1的前提是能够消除连续一段的 1，需要确保次低位为 1（存在连续段），应当优先使用 +1 操作。有个例外就是，需要额外对 n = 3去判断，因为 0011的话 - 1会比 +1更好
们可以从二进制的角度进行分析：以二进制的最低位0以及1去对比
偶数直接移位
奇数判断，奇数+1 的话，可以消除二进制的一连串1，所以这就需要次低位为1，优先使用n++会更好；反之就-1
因此，对于 n 为奇数所能执行的两种操作:
时间复杂度 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; } 复制代码
作者：Jayhaw_花
链接：https://juejin.cn/post/7032450431338938399