Skip to content

231 Power of Two

231. Power of Two

题目:

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

难度:

Easy

思路：

power of two 那是这个数字的binary 表示一定只有一个1

套用以前的代码leetcode191

这样会超时

class Solution(object):
    def isPowerOfTwo(self, n): # 此法超时
        """
        :type n: int
        :rtype: bool
        """
        cnt = 0
        while n != 0:
            n &= n - 1
            cnt += 1
        return cnt == 1

跟power of three一样递归，可以AC

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        if n == 1:
            return True
        if n % 2 == 0:
            return self.isPowerOfTwo(n/2)
        return False

也是有算法的wikipedia page

The binary representation of integers makes it possible to apply a very fast test to determine whether a given positive integer x is a power of two:

positive x is a power of two ⇔ (x & (x − 1)) is equal to zero.

注意特殊case 0的处理

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n & (n-1) == 0 if n != 0 else False
回到顶部