Leetcode 2的幂 3的幂 4的幂总结

题目列表：

2的幂
3的幂
4的幂

2的幂

题目大意

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

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

示例2：

输入: 16
输出: true
解释: 24 = 16

示例3：

输入: 218
输出: false

方法一：暴力

采用暴力循环的方法，逐个尝试2的n次幂，直到找到结果。这题会超时。

public boolean isPowerOfTwo(int n) {
        if(n==1) return true;
        int cur = 1;
        while(cur<n) {
            cur *=2;
            if(cur==n) return true;
        }
        return false;
    }

方法二：打表加二分查找

首先打表记录2^31以内的所有整数，然后对这张整数表进行二分查找。

 private void form() {
        res[0] = 1;
        for(int i=1;i<31;i++)
            res[i]=res[i-1]*2;
    }
public boolean isPowerOfTwo(int n) {
        form();
        if(n!=1 && n%2==1) return false;
        int low = 0;
        int high = 30;
        while(low<high) {
            int mid = (low+high)>>1;
            if(res[mid]==n) return true;
            else if(res[mid] > n)
                high = mid -1;
            else if(res[mid] < n)
                low = mid+1;
        }
        return res[low]==n?true:false;
    }

运行时间3ms，击败87.42%。

方法三：位运算

2^n 和 2^n-1相与一定为0。

public boolean isPowerOfTwo(int n) {
        if(n<=0) return false;
        return (n&(n-1))==0?true:false;
    }

运行时间2ms,击败98.23%。

3的幂

题目大意

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例1：

输入: 27
输出: true

示例2：

输入: 0
输出: false

方法一：暴力法

用迭代的方法，当n>=3时，判断n%3是否等于0，如果可以被3整除，n/=3，继续循环。

 public boolean isPowerOfThree(int n) {
         while(n>=3 && n%3==0) 
            n /=3 ;
        return n==1?true:false;
    }

运行时间18ms,击败96.31%。

方法二：log运算

3^x = n，解方程求出x,判断x是否为整数。

public boolean isPowerOfThree(int n) {
        return (Math.log10(n)/Math.log10(3))%1==0;      
}

注意：这里用log10这个方法可能会有精度问题，如算出4.999999999，下面我们用epsilon进行修正。

public boolean isPowerOfThree(int n) {
     double epsilon = 0.0000000000001;
     return (Math.log(n) / Math.log(3) + epsilon) % 1 
       <= 2 * epsilon;
}

运行时间24ms,击败63.98%。

方法三：最大数法

因为题目给的测试用例是整数范围，我们只需要求得4^x <= Integer.MAX_VALUE，即这个4^{x为多少。这样所有4}j的数，一定是4^x的因数。

public boolean isPowerOfThree(int n) {
        return n>0 && 1162261467%n==0;
    }

运行时间18ms,击败96.31%。

方法四：基数转换

采用Integer.toString(num,base)这个方法，可以将num转化为以base为基数的字符串，然后对这个字符串利用正则表达式判断。最高位必定为1，之后跟着若干个0，并且无其他元素。

 public boolean isPowerOfThree(int n) {
        return Integer.toString(n,3).matches("^10*$");      
    }

运行时间72ms,击败59.75%。

4的幂

题目大意

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

思路

与上述两题思路一致，也可以采用位运算，log运算，迭代的方法等，这里只介绍位运算方法。

位运算

用一张图直观地表示4^x这些数的特点。

image.png

1.首先这个数必须是2的幂次方。
可用(n&(n-1))==0判断是否为2的幂次方。
2.它的二进制表示中奇数位为 1 ，偶数位为 0
符合这两个条件的二进制数是：
1010101010101010101010101010101
用16进制表示为0x55555555

 public boolean isPowerOfFour(int num) {
        if (num <= 0) return false;
        if ((num &(num-1))!=0) return false;  //不是2^n
        return (0x55555555 & num)==num;
    }

运行时间2ms ，击败97.43%。