這是悅樂書的第204次更新亿扁，第215篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級別的第71題（順位題號是326）政溃。給定一個整數(shù)酱畅，寫一個函數(shù)來確定它是否為3的冪挪凑。例如：
輸入：27
輸出：true
輸入：0
輸出：false
輸入：9
輸出：true
輸入：45
輸出：false
跟進(jìn)：你可以不使用任何循環(huán)/遞歸嗎析恢？
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8键兜，環(huán)境是win7 64位系統(tǒng)凤类，使用Java語言編寫和測試。
02 第一種解法
新建一個變量普气，只要其小于n谜疤，依次乘上3，最后比較兩數(shù)是否相等现诀。當(dāng)然夷磕，你也可以做除法。
public boolean isPowerOfThree(int n) {
long m = 1;
while (m < n) {
m *= 3;
}
return m == n;
}
03 第二種解法
使用遞歸的方法仔沿。當(dāng)n等于0的時候坐桩，返回false，當(dāng)n等于1的時候封锉，返回true绵跷。當(dāng)n大于1的時候，先判斷其對3取余是否等于 0成福，如果等于0碾局，則將n除以3再調(diào)用自己。最后返回false奴艾。
public boolean isPowerOfThree2(int n) {
if (n == 0) {
return false;
}
if (n == 1) {
return true;
}
if (n > 1) {
return n%3 == 0 && isPowerOfThree2(n/3);
}
return false;
}
04 第三種解法
將第二種解法的遞歸換成迭代的方式也可以净当。
public boolean isPowerOfThree3(int n) {
if (n == 0) {
return false;
}
if (n == 1) {
return true;
}
while (n%3 == 0) {
n /= 3;
}
return n == 1;
}
05 第四種解法
利用取余。一般的思路是對3取余蕴潦，但是這只能判斷n是否是3的倍數(shù)像啼，而不能保證是3的冪次方。但是我們可以反過來對n取余潭苞，借助1162261467這個整數(shù)忽冻，因為它是3的19次方，是int類型范圍內(nèi)3能夠取到的最大冪次方數(shù)萄传。只要n是3的冪次方甚颂，1162261467對n取余都會返回0。
public boolean isPowerOfThree4(int n) {
return n > 0 && 1162261467%n == 0;
}
06 第五種解法
利用數(shù)學(xué)中的對數(shù)算法秀菱。以下是推理步驟：
3^X == N
log (3^X) == log N
X log 3 == log N
X == (log N) / (log 3)
如果n是3的冪次方振诬，那么將兩數(shù)取對數(shù)后再做除法，得到的是一個以冪次方為整數(shù)位衍菱，以0位小數(shù)位的double類型數(shù)赶么，那么對其取整再和自身做減法，那么它的絕對值肯定是無限接近于0的脊串。
public boolean isPowerOfThree5(int n) {
double lg = Math.log(n)/Math.log(3);
return Math.abs(lg-Math.round(lg)) <= 0.00000000000001;
}
07 第六種解法
借助包裝類Integer的toString方法辫呻。
Integer.toString(int par1, int par2)清钥，par1表示要轉(zhuǎn)成字符串的數(shù)字，par2表示要轉(zhuǎn)成的進(jìn)制表示放闺。我們可以將n轉(zhuǎn)成3進(jìn)制的數(shù)祟昭，那么只要是3的冪次方，轉(zhuǎn)換成3進(jìn)制字符串后怖侦，就是一個以1開頭尾隨k個0的字符串篡悟。
public boolean isPowerOfThree6(int n) {
if (n <= 1) {
return n == 1;
}
return Integer.toString(n, 3).matches("10*");
}
08 第七種解法
將int類型范圍內(nèi)所有3的冪次方整數(shù)放入一個HashSet中，然后判斷n是否在HashSet中匾寝。
public boolean isPowerOfThree7(int n) {
HashSet<Integer> set = new HashSet<>(Arrays.asList(1, 3, 9, 27,
81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441,
1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467));
return set.contains(n);
}
09 小結(jié)
算法專題目前已連續(xù)日更超過兩個月搬葬，算法題文章71+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】艳悔、【算法】急凰、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集猜年。
以上就是全部內(nèi)容抡锈，如果大家有什么好的解法思路鄙漏、建議或者其他問題逢净，可以下方留言交流觅赊，點贊灶挟、留言、轉(zhuǎn)發(fā)就是對我最大的回報和支持腾夯！
