※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 思路：
: 1.一開始直接遞迴乘/除結果吃TLE，所以這題很明顯要用分治去處理。
一開始吃overflow的：
class Solution
{
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n > 0)
return x * myPow(x, n - 1);
if (n < 0)
return 1 / (x * myPow(x, -(n + 1)));
return x;
}
};
: 2.指數的特性，3^11 可以被表示為 3 * 3^2 * 3^8，其中因為拆分完的指數欄位
: 必定能被二進位表示，上式可被轉為：3 * (3^1)^2 * (3^4)^2
: 也就是說我們如果有一個快速的方法可以求出 3 的 2^k 次方，本來需要 n 次乘法
: 才能完成的運算可以被簡化為 O(logn) 次。
後面改成處理奇數偶數
class Solution
{
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n < 0)
return 1 / (x * myPow(x, -(n + 1)));
if (n % 2 != 0)
return x * myPow(x, n - 1);
return myPow(x * x, n / 2);
}
};
變成每次計算一半 n偶數就兩個一半相乘
(x * x, n / 2)
n奇數就是這次的次方減一去算偶數結果 再乘一個自己
(x * (x * x, n-1 / 2))