【Medium】50. Pow(x, n)

Implement pow(x, n).

中心思想： 

这题需要注意n有几种特殊情况： n = 1, return 0

x = 0, n必须为非负数

n < 0, 结果要变为分母

n = -INT_MIN时，不能直接使用-n， 要用INT_MAX

解法一：用递归方法将n个x乘起来

解法二（O(logn)）：利用对称性，pow(x,n) = pow(x,n/2)*pow(x,n-n/2)

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