231. Power of Two

  • 39.6%

https://leetcode.com/problems/power-of-two/#/description

Given an integer, write a function to determine if it is a power of two.


方法一:

利用 n&(n-1)判断, 时间复杂度O(1)

值得关注的点, 1. 考虑n<=0的情况 2. n&(n-1)为0时是True,所以要加否定 3. 否定符号是 ! 不是 ~

1
2
3
4
5
6
7
class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0) return false;
return !(n&(n-1));
}
};

or

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && !(n&(n-1));
}
};

方法二:

相除法,时间复杂度O(1)

1
return n>0 && (1073741824 % n == 0);

方法三:

迭代,时间复杂度 O(logn)

1
2
3
if(n==0) return false;
while(n%2==0) n/=2;
return (n==1);

方法四:

递归,时间复杂度O(logn)

1
return n>0 && (n==1 || (n%2==0 && isPowerOfTwo(n/2)));

Python one line solution

1
2
3
4
5
6
7
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
return n > 0 and not (n & n-1)

参考资料:

  1. https://discuss.leetcode.com/topic/47195/4-different-ways-to-solve-iterative-recursive-bit-operation-math
  2. https://discuss.leetcode.com/topic/27934/python-one-line-solution
谢谢你,可爱的朋友。