LeetCode算法题-Power Of Two(Java实现)

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+篇,