LeetCode 0050 - Pow(x, n)
# Hints
- 快速幂
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Implement , which calculates raised to the power ().
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
is a 32-bit signed integer, within the range
Noted by JM233333: Do not use big-number-arithmetic, just let the result be set as automatically.
# 题意
给定一个浮点数 和一个整数 ,求 的值。
注:原题没有说明,不要使用大数运算,任由编译器将超大答案设置为 即可。
# 题解
用快速幂直接求解即可。对于 的情况,求出 后取倒数即可。
细节问题:
- 注意特判 的情形。
# AC代码
class Solution {
private:
const int MIN = (1 << 31);
public:
double myPow(double x, int n) {
double res;
if (n >= 0) {
res = power(x, n);
} else {
res = 1.0 / (n == MIN ? (power(x, abs(n + 1)) * x) : power(x, abs(n)));
}
return res;
}
// 快速幂
double power(double a, int n) {
double res = 1;
while (n > 0) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01