0342. 4 的幂

题目地址(342. 4 的幂)

题目描述

1
给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。
2
3
示例 1:
4
5
输入: 16
6
输出: true
7
示例 2:
8
9
输入: 5
10
输出: false
11
进阶:
12
你能不使用循环或者递归来完成本题吗?
Copied!

前置知识

  • 数论

公司

  • 百度
  • twosigma

思路

符合直觉的做法是不停除以 4 直到不能整除,然后判断是否为 1 即可。 代码如下:
1
while (num && num % 4 == 0) {
2
num /= 4;
3
}
4
return num == 1;
Copied!
但是这道题目有一个 follow up: “你是否可以不使用循环/递归完成”。因此我们需要换种思路。
我们先来看下,4 的幂次方用 2 进制表示是什么样的.
263.342.power-of-four-1
发现规律: 4 的幂次方的二进制表示 1 的位置都是在奇数位(且不在最低位),其他位置都为 0
我们还可以发现: 2 的幂次方的特点是最低位之外,其他位置有且仅有一个 1(1 可以在任意位置)
我们进一步分析,如果一个数字是四的幂次方,那么只需要满足:
  1. 1.
    是 2 的幂次方, 就能保证最低位之外,其他位置有且仅有一个 1
  2. 2.
    这个 1 不在偶数位置,一定在奇数位置
对于第一点,如果保证一个数字是 2 的幂次方呢? 显然不能不停除以 2,看结果是否等于 1,这样就循环了。 我们可以使用一个 trick, 如果一个数字 n 是 2 的幂次方,那么 n & (n - 1) 一定等于 0, 这个可以作为思考题,大家思考一下。
对于第二点,我们可以取一个特殊数字,这个特殊数字,奇数位置都是 1,偶数位置都是 0,然后和这个特殊数字 求与, 如果等于本身,那么毫无疑问,这个 1 不再偶数位置,一定在奇数位置,因为如果在偶数位置,求与的结果就是 0 了 题目要求 n 是 32 位有符号整形,那么我们的特殊数字就应该是01010101010101010101010101010101(不用数了,一共 32 位)。
Could not load image
263.342.power-of-four-2
如上图,64 和这个特殊数字求与,得到的是本身。 8 是 2 的次方,但是不是 4 的次方,我们求与结果就是 0 了。
为了体现自己的逼格,我们可以使用计算器,来找一个逼格比较高的数字,这里我选了十六进制,结果是0x55555555
263.342.power-of-four
代码见下方代码区。
说实话,这种做法不容易想到,其实还有一种方法。 如果一个数字是 4 的幂次方,那么只需要满足:
  1. 1.
    是二的倍数
  2. 2.
    减去 1 是三的倍数
代码如下:
1
return num > 0 && (num & (num - 1)) === 0 && (num - 1) % 3 === 0;
Copied!

关键点

  • 数论
  • 2 的幂次方特点(数学性质以及二进制表示)
  • 4 的幂次方特点(数学性质以及二进制表示)

代码

语言支持:JS, Python
JavaScript Code:
1
/*
2
* @lc app=leetcode id=342 lang=javascript
3
*
4
* [342] Power of Four
5
*/
6
/**
7
* @param {number} num
8
* @return {boolean}
9
*/
10
var isPowerOfFour = function (num) {
11
// tag: 数论
12
13
if (num === 1) return true;
14
if (num < 4) return false;
15
16
if ((num & (num - 1)) !== 0) return false;
17
18
return (num & 0x55555555) === num;
19
};
Copied!
Python Code:
1
class Solution:
2
def isPowerOfFour(self, num: int) -> bool:
3
if num == 1:
4
return True
5
elif num < 4:
6
return False
7
else:
8
if not num & (num-1) == 0:
9
return False
10
else:
11
return num & 0x55555555 == num
12
13
# 另一种解法:将数字转化为二进制表示的字符串,利用字符串的相关操作进行判断
14
def isPowerOfFour(self, num: int) -> bool:
15
binary_num = bin(num)[2:]
16
return binary_num.strip('0') == '1' and len(binary_num) % 2 == 1
Copied!
复杂度分析
  • 时间复杂度:$O(1)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。