LeetCode算法题-Power Of Two(Java实现)
这是悦乐书的第194次更新,第200篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第56题(顺位题号是231)。给定一个整数,写一个函数来确定它是否是2的幂。例如:
输入:1
输出:true
说明:2^0 = 1
输入:16
输出:true
说明:2^4 = 16
输入:218
输出:false
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
此解法是做乘法,新建一个变量,初始值为1,然后循环乘以2,只要该变量小于n,最后判断该变量和n是否相等。
public boolean isPowerOfTwo(int n) {
long m = 1;
while (m < n) {
m = m*2;
}
return m == n;
}
03 第二种解法
此解法是做除法,先用n对2取余数,如果等于0,说明n是偶数,那么除以2,依次循环判断。最后判断是否和1相等。
public boolean isPowerOfTwo2(int n) {
if (n<1) {
return false;
}
while (n%2 == 0) {
n = n/2;
}
return n == 1;
}
04 第三种解法
特殊情况:当n小于1的时候,直接返回false。
正常情况:先将n转化为二进制字符串,然后判断此字符串中的1的个数,如果n是2的幂次方,那么1的个数只可能有一个,即此二进制字符串中1的第一次出现的位置和最后一次出现的位置相等。
public boolean isPowerOfTwo3(int n) {
if (n<1) {
return false;
}
String str = Integer.toBinaryString(n);
return str.indexOf("1") == str.lastIndexOf("1");
}
05 第四种解法
特殊情况:当n小于1的时候,直接返回false。
正常情况:借助包装类Integer,使用其bitCount()方法,统计其二进制数中1的个数,等于1则说明n是2的幂次方,反之则不是。
public boolean isPowerOfTwo4(int n) {
if (n<1) {
return false;
}
return Integer.bitCount(n) == 1;
}
06 第五种解法
特殊情况:当n小于1的时候,直接返回false。
正常情况:与(&)运算的规则是相同的位上均为1时结果为1,如果n是2的2的幂次方,其二进制数是只有一个1的,后面的位都是0,而n-1的二进制数是n的二进制数1变成0,n的二进制数1之后的0变成1,两者进行与(&)运算,其结果是0。比如:
1的二进制数为1,0的二进制数为0,与运算结果为0
2的二进制数为10,1的二进制数为01,与运算结果为0
4的二进制数为100,3的二进制数为011,与运算结果为0
8的二进制数为1000,7的二进制数为0111,与运算结果为0
public boolean isPowerOfTwo5(int n) {
if (n<1) {
return false;
}
return (n&(n-1)) == 0;
}
07 小结
算法专题目前已连续日更超过一个月,算法题文章56+篇,