Pow(x,n)實作

這是 LeetCode 第50題：LeetCode Problem 50. Pow(x,n)，初探 LeetCode 寫了兩三題 Easy 後看到這個想說這難度怎麼有 Medium？就稍微寫了一下 Recursive Function，大概就是 myPow(x,n) 處理 base part n=0 傳回1，然後 n > 0 時 return x * myPow(x,n-1)，而 n < 0 時 return 1/myPow(x, n*-1)

submit 後 LeetCode 很不客氣用 n = 232 - 1 ，回給我 time out。被殺個措手不及。

是我太大意了，既然這麼大的數字那能不能用一半一半 log2 n 呢？想了一下指數律就好了不難，xn = ( xn/2 ) * ( xn/2 ) * ( xn%2 )

第二次我就把 recursive part 改成 return myPow(x,n/2) * myPow(x,n/2) * myPow(x, n%2) ，但是仍然 time out 。

這樣都還是逾時真的超乎我想像，但想一想再更精簡一點，用空間換時間，就不要算兩次，我先 double q = myPow(x,n/2) 和 double r = myPow(x,n%2)，然後 return q*q*r ，過了。

但一樣又打了回來，下一個關卡是 LeetCode 用 n = - 232 讓我回家。

我的錯，他是知道有人會在 n < 0 時 return 1/myPow(x, n*-1) 嗎？Integer.MIN_VALUE 變號就直接炸了，確實學了一課。

最後送過是我把 base part 考慮完整一點，n=0 return 1，n=1 return x，n=-1 return 1/x，拿掉 n < 0 的部份，全部交由對半分的遞迴去跑。很感動的第五次給過了。

LeetCode 玩下來會比 CodeWars 多了一個挫敗感，因為 LeetCode 會把失敗的投稿算入，真的要在自己機器上考量萬全再送，不然表現慘不忍睹。好處就是怎麼死的？是因為什麼 input 而失敗？ LeetCode 給得很清楚，可針對症狀下藥，這部份 CodeWars 就常常鬼打牆了。