50. Pow(x, n) (Medium)

Implement pow(x, n).

Solution 1: recursive

double myPow(double x, int n) {
    if (n < 0) return 1 / power(x, -n);
    return power(x, n);
}
double power(double x, int n) {
    if (n == 0) return 1;
    double half = power(x, n / 2);
    return (n % 2 == 0) ? half * half: x * half * half;
}

Solution 2:

还有一种写法可以只用一个函数即可,在每次递归中就检查n的正负,然后做相应的变换即可,代码如下:

double myPow(double x, int n) {
    if (n == 0) return 1;
    double half = myPow(x, n/2);
    if (n % 2 == 0) return half*half;
    else if (n > 0) return x*half*half;
    else return half*half/x;
}

Solution 3: iterative

这道题还有迭代的解法,我们让i初始化为n,然后看i是否是2的倍数,是的话x乘以自己,否则res乘以x,i每次循环缩小一半,直到为0停止循环。最后看n的正负,如果为负,返回其倒数,参见代码如下:

double myPow(double x, int n) {
    double res = 1.0;
    for (int i = n; i != 0; i /= 2) {
        if (i % 2) res *= x;
        x *= x;
    }
    return (n < 0) ? 1/res:res;
}

results matching ""

    No results matching ""