50. pow(x, n)
题目来源:https://leetcode-cn.com/problems/powx-n/
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10 输出: 1024.00000
示例 2:
输入: 2.10000, 3 输出: 9.26100
示例 3:
输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。
解法
错误解法:
#C++:
class Solution {
public:
double myPow(double x, int n) {
if(n==0) return 1;
else if(n<0)
{
double total=1;
for(int i=0;i<-n;i++)
total *= x;
total = 1.0/total;
return total;
}
else if(n>0)
{
double total=1;
for(int i=0;i<n;i++)
total *= x;
return total;
}
return 0;
}
};
错误原因:
题目要求
-100.0 < x < 100.0 n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1] 。
错误版本算法循环次数过多,导致运行超时
解决办法:
采用快速幂运算方法求解
「快速幂算法」的本质是分治算法,即「二分法角度」
方法一:快速幂 + 递归
class Solution {
public:
double QuickMul(double x,int n)
{
if(n==0) return 1.0;
double y=QuickMul(x,n/2);
return n%2==0? y*y : y*y*x;
}
double myPow(double x, int n) {
if(n==0)
return 1;
else if(n<0)
return 1/QuickMul(x,n);
else if(n>0)
return QuickMul(x,n);
return -1;
}
};
方法二:快速幂 + 迭代
迭代的思路是将幂按照二进制进行拆分,如x^7 = x * x^2 * x^4;
class Solution {
public:
double QuickMul(double x,long long n)
{
long long N = n;
double res=1;
if(N == 0)
return 1.0;
else
{
double t = x;
while(N!=0){
if(N & 0x01 == 1)
{
res = res * t;
}
N = N >> 1;
t = t * t;
}
return res;
}
}
double myPow(double x, int n) {
long long N = n; //1.00000 与 -2147483648 这组数据会越界,-N会出错,因此需要用long long存储
return n>=0 ? QuickMul(x,N) : 1/QuickMul(x,-N);
}
};
测试过程中遇到的问题:
1.00000 与 -2147483648 这组数据会越界,-N会出错,因此需要用long long存储n的数值,以避免-N出错。