题目地址:https://leetcode.com/problems/power-of-four/open in new window

Total Accepted: 9305 Total Submissions: 28083 Difficulty: 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?

题目大意

判断一个数是不是4的幂。

解题方法

递归

如果能被4整除,就看除以4之后是否能继续整除。

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

1 2 3 4 5 6 7 8 9 10 11

AC:2ms

迭代

和递归同样的原理。

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

1 2 3 4 5 6 7 8 9 10

效率凑活。

位运算

查了一下,发现还有更好的方法。就是判断二进制中1出现的位数是不是在奇数位。用0101 0101 ……来进行排除。16进制数为:0x55555555。

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

1 2 3 4 5 6 7

Java代码如下:

public class Solution {
    public boolean isPowerOfFour(int num) {
        return num > 0 && (num & (num - 1)) ==0  && (num & 0x55555555) !=0;
    }
}

1 2 3 4 5

函数法

判断取以4为底的log之后,强转成int,再取上4的幂是不是原来的数字。

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and (4 ** (int(math.log(num, 4)))) == num

1 2 3 4 5 6 7

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发