【每日一题】LeetCode. 50. Pow(x, n) 每日一题

每日一题，防止痴呆 = =

一、题目大意实现 pow(x, n) ，即计算 x 的 n 次幂函数。

文章图片

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
二、题目思路以及AC代码这个思路就明显的不能再明显了，幂次这么大，肯定是用快速幂算法才不会超时，下面就简单的说一下快速幂算法递归和迭代的两种思路，具体可以参看这篇博客，我觉得讲的还是很详细的。
https://blog.csdn.net/Harington/article/details/87602682
快速幂递归思路快速幂递归的思路相对来说比较好理解，对于幂运算来说，最暴力的方法就是a^b = a×a×a…×a，但是这样的时间复杂度为O(b)，那么我们可以考虑另一种算法，对于a^b来说，如果b是偶数，那么a^b=a^(b/2) * a^(b/2)，如果b是奇数，那么a^b = a × a^(b-1)，这样就可以进行递归求解了，总体的时间复杂度是O(logn)。
快速幂迭代思路 【【每日一题】LeetCode. 50. Pow(x, n)】快速幂的迭代思路利用了二进制，如果要求解a^b，我们可以将b进行拆解，按照其二进制的形式，比如我们要计算a^13，那么a^13 = a^1 + a^4 + a^8，那1，4，8是什么呢，就是13的二进制表示，13的二进制位1101，三个位置的1分别对应于等式右侧的三项，这样就可以通过对b逐位比较，来得到幂运算的结果了，时间复杂度同样是O(logn)。
下面给出快速幂递归思路的AC代码：

typedef long long ll; class Solution { public: double qPow(double x, ll n) { if (n == 0) return 1; if (n & 1) { return x * qPow(x, n-1); }double tmp = qPow(x, n/2); return tmp * tmp; }double myPow(double x, int n) { ll n_tmp = n; if (n_tmp < 0) return 1 / qPow(x, -n_tmp); else return qPow(x, n_tmp); } };

如果有问题，欢迎大家指正！！！