LeetCode - 幂次问题

LeetCode231 - 二的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 :

输入: 1
输出: true
解释: 20 = 1

位运算方法

二的幂次方很容易想到二进制数组，显然只要判断 n&(n-1) == 0 就可知是否为二的幂次

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;
    }
}

递归法

1. n<=0 返回false
2. 只要能够整除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不是质数，所以不能再使用整数限制法。

4的幂次方的数的二进制满足两个条件:

1. 有且仅有一个1
2. 这个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 位的数量

本文链接：