Implement pow(x, n).
Notice
You don‘t need to care about the precision of your answer, it‘s acceptable if the expected answer and your answer ‘s difference is smaller than 1e-3.
Example
Pow(2.1, 3) = 9.261
Pow(0, 1) = 0
Pow(1, 0) = 1
Challenge
O(logn) time
参考了@grandyang 的代码
解法一：
1 class Solution { 2 public: 3 double myPow(double x, int n) { 4 double res = 1.0; 5 for (int i = n; i != 0; i /= 2) { 6 if (i % 2 != 0) { 7 res *= x; 8 } 9 x *= x; 10 } 11 return n < 0 ? 1 / res : res; 12 } 13 };
迭代
解法二：
1 class Solution { 2 public: 3 double myPow(double x, int n) { 4 if (n < 0) { 5 return 1 / power(x, -n); 6 } 7 8 return power(x, n); 9 } 10 double power(double x, int n) { 11 if (n == 0) { 12 return 1; 13 } 14 15 double half = power(x, n / 2); 16 if (n % 2 == 0) { 17 return half * half; 18 } 19 20 return x * half * half; 21 } 22 };
解法三：
1 class Solution { 2 public: 3 /** 4 * @param x the base number 5 * @param n the power number 6 * @return the result 7 */ 8 double myPow(double x, int n) { 9 if (n == 0) { 10 return 0; 11 } 12 if (n == 1) { 13 return x; 14 } 15 if (n == -1) { 16 return 1 / x; 17 } 18 19 return myPow(x, n / 2) * myPow(x, n - n / 2); 20 } 21 };
会超时