Algorithmの二分割応用のpow(x,n)

もっと読む
設計アルゴリズム、xのn乗を求める:pow(x,n)
アルゴリズム1

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;
    }
    
}

アルゴリズム2

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
を選択します.