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
}
不過我蠻好奇正規表達式本身的時間複雜度是多少
該不會我寫一個*或+他就會跑迴圈吧?