50. Pow(x, n)

题意：

解题思路：

(快速幂的递归写法) O(logn)
1. 每次缩写一半的规模再相乘
2. n为偶数：2的4次方 = 2的2次方 * 2的2次方
3. n为奇数：2的5次方 = 2的2次方 * 2的2次方 * 2的1次方

PHP代码实现：

class Solution {
    function myPow($x, $n) {
        return $this->myPow1($x, $n);
        $n = (float) $n;
        if ($n < 0) {
            $x = 1 / $x;
            $n = -$n;
        }
        return $this->x2($x, $n);
    }
    //分治思想(每次取一半的数进行计算，最后相乘)
    // 2 2 2 2 2 2 => 2 2 2 = 8  2 2 2 = 8  =》 64
    function myPow1($x, $n) {
        if (!$n) return 1;
        if ($n < 0) {
            return 1 / $this->myPow1($x, -$n);
        }
        if ($n % 2) {
            return $x * $this->myPow1($x, $n - 1);
        }
        return $this->myPow1($x * $x, $n / 2);
    }
    function x2($x, $n) {
        if ($n == 0) return 1;
        $half = $this->x2($x, floor($n/2));
        if (fmod($n, 2) == 0) {
            return $half * $half;
        } else {
            return $half * $half * $x;
        }
    }
}

GO代码实现：

func myPow(x float64, n int) float64 {
    if n >= 0 {
        return x2(x, n)
    }
    return 1.0 / x2(x, -n)
}
func x2(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    y := x2(x, n / 2)
    if n % 2 == 0 {
        return y * y
    }
    return y * y * x
}