231. 2 的幂

2021-05-30 LeetCode每日一题

链接:https://leetcode-cn.com/problems/power-of-two/

题目

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。

如果存在一个整数 x 使得 n == 2 ^ x ,则认为 n 是 2 的幂次方。

输入:n = 1
输出:true
解释:2^0 = 1
    
输入:n = 16
输出:true
解释:2^4 = 16
    
输入:n = 3
输出:false
    
输入:n = 4
输出:true
    
输入:n = 5
输出:false
    
-231 <= n <= 231 - 1

分析

解法一:普通循环,超时。

解法二:列出2 ^ 0到2^30次方放到一个数组里,然后判断n是否在数组里。

解法三:2^x表示为二进制数,只有一位为1,其余位都为0,而n & (n - 1),则可以把n的最低位置0,所以利用这个特性,只需要将n和n - 1进行&运算然后判断结果是否为0即可。

编码

解法二:

class Solution {
    public boolean isPowerOfTwo(int n) {
        List<Double> list = Arrays.asList(Math.pow(2, 0), Math.pow(2, 1), Math.pow(2, 2), 			Math.pow(2, 3),	Math.pow(2, 4), Math.pow(2, 5), Math.pow(2, 6), Math.pow(2, 7), 			Math.pow(2, 8), Math.pow(2, 9), Math.pow(2, 10), Math.pow(2, 11), Math.pow(2, 12), 			Math.pow(2, 13), Math.pow(2, 14), Math.pow(2, 15), Math.pow(2, 16), Math.pow(2, 17), 		 Math.pow(2, 18), Math.pow(2, 19), Math.pow(2, 20), Math.pow(2, 21), Math.pow(2, 22), 		  Math.pow(2, 23), Math.pow(2, 24), Math.pow(2, 25), Math.pow(2, 26), Math.pow(2, 27), 		   Math.pow(2, 28), Math.pow(2, 29), Math.pow(2, 30));

        return list.contains((double)n);
    }
}

231. 2 的幂

解法三:

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }

        return (n & (n - 1)) == 0;
    }
}

231. 2 的幂

上一篇:2021-02-20


下一篇:斐波那契数列-->兔子上台阶