leetcode-50-Pow(x,-n)

描述


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
}

相关问题


题目来源