50. Pow(x, n)

题目：

Implement pow(x, n).

链接： http://leetcode.com/problems/powx-n/

题解：

使用二分法求实数幂，假如不建立临时变量halfPow，直接return计算结果的话会超时，还没仔细研究为什么。

Time Complexity - O(logn)， Space Complexity - O(1)。

public class Solution {
    public double myPow(double x, int n) {
        if(x == 0)
            return x;
        if(n == 0)
            return 1;
        double halfPow = myPow(x, n / 2), result;
        if(n % 2 == 0)
            result = halfPow * halfPow;
        else if (n > 0)
            result = halfPow * halfPow * x;
        else
            result = halfPow * halfPow / x;
        return result;
    }
}

更新Update:

public class Solution {
    public double myPow(double x, int n) {
        if(x == 0.0)
            return 0.0;
        if(n == 0)
            return 1.0;
        if(n % 2 == 0)
            return myPow(x * x, n / 2);
        else {
            if(n > 0)
                return myPow(x * x, n / 2) * x;
            else
                return myPow(x * x, n / 2) / x;
        }
    }
}

二刷：

还是二分法。

Java:

使用临时变量:

Time Complexity - O(logn)， Space Complexity - O(1)。

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

不适用临时变量，使用尾递归:

Time Complexity - O(logn)， Space Complexity - O(1)。

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

三刷:

Java:

public class Solution {
    public double myPow(double x, int n) {
        if (x == 0.0) return 0.0;
        if (n == 0) return 1.0;
        if (n % 2 == 0) return myPow(x * x, n / 2);
        else if (n < 0) return myPow(x * x, n / 2) / x;
        else return myPow(x * x, n / 2) * x;
    }
}

测试：

Reference:

blog.****.net/linhuanmars/article/details/20092829

https://leetcode.com/discuss/17005/short-and-easy-to-understand-solution

https://leetcode.com/discuss/52800/5-different-choices-when-talk-with-interviewers

https://leetcode.com/discuss/12004/my-answer-using-bit-operation-c-implementation

https://leetcode.com/discuss/9459/o-logn-solution-in-java

https://leetcode.com/discuss/39143/shortest-python-guaranteed

https://leetcode.com/discuss/21272/lg-n-320ms-javasolution-9-lines

https://leetcode.com/discuss/13545/simple-iterative-lg-n-solution

https://leetcode.com/discuss/62484/iterative-java-python-short-solution-o-log-n