LeetCode - 幂次问题
LeetCode231 - 二的幂
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
示例 :
输入: 1
输出: true
解释: 20 = 1
位运算方法
二的幂次方很容易想到二进制数组,显然只要判断 n&(n-1) == 0
就可知是否为二的幂次
10进制 | 二进制 | n-1 | n&(n-1) |
---|---|---|---|
$$2^0 = 1$$ | 0001 | 0000 | 0000 |
$$2^1 = 2$$ | 0010 | 0001 | 0000 |
$$2^2 = 4$$ | 0100 | 0011 | 0000 |
$$2^3 = 8$$ | 1000 | 0111 | 0000 |
…… |
Java代码如下
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
整数限制法
由题目已给的条件可知n是int类型,而int的范围在 $$-2^{31}$$ ~ $$2^{31}-1$$ ,所以在int范围内最大的应该是 $$2^{30}$$ ,所以只需判断 1073741824 % n == 0
即可
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && 1073741824 % n == 0;
}
}
递归法
- n<=0 返回false
- 只要能够整除3就继续,直到n=1为止,否则返回false
class Solution {
public boolean isPowerOfThree(int n) {
if(n <= 0) return false;
else if(n == 1)return true;
else return (n%2 ==0) ? isPowerOfThree(n/2) : false;
}
}
LeetCode326 - 三的幂
和上一题思路大体相同,但是三次幂的话不能使用二进制来做位运算,整数限制法和递归法依然可用。
LeetCode342 - 四的幂
因为4不是质数,所以不能再使用整数限制法。
10进制 | 二进制 |
---|---|
$$4^0 = 1$$ | 0000 0001 |
$$4^1 = 4$$ | 0000 0100 |
$$4^2 = 16$$ | 0001 0000 |
$$4^3 = 64$$ | 0100 0000 |
…… |
4的幂次方的数的二进制满足两个条件:
- 有且仅有一个1
- 这个1在奇数位上
构造一个二进制数和n做与运算,考虑用0101010 10101010 10101010 10101010 (偶数为1,奇数为0,共31位),转化为10进制是2863311530
代码如下:
class Solution {
public boolean isPowerOfFour(int num) {
if(num < 0) return false;
return ((num & 715827882)==0 && Integer.bitCount(num)==1) ? true : false;
}
}
注:Integer.bitCount
返回指定 int
值的二进制补码表示形式的 1 位的数量