這是悅樂書的第205次更新桥狡，第216篇原創(chuàng)
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第72題（順位題號是342）。給定一個整數(shù)（帶符號的32位）数冬，寫一個函數(shù)來檢查它是否為4的冪。例如：
輸入：16
輸出：true
輸入：5
輸出：false
跟進：你可以在沒有循環(huán)/遞歸的情況下解決它嗎晶框？
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8软族，環(huán)境是win7 64位系統(tǒng)敦冬，使用Java語言編寫和測試兜喻。
02 第一種解法
特殊情況：當num小于等于1時，直接返回num和1是否相等的結(jié)果索赏。
正常情況：先判斷對4取余是否等于0，如果等于0贴彼，則num除以4繼續(xù)循環(huán)潜腻，最后判斷num是否等于1。
public boolean isPowerOfFour(int num) {
if (num <= 1) {
return num == 1;
}
while (num%4 == 0) {
num /= 4;
}
return num == 1;
}
03 第二種解法
使用遞歸的方式器仗，判斷邏輯和第一種解法一致融涣。
public boolean isPowerOfFour2(int num) {
if (num <= 1) {
return num == 1;
}
if (num > 1 ) {
return num%4 == 0 && isPowerOfFour2(num/4);
}
return false;
}
04 第三種解法
利用Integer.toString(int par1, int par2)方法童番，將num轉(zhuǎn)成4進制字符串，然后匹配以1開頭且尾隨k(k>=0)個0的正則威鹿。
public boolean isPowerOfFour3(int num) {
return num > 0 && Integer.toString(num, 4).matches("10*");
}
05 第四種解法
將4的所有冪次方整數(shù)放入一個HashSet中剃斧，然后判斷num是否被包含在其中。
public boolean isPowerOfFour4(int num) {
Set<Integer> set = new HashSet<>(Arrays.asList(1, 4, 16, 64, 256, 1024, 4096, 16384, 65536,
262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824));
return num > 0 && set.contains(num);
}
06 第五種解法
使用數(shù)學(xué)運算中的對數(shù)忽你。
4^X == N
log (4^X) == log N
X log 4 == log N
X == (log N) / (log 4)
如果num是4的冪次方幼东，那么將兩數(shù)取對數(shù)后再做除法，得到的是一個以冪次方為整數(shù)位科雳，以0位小數(shù)位的double類型數(shù)根蟹，那么對其取整再和自身做減法，那么它的絕對值肯定是無限接近于0的糟秘。
public boolean isPowerOfFour5(int num) {
double d = Math.log(num)/Math.log(4);
return Math.abs(d - Math.round(d)) <= 0.00000000001;
}
07 第六種解法
如果num是4的冪次方简逮，那么其二進制數(shù)會滿足兩個條件：
只會有一個1。
后面尾隨0的個數(shù)是偶數(shù)個蚌堵。
第一個條件借助包裝類Integer的bitCount方法买决，第二個條件依舊借助這個方法，但是對象變成了num-1吼畏，統(tǒng)計完1的位數(shù)后督赤，對2取余，判斷1的個數(shù)是否為偶數(shù)泻蚊。
public boolean isPowerOfFour6(int num) {
return num > 0 && Integer.bitCount(num) == 1 && Integer.bitCount(num-1)%2 == 0;
}
08 小結(jié)
算法專題目前已連續(xù)日更超過兩個月躲舌，算法題文章72+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】性雄、【算法】没卸、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集秒旋。
以上就是全部內(nèi)容约计，如果大家有什么好的解法思路、建議或者其他問題迁筛，可以下方留言交流煤蚌，點贊、留言细卧、轉(zhuǎn)發(fā)就是對我最大的回報和支持尉桩！
