Implement pow(x, n).
算法一，二分法
思路：
将指数进行二分后，进行递归。后一半可以利用前一半的结果。
此算法在leetcode上实际执行时间为8ms。
class Solution {
public:
double pow(double x, int n) {
if (!n) return 1;
if (n>0) {
const double result = n % 2 ? x : 1;
const double part = pow(x, n/2);
return result * part * part;
}
else {
const double result = n == INT_MIN ? 1 / x: 1;
n = n == INT_MIN ? n+1 : n;
return result / pow(x, -n);
}
}
};
算法二，进制法
利用进制转换的思路。
例如n=6， 二进制表示为101。 如何转换成10进制呢。
方法之一，就是最低位是否为1，如果为1对其累加其权重。
然后加n向右移一位，重复上面的步骤。
对应此算法中， if (n%2),就是在测试n的最低位是为1.
n /= 2，即将n向右移了一位。
x *= x，则是算其对应的权重。
此算法在leetcode上，实行执行时间为7ms。
class Solution {
public:
double pow(double x, int n) {
if (n>=0) {
double result = 1;
while (n) {
if (n%2) result *= x;
n /= 2;
x *= x;
}
return result;
}
else {
const double result = n == INT_MIN ? 1 / x: 1;
n = n == INT_MIN ? n+1 : n;
return result / pow(x, -n);
}
}
};