Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?
題目解釋?zhuān)航o一個(gè)整數(shù) n介返，判斷是否為 3 的次方拴事。
挑戰(zhàn)：不用迴圈或遞迴。
週日想透過(guò) LeetCode 練一下手感圣蝎，突然看到這一題刃宵，想說(shuō)也太簡(jiǎn)單了吧。3 的次方徘公，有什麼難的组去？腦袋馬上有著滿滿的想法。
什麼步淹，不可以用迴圈跟遞迴４勇 ？這該從哪切入才好缭裆？
沒(méi)啥想法键闺？先寫(xiě)一個(gè)測(cè)試案例出來(lái)就對(duì)了。
測(cè)試案例如下：
[TestMethod]
public void n_is_3_should_be_true()
{
var n = 3;
Assert.IsTrue(new Solution().IsPowerOfThree(n));
}
產(chǎn)品代碼思路
一開(kāi)始看到 3 的次方澈驼，腦袋就是先想到「各數(shù)字相加辛燥，若能被 3 整除，就代表是 3 的倍數(shù)」。
喂挎塌！這跟 3 的次方?jīng)]有關(guān)係芭橇！
恩榴都，沒(méi)有關(guān)係待锈。那就改成：
- n 除以 3, 若餘數(shù)不為 0，則 return false;
- 若餘數(shù)為 0嘴高，則商數(shù)當(dāng)下一次的 n竿音，再次除以 3 運(yùn)算。
就這麼簡(jiǎn)單拴驮！但不用迴圈或遞迴該怎麼完成呢春瞬？
...
...
... ... ... 沒(méi)有，這算法就是得迴圈或遞迴
思路再繞個(gè)彎套啤，既然是數(shù)學(xué)宽气，從 Math 的角度想有啥可以用的。次方就是指數(shù)潜沦，指數(shù)相對(duì)的就是對(duì)數(shù)抹竹。
那只要找到對(duì)數(shù)的方法就簡(jiǎn)單啦。用 Math.Log() 就可以了止潮。但是 MSDN 的說(shuō)明：Math.Log 方法 (Double, Double) 是回傳 double 的窃判。
因此還需要判斷，這個(gè) double 是否為整數(shù)喇闸。若為整數(shù)袄琳，代表 n 為 3 的次方數(shù)。
如何判斷一個(gè) double 是否為整數(shù)
因?yàn)槲覍?shí)在不是很想用 ToString() 再去判斷有沒(méi)有小數(shù)點(diǎn)燃乍，所以我決定用 mod 1 取餘數(shù)是否為 0 判斷是否為整數(shù)唆樊。
產(chǎn)品代碼如下：
public class Solution
{
public bool IsPowerOfThree(int n)
{
var o = Math.Log(n, 3);
var p = o % 1;
return p == 0;
}
}
通過(guò)測(cè)試。
Double 精準(zhǔn)度問(wèn)題
當(dāng)測(cè)試案例 n 為 243 時(shí)刻蟹，會(huì)發(fā)現(xiàn)期望為 3 的 5 次方逗旁，但 o 的值雖為 5，mod 1 後 p 的值卻為 0.999999舆瘪，如下圖所示：
修正 double 精準(zhǔn)度的問(wèn)題片效，我決定用偷吃步，把 double 轉(zhuǎn)成 decimal 處理英古。產(chǎn)品代碼如下：
public bool IsPowerOfThree(int n)
{
var o = (decimal)Math.Log(n, 3);
var r = o % 1;
return r == 0;
}
通過(guò) n = 243 double 精準(zhǔn)度測(cè)試失敗的問(wèn)題淀衣。
當(dāng) n = 0 會(huì) overflow exception
Math.Log() 當(dāng)傳入 n 為 = 0 時(shí)，會(huì)拋 overflow exception召调，因?yàn)?n 只要是整數(shù)都可以傳入膨桥。所以直接針對(duì) n 的範(fàn)圍作限制與判斷蛮浑。產(chǎn)品代碼如下：
public class Solution
{
public bool IsPowerOfThree(int n)
{
if (n <= 0) return false;
var o = (decimal)Math.Log(n, 3);
var r = o % 1;
return r == 0;
}
}
重構(gòu)：inline variable
產(chǎn)品代碼如下：
public class Solution
{
public bool IsPowerOfThree(int n)
{
if (n <= 0) return false;
return (decimal)Math.Log(n, 3) % 1 == 0;
}
}
結(jié)論
難得有一題 LeetCode 兩行程式碼就搞定了，有趣只嚣。
透過(guò) LeetCode 的練習(xí)沮稚，總能練習(xí)思路跟探索你平時(shí)可能不會(huì)用到的 API 。
練功就是這樣册舞，你看練詠春的打木人樁蕴掏，他不痛嗎？敵人可能站在那邊不動(dòng)讓他打嗎环础？練到?jīng)]有槍頭也可以捅進(jìn)去就對(duì)了囚似！
心智開(kāi)越多地圖剩拢，你未來(lái)能用的武器就越多线得，誰(shuí)知道未來(lái)會(huì)碰到什麼樣的需求呢？腦袋跟寫(xiě) code 都是需要練習(xí)的徐伐，code for fun!!
