描述
Implement pow(x, n), which calculates x
raised to the power n
(i.e., xn
).
Example 1:
1 2
| Input: x = 2.00000, n = 10 Output: 1024.00000
|
Example 2:
1 2
| Input: x = 2.10000, n = 3 Output: 9.26100
|
Example 3:
1 2 3
| Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
|
Constraints:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
分析
$x^n$ 可以写作 $ x^{n/2} * x^{n/2} * x^{n\%2} $,可以用递归。
解决方案1(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public: double pow_recu(double x, int n) { if(n == 0) { return 1; } double harf_x = pow_recu(x, n/2); if(n % 2 == 0) { return harf_x * harf_x; }else { return harf_x * harf_x * x; } } double myPow(double x, int n) { if(n < 0) { return 1 / pow_recu(x, -n); }else { return pow_recu(x, n); } } };
|
解决方案2(Golang)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| func myPow(x float64, n int) float64 { if n >= 0 { return quickMul(x, n) } return 1.0 / quickMul(x, -n) }
func quickMul(x float64, n int) float64 { if n == 0 { return 1 } y := quickMul(x, n/2) if n%2 == 0 { return y * y } return y*y*x }
|
相关问题