清风的技术小屋

不为所动, 做更专业的自己

0%

LeetCode 50 - Pow(x, n)

问题描述

Implement pow(x, n), which calculates \(x\) raised to the power \(n\) (\(x^n\)).

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
3
Input: 2.00000, -2
Output: 0.25000
Explanation: 2^(-2) = (1/2)^2 = 1/4 = 0.25

Note:

  • \(-100.0 \lt x \lt 100.0\)
  • \(n\) is a 32-bit signed integer, within the range \([-2^{31}, 2^{31}-1]\)

Related Topics: Math, Binary Search

原问题: 50. Pow(x, n)

中文翻译版: 50. Pow(x, n)

解决方案

方案1

题目中 \(n\) 是整数,此时求 \(x\)\(n\) 次方可以分解为两个 \(x\)\(n/2\) 次方相乘,即:

\[ x^n = \begin{cases} x^{n/2} \cdot x^{n/2} & n \text{ is even} \\ x^{n/2} \cdot x^{n/2} \cdot x & n \text{ is odd} \end{cases} \]

则此题可以用递归进行求解,需要注意的是如果 \(n\) 是负数,不能在代码里将 \(n\) 转为正数,\(x\) 转为 \(1/x\),因为该题的测试用例中会有 \(n = -2^{31}\) 这种取值,如果取正会导致数值溢出,解决办法是当 \(n\) 为奇数时,此时

\[ x^{n} = x^{n/2} \cdot x^{n/2} \cdot \frac{1}{x} \]

参考解题代码1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

class Solution {
public:
double myPow(double x, int n) {
// do not transfer n to -n if n < 0
// because of numerical overflow (n = -2^31)
if (n == 0)
return 1.0;
double half = myPow(x, n/2);
if (n % 2 == 0) {
return half * half;
} else {
if (n < 0)
x = 1 / x;
return half * half * x;
}
}
};

int main()
{
double x;
int n;
Solution solu;

x = 1.00000;
n = -2147483648; // n = -2^31
cout << "Pow(" << x << ", " << n << ") = "
<< solu.myPow(x, n) << endl;
return 0;
}

方案2

方案1是递归解法,这里介绍非递归解法。从二进制角度看整数 \(n\),如果第 \(k\) 位为1,说明 \(x^n\) 可以表示为 \(x^n = x^{2^k} \cdot x^{n-2^k}\),以此类推,将余下的 \(x^{n-2^k}\) 根据非零位进行分解。例如 \(n=5\),其二进制表示为 101,则根据非零位,我们可以得到以下分解:

\[ x^5 = x^{2^2} \cdot x^{2^0} \]

根据分解可以得到一个迭代解法,就是计算结果初始值为 ans = 1,从第0位依次往高位对 \(n\) 的二进制进行非零判断,如果 \(n\) 的二进制第 \(k\) 位非0,则 ans 乘上 \(x^{2^k}\),即

\[ \text{ans} = \text{ans} \cdot x^{2^k} \]

遍历完 \(n\) 的所有二进制位,ans 就是我们求得的计算结果。

那么我们怎么快速得到 \(x^{2^k}\) 呢?我们可以将 \(n\) 不断进行右移操作,每移动1位,对 \(x\) 就进行以下计算

1
x *= x

这样当我们右移 \(k\) 次时,此时 \(x\) 已经是原始 \(x\)\(2^k\) 次方,此时我们用位与运算判断第1位是否非0,如果非0,按照前面迭代过程可得,最终计算结果 ans 需要乘上 \(x\)

参考解题代码2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;


class Solution {
public:
double myPow(double x, int n) {
if (n == 0)
return 1.0;

long long num = n;
double ans;

if (n < 0) {
// use long long type to avoid numerical overflow
num = -(long long)n;
x = 1 / x;
}

ans = 1.0;
while (num > 0) {
if ((num & 1) != 0)
ans *= x;
x *= x;
num >>= 1;
}

return ans;
}
};

int main()
{
double x;
int n;
Solution solu;

x = 1.00000;
n = -2147483648; // n = -2^31
cout << "Pow(" << x << ", " << n << ") = "
<< solu.myPow(x, n) << endl;
return 0;
}