2017-04-13 18:09:01 +0000   |     algorithm leetcode binary search math   |   Viewed times   |    

题目

Implement pow(x, n).

注:这题主要考察的是分治法的运用。不是为了考察处理像Double.NaN,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,0.0,-0.0这样的极端情况的处理。所以第二个参数幂nint型,并且测试数据集中没有刁难以上的极端值。否则根据Math.pow()函数的规约(Math.pow(),情况复杂地多。

递归分治

不是所有问题分治法都有效,但幂运算可以简化成2次. 终结条件是n等于0,1,-1的情况,可以直接返回对应结果。其他情况都是递归让n减半。

代码

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

简化代码

把终结条件设为0,1,-1是为了减少一层递归,提高效率。如果单纯为了简化逻辑和代码的话,终结条件可以只考虑n=0的情况。但这种情况,效率就会受影响。

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

结果

0,1,-1为终结条件的结果。 pow-1

0为终结条件的结果。 pow-3

和库函数Math.pow()比较

代码

直接调用Math.pow().

public double myPow(double x, int n) {
    return Math.pow(x,(double)n);
}

结果

应该说和我们的的算法效率差不多。 pow-2