力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0342. 4 的幂
题目地址(342. 4 的幂)
https://leetcode-cn.com/problems/power-of-four/
题目描述
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.
是 2 的幂次方, 就能保证最低位之外,其他位置有且仅有一个 1
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.
是二的倍数
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 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0283. 移动零
下一个
0349. 两个数组的交集
最近更新
1yr ago
复制链接
内容
题目地址(342. 4 的幂)
题目描述
前置知识
公司
思路
关键点
代码