0231._Power_of_Two.md

231. Power of Two

难度: Easy

刷题内容

原题连接

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

内容描述

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

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1
Example 2:

Input: 16
Output: true
Explanation: 24 = 16
Example 3:

Input: 218
Output: false

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

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

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(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            	

思路 3 - 时间复杂度: O(1)- 空间复杂度: O(1)******

也是有算法的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

思路 4 - 时间复杂度: O(1)- 空间复杂度: O(1)******

判断是power of two也可以用 2**31 % num == 0

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and 2**31 % n == 0