Algorithm之二分治应用之pow(x,n)

设计算法，求 x 的 n 次幂：pow(x, n)


算法一

public class Solution {
    
    /*
    * Solution 1: Time Limit Exceeded 
    *
    * Test Case：
    *           x = 0.00001
    *           n = 2147483647
    */
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        if(n == 0) return 1;
        boolean neg = false;
        if(n < 0){
            neg = true;
            n = -n;
        }
        double r = 1;
        while(n > 0){
            r *= x;
            n--;
        }
        if(neg) r = 1 / r;
        return r;
    }
    
}

算法二

public class Solution {
    
   /*
    * Solution 2: Divider and Conquer
    *
    * NOTE: 1
    *  // if(x == 0) return 0;   
    *  // if x = +0, and m is less than 0, the result is positive Infinity.
    *
    * NOTE: 2
    *  // 如果 m 是偶数：则直接返回 half * half   
    *  // 如果 m 是奇数：则直接需要在偶数的基础上，再补上一位。
    *  //                这一位是 m / 2 时，舍掉的那一位。
    *-----------------------------------------------
    */
   public double myPow(double x, int m) {
        if(m == 0) return 1;
        double half = myPow(x, m / 2);
        
        double val = half * half;
        if(m % 2 == 0) // 偶数：正、负
            return val;
        else{
            
            if(m > 0)  // 奇数：正
                return val * x;
            else       // 奇数：负
                return val * (1 / x);
        }
   }
}

-
引用：
https://leetcode.com/problems/powx-n








-