算法训练-贪心
?题目:
题目描述
给定一个正整数?n
?,你可以做如下操作:
- 如果?
n
?是偶数,则用?n / 2
替换?n
?。 - 如果?
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的情况的归类,然后再转换为位运算进行解题以提高速度。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!