- Power of Four
Easy
Given an integer n, return true if it is a power of four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4x.
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
Constraints:
-231 <= n <= 231 - 1
class Solution:
def isPowerOfFour(self, n: int) -> bool:
if n == 1:
return True
if n < 4:
return False
return self.isPowerOfFour(n / 4)
通过递归很容易解决, 也很有启发, 注意比能用 n // 4, 应为递归是让n, 不断变小, 同时买次都除以4。
Runtime: 28 ms, faster than 86.12% of Python3 online submissions for Power of Four.
Memory Usage: 14.3 MB, less than 6.51% of Python3 online submissions for Power of Four.
但是题目要求: Follow up: Could you solve it without loops/recursion?
Follow up 感觉很难, 不用这些怎么解决。
一般这类为题通过二进制解决:
4 = 0b100
16 = 0b10000
64 = 0b1000000
可见如果转化为二进制, bin(n)[3:]都是0, int后结果为0, 而且0的个数为偶数。
但是
1 = 0b1, 需要单独考虑
class Solution:
def isPowerOfFour(self, n: int) -> bool:
# if n == 1:
# return True
# if n < 4:
# return False
# return self.isPowerOfFour(n / 4)
# method 2
return n == 1 or n > 0 and int(bin(n)[3:]) == 0 and len(bin(n)[3:]) % 2 == 0
n > 0 必须考虑, 如果n == 0, bin(n)[3:]报错。