151 字
1 分钟
快速幂 Pow(x,n)
题目描述
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。 示例 1：
输入：x = 2.00000, n = 10输出：1024.00000示例 2：
输入：x = 2.10000, n = 3输出：9.26100个人C++解答
快速幂有两种方法，一种是分治思想，另一种是倍增法，我用的是分治的思路，将x的n次方化为x的n/2*n/2次方×x的n%2次方，下面给出代码；
class Solution {public: double myPow(double x, int n) { if(n==0) return 1; if(n==1) return x; if(n==-1) return 1/x;
double a = myPow(x,n/2); double b = myPow(x,n%2); return a*a*b; }};个人C++解答
这一部分是倍增法的代码，我没有去尝试理解，来自评论区FATSHEEP好友提供，灵神的题解也是用到的倍增法
double myPow(double x, int n) { double ans = 1; while(n != 0) { if(n & 1) { if(n < 0) ans *= 1/x; else ans *= x; } n /= 2; x *= x; } return ans;} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐