50. Pow(x, n)
题意：
求x的n次方。
思路：平方加速
萌新肯定就直接转换成加法了，不用想这样肯定是超时的。
若加快运行速度，合适的方法就是在适当的时候平方。
先说一下范围限制的问题，int在32位系统下的范围是 [−232, 231 − 1]，也就是说当n为负数不能简单的n=-n,x=1/x，因为当n为−232时会超界。正确的方法是转化成1/x的-n+1次方再乘一个1/x，也就是说求xn等价于求 xn * x-1。
首先写出来递归形式的代码，代码简洁但会比较慢。
double myPow(double x, int n) {
if (n < 0)
return 1 / x*myPow(1 / x, -n - 1);
if (n == 0)
return 1;
if (n == 1)
return x;
double half = myPow(x, n / 2);
if (n % 2)
return x*half*half;
else
return half*half;
}
然后转化成非递归模式，使用一个stack存每次除以2的结果，
比如19 -> 9 -> 4 -> 2 。
需要记录每次的结果而并不是简单的得到次数的原因是 每次有奇数就说明少乘了一份，需要多计算一次*x。
切分的时候n>=2的话要继续分，n==1的时候直接返回就可以了。
double myPow(double x, int n) {
if (n == 0)
return 1;
if (n < 0)
return myPow(1 / x, -(n + 1)) / x;
stack<int> s;
for (; n != 1; n /= 2)
s.push(n);
double res = x;
while (!s.empty()) {
res *= res;
if (s.top() % 2)
res *= x;
s.pop();
}
return res;
}
投递快手等公司7个岗位 >
查看14道真题和解析
，