博文中会简要介绍Leetcode P0050题目分析及解题思路。
“Pow(x, n)”是一道比较基础的题目，主要考察分而治之的思想。
Implement pow(x, n), which calculates x raised to the power n (i.e. x^n)
核心思路可以自上而下采取二分，也可以自下而上采取二分。自下而上地扩大解空间的想法和p0029的思路十分相似，而自上而下采取二分则是传统的分而治之思想，递归地解决子问题。
需要注意的是自上而下的思路可能会由于递归层数过大导致栈溢出，所以建议使用第一种方法，即自下而上地扩大解空间。
以下是Java的题解代码实现。
class Solution {
public double myPow(double x, int n) {
if (n == 0)
return 1.0;
double product = 1.0;
long remain = Math.abs((long) n);
while (remain > 0) {
long multiple = 1;
double temp = x;
while ((multiple*2) <= remain) {
temp *= temp;
multiple += multiple;
}
product *= temp;
remain -= multiple;
}
return (n > 0)? product: 1.0/product;
}
}
第二种Java解法，快速幂。
class Solution {
public double myPow(double x, int n) {
double product = 1.0;
long exp = Math.abs((long) n);
while (exp != 0) {
if ((exp&1) == 1)
product *= x;
x *= x;
exp >>= 1;
}
return (n >= 0)? product: 1.0/product;
}
}
以下是C++的题解代码实现。
class Solution {
public:
double myPow(double x, int n) {
if (n == 0)
return 1.0;
double product = 1.0;
long remain = abs(long(n));
while (remain > 0) {
long multiple = 1;
double temp = x;
while ((multiple*2) <= remain) {
temp *= temp;
multiple += multiple;
}
product *= temp;
remain -= multiple;
}
return (n > 0)? product: 1.0/product;
}
};