[LeetCode] Pow(x, n)

Implement pow(x, n).

思路1：利用整数n的二进制表达
性质：(x^y)^z = x^(y*z)
例如：(5^3)^2 = 5^3 * 5^3 = 5^(3*2)

10: 二进制(1010)b = (2^3)*1 + (2^2)*0 + (2^1)*1 + (2^0)*0
3^10 = 3^[(2^3)*1] * 3^[(2^2)*0] * 3^[(2^1)*1] * 3^[(2^0)*0] 
res = 1
res = res^2 * 3^1 = 3^(1)b
res = res^2 * 3^0 = 3^2 = 3^(10)b
res = res^2 * 3^1 = 3^5 = 3^(101)b
res = res^2 * 3^0 = 3^10 = 3^(1010)b
需要特殊处理 n<0的情况。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: double pow(double x, int n) { bool negPow = n<0 ? true : false; n = abs(n); double res = 1; for(int i=31; i>=0; i--) { res = res*res; if(n & (1<<i)) res = res*x; } if(negPow) res = 1/res; return res; } };

思路2：分治递归

递归公式为：x^n = x^(n/2) * x^(n/2) * x^(n%2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: double pow(double x, int n) { if(n>=0) return powPositive(x,n); else return 1/powPositive(x,-n); } double powPositive(double x, int n) { if(n==0) return 1; // base case double res = powPositive(x, n/2); res *= res; if(n%2) res *= x; return res; } };