算法训练-贪心

?题目：

#397整数替换. - 力扣（LeetCode）

题目描述

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

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

返回?n?变为?1?所需的?最小替换次数?。

示例 1：

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

示例 2：

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

示例 3：

输入：n = 4
输出：2

提示：

• 

解题

? ? 如果拿到的是偶数，那我们只能执行 n/2 这一步。如果我们拿到的是奇数，我们有两个选择：(n-1)和(n+1)，无论执行哪个最后都会得到一个偶数。所以可以看出，具体影响结果的步骤在n为奇数的时候。我们需要做的就是让步骤中出现奇数的次数尽可能少。

①解法一：贪心+递归

? ? ? ? 这是最容易想到的解法，也就是用递归一步步枚举，然后取最优解。我们知道只有当n为奇数才是影响结果的关键步骤。

很简单地，能得出下面代码：

    public static int integerReplacement(int n) {
        if (n == 1)
            return 0;
        if (n % 2 == 0){
            return integerReplacement(n >> 1) + 1;
        }else {
            return Math.min(integerReplacement(n+1),integerReplacement(n-1)) + 1;
        }
    }

但如果直接提交这个代码就会发现，其实是不能通过全部测试用例的，出错的测试用例刚好是n为Integer.MAX_VALUE这个极端取值。同时这个值也刚好是奇数，如果对他进行+1，那么就会得到Integer.MIN_VALUE，是一个负数。显然最终会出异常。那我们怎么解决呢？答案是：位运算。因为当n为奇数时，n+1的结果必定是偶数，而偶数的下一步必定也是执行n / 2，所以执行两步的公式是。我们可以用位运算 (n >> 1) + 1 来等效替代。那(n-1)然后再除2这两步也能简化为位运算吗？答案是可以的，两步可以用位运算(n >> 1)替代 （注意，只有n为奇数才能这么替代）这样子我们就对代码完成了优化，使用位运算不仅能解决掉极端取值报错的情况，还能优化步骤，具体AC代码如下：

    public static int integerReplacement(int n) {
        if (n == 1)
            return 0;
        if (n % 2 == 0){
            return integerReplacement(n >> 1) + 1;
        }else {
            //(n+1)/2和(n-1)/2分别用((n>>1)+1)和(n>>1))替代
            return Math.min(integerReplacement((n>>1)+1),integerReplacement(n>>1)) + 2;
        }
    }

②解法二:贪心+归纳

如果将得到的n转换成二进制呢？

我们知道，n / 2 就是相当于将n 的二进制右移一位，也就是 n >> 1。

我们不妨接着枚举n的二进制尾数的种种情况：

n的尾数为011：

? ? ? ? (n+1): 011 -> 100 -> 10 -> 1? ? ? ? ? ? ? ? (n-1)：011 -> 010 -> 01

n的尾数为0111:

? ? ? ? (n+1)：0111 -> 1000 -> 100 -> 10 -> 1? ? ? ? (n-1)：0111 -> 0110 -> 011 -> 010 -> 01

n的尾数为01111:

? ? ? ? (n+1)：10000 -> 1000 -> 100 -> 10 -> 1

? ? ? ? (n-1)：01111 -> 01110 -> 0111 -> 0110 -> 011 -> 010 -> 01

....再列举一两个可以发现，当n的二进制尾数有三个或以上连续的1，那么(n+1)就是划算的，否则就用(n-1)。

得出结论后写代码就轻松很多了

public static int integerReplacement2(int n) {
        long n2 = n;//防止出现n = Integer.MAX_VALUE这种极端的取值，n+1越界
        int sum = 0;
        while (n2 != 1){
            if ((n2 & 1) == 0){//n2为偶数
                n2/=2;
                sum++;
            }else {//n2为奇数
                //n == 3直接sum+=2结束
                if (n2 == 3){
                    sum+=2;
                    break;
                }
                if ((n2 & 3) == 3){// 等效n2 % 4 == 3的情况
                    n2+=1;//n+1
                    sum++;
                } else if ((n2 & 3) == 1) {// 等效n2 % 4 == 1的情况
                    n2-=1;
                    sum++;
                }
            }
        }
        return sum;
    }

至此，这道题也就解完了。如果在力扣看官方解答，其实可以发现他用的是另一种贪心的方法：

③解法三:贪心+归纳

如果n为奇数且n > 3，n % 4只有两种结果：1或者3，当n % 4 == 1时，采取(n-1)，当n % 4 == 3时，采取(n+1)。感兴趣的小伙伴可以自行到? 题解-力扣官方题解? 去看推演步骤。这里重点不是这个解法是怎么推演出来的，而是这个解法与上一个解法(解法二)之间的关联。

解法二与解法三之间的关联

? ? ? ? 在解法二中，我们提到了，n的二进制形式末尾有连续3个或者更多的1时，采用(n+1)。而在解法三中，n % 4 == 3时采用(n+1)。其实这之间是有关联的。不难发现，二进制 100 其实就是4。当n%4时(n > 3)，得到的结果其实就是n的二进制形式的末两位，比如当n的二进制为 XXXX01的形式，那么 n%4肯定是为1的，当n的二进制为 XXXX11的形式，那么 n%4肯定是为3的。所以解法二中所说，n的二进制形式满足末尾有三个或者更多连续的1其实也就等价于n % 4 == 3 (n > 3)。这里之所以强调n > 3是因为如果当n = 3时，采用(n+1)明显不合理，所以n=3是特殊情况不能被归纳进来。

? ? ? ? 其实n的二进制形式的末尾规律并不好发现，我们应该能先发现 n % 4的情况的归类，然后再转换为位运算进行解题以提高速度。