Pow(x, n)

Implementpow(x,n).

Example 1:

Input:2.00000, 10

Output:1024.00000

Example 2:

Input:2.10000, 3

Output:9.26100

分析

归并排序注意两点： 1、 bipartition 2、merge

此题用到了bipartition

能用stack当然也能用ArrayList 只是stack更好

代码

//版本一： 用recursion

class Solution {
    public double myPow(double x, int n) {
        return myOwnPow(x, n);  
    }

    double myOwnPow(double x , long n){
        if( n == 0 ) return 1.0;

        if(n < 0 ) { // n ^(-3) = 1/n3 ？？？
            return 1 / myOwnPow(x, 0 - n);
        } 

        if( n == 1) return x;

        double halfResult = myOwnPow(x , n/2);
        double result = halfResult * halfResult;
        if((n & 1) == 1) { // 判断奇数偶数 ？ why？？？？？ 
            result *= x;
        }

        return result;
    }   
}

//版本二：用iteration

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

        double result = myPosPow(x, Math.abs((long)n));
        return n>0 ? result :1/ result;
    }

    private  double myPosPow(double x , long n ){
        // top down

        Stack<Double> stack = new Stack<>();
        while(n!=1){
            if((n&1)==1 ){
                stack.push(x);
            }else{
                stack.push(1.0);
            }
            n = n/2;
        }

        // bottom up
        double result = x;
        while(!stack.isEmpty()){
            result = result * result* stack.pop();
        }
        return result;
    }
}