LeetCode - 50. Pow(x, n) 题解

Question

题目

解析

这个题目和普通的求幂不同的是:

• 其中 x (底数) 是 double 类型的，且 n 是范围是 Integer 范围的（可正可负) :
• 要注意的就是当 n 为负数的时候，我们可以转换成求 1.0 / pow(x,-n) ；
• 还一个很重要的地方就是当 n = Integer.MIN_VALUE 的时候要特殊处理，因为整形范围是-2³¹到 2³¹-1，所以或者我们使用 long 来存转换的数，或者特殊判断一下；

递归求解

两种写法意思一样，第二种写法更加简洁:

class Solution {
    public double myPow(double x, int n) {
        if (n > 0) {
            return pow(x, n);
        } else {
            if (n == Integer.MIN_VALUE) {
                return 1.0 / (pow(x, -(Integer.MIN_VALUE + 1)) * x); // MAX_VALUE = -(Integer.MIN_VALUE + 1)
            }
            return 1.0 / pow(x, -n);
        }
    }

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

class Solution {
    public double myPow(double x, int n) {
        if (n == 0)
            return 1.0;
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                // return 1.0 / (myPow(x,-(Integer.MIN_VALUE+1)) * x);
                return 1.0 / (myPow(x, Integer.MAX_VALUE) * x);
            }
            return 1.0 / myPow(x, -n);
        }
        double half = myPow(x, n / 2);
        if (n % 2 == 0)
            return half * half;
        else
            return x * half * half;
    }
}

非递归求解

三种写法的意思都是一样，只不过处理 Integer.MIN_VALUE 的方式不同而已。

class Solution {
    public double myPow(double x, int n) {
        if (n == 0)
            return 1.0;
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                return 1.0 / (myPow(x, Integer.MAX_VALUE) * x);
            } else {
                return 1.0 / myPow(x, -n);
            }
        }
        double res = 1.0;
        while (n > 0) {
            if ((n & 1) != 0)
                res *= x;
            x = x * x;
            n >>= 1;
        }
        return res;
    }
}

class Solution {
    public double myPow(double x, int n) {
        if (n == 0)
            return 1.0;
        double res = 1.0;
        if (n < 0) {
            x = 1 / x;
            n = -(1 + n);  // for Integer.MIN_VALUE   
            res *= x;  // x is 1/x   because n is -(n+1) so should do this 
        }
        while (n > 0) {
            if ((n & 1) != 0)
                res *= x;
            x = x * x;
            n >>= 1;
        }

        return res;
    }
}

class Solution {
    public double myPow(double x, int n) {
        if (n == 0)
            return 1.0;

        long abs = Math.abs((long) n); // also for Integer.MIN_VALUE

        double res = 1.0;
        while (abs > 0) {
            if ((abs & 1) != 0)
                res *= x;
            x = x * x;
            abs >>= 1;
        }
        if (n < 0)
            return 1.0 / res;
        return res;
    }
}