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);
}
}
解法三:
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}