342.Power of Four
检查数字n是不是4的x次方倍
如果n=4^x则回传true，否则回传false
题:1 答:true
题:5 答:false
题:16答:true
Follow up: 不用递回或循环完成题目
First thought:
一开始就写了一个循环
如果数字比较小 就*4再比一次
不过看到Follow up之后决定想一下最佳解
Approach:
后来看到4这个数字跟2有关
想到可以用binary去解
4的次方倍 换成binary一定是1+偶数个0
例如:
1=1
4=100
16=10000
64=1000000
所以把数字转成binary后用正规表达式去检验就好了
TS code:
function isPowerOfFour (n: number): boolean {
const binary = (n).toString(2)
const reg = /^1(00)*$/
const result = reg.exec(binary)
return result !== null
}
一行版本
function isPowerOfFour (n: number): boolean {
return /^1(00)*$/.exec(n.toString(2)) !== null
}
不过我蛮好奇正规表达式本身的时间复杂度是多少
该不会我写一个*或+他就会跑循环吧?