Skip to content

Latest commit

 

History

History
203 lines (150 loc) · 4.47 KB

0342._Power_of_Four.md

File metadata and controls

203 lines (150 loc) · 4.47 KB

342. Power of Four

难度: Easy

刷题内容

原题连接

内容描述

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true
Example 2:

Input: 5
Output: false
Follow up: Could you solve it without loops/recursion?

解题方案

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

继续照抄power of three， recursive

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

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

iterative

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        while num != 1:
            if num % 4 != 0 :
                return False
            else:
                num /= 4
        return True

Follow up: Could you solve it without loops/recursion?

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

  • num & (num-1) == 0代表num的二进制表示中只有一个1
  • len(bin(num)[3:]) % 2 == 0代表num的二进制的那个唯一的一个1后面的0的数量是偶数的，比如bin(4) = 0b100，后面有2个0，说明是4的幂次
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and num & (num-1) == 0 and len(bin(num)[3:]) % 2 == 0

同样的原理，也可以写成下面这样：

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and num & (num-1) == 0 and bin(num)[3:].count('0') & 1 == 0

或者用正则：

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return bool(re.match(r'^0b1(00)*$', bin(num)))

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

纯粹的bit manipulation

  • num & (num-1) == 0代表num的二进制表示中只有一个1
  • 0x55555555是16进制，代表的二进制是0b1010101010101010101010101010101，所有的偶数位deigit都是1，也就是说只有num的二进制是0b1(00)* 类型的，才会始终满足num & 0x55555555 == num
  • 但是0是一个特殊情况，所以我们要让num 不为0，同时4的幂次肯定是大于0的，所以我们直接写``num > 0`
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and num & (num - 1) == 0 and num & 0x55555555 == num

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

判断是power of two也可以用 2**31 % num == 0,但是被模的数只能是正数，所以要加一个num > 0

class Solution:
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and 2**31 % num == 0 and num & 0x55555555 == num

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

num为1肯定返回True

如果num在是power of two的基础上，那么num如果想是power of four，它的个位数肯定是4或者6，因为4, 16, 64, 256，power of four是个位数4和6交替的序列

beats 99.65%

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        digit = num % 10
        return num == 1 or (num & (num-1) == 0 and (digit == 4 or digit == 6))

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

数学证明一波

if num = 4^x, x > 0
then num = 4^(x-1) * 4
then num % 3 = [4^(x-1) * (3+1)] % 3 = 4^(x-1) % 3 = 4^(x-2) % 3 = ... = 1 % 3 = 1

所以如果一个数是4的幂次方，那么mod 3的结果肯定为1

beats 99.65%

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num & (num-1) == 0 and num % 3 == 1