算法训练-贪心

2024-01-09 12:28:23

?题目:

#397整数替换. - 力扣(LeetCode)

题目描述

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

  1. 如果?n?是偶数,则用?n / 2替换?n?
  2. 如果?n?是奇数,则可以用?n + 1n - 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

提示:

  • 1 <= n <= 2^{_{31}}- 1

解题

? ? 如果拿到的是偶数,那我们只能执行 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,所以执行两步的公式是\frac{n+1}{2}。我们可以用位运算 (n >> 1) + 1 来等效替代。那(n-1)然后再除2这两步也能简化为位运算吗?答案是可以的,\frac{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的情况的归类,然后再转换为位运算进行解题以提高速度。

文章来源:https://blog.csdn.net/werewolfwerewolf/article/details/135467408
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。