LeetCode笔记50：Pow(x, n)

哇！50题了耶[耶]

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

最近题目都这么短的吗？[what]

出现了！快速幂，重点，面试常考！

本文答案参考自LeetCode官方题解。

我们小学二年级（[看]）就学过：（2的10次方） 等于 （2的5次方 乘以 2的5次方）

所以，我们可以将n次方分解为 n/2次方乘以n/2次方，n/2次方又可以分解为 n/4次方乘以n/4次方

这体现了一个重要的算法思想：分治算法。<(￣︶￣)>

递归的一个重点是设置结束条件，在这里结束条件就是当 n=1次方时，返回0.

还有，这里要注意n是奇偶数的不同情况。[灵光一闪]

这里就不写解法了，只有贴代码才能体现递归之美：

class Solution {

public:

double quickMul(double x, long long 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) {

long long N = n;

return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);

}

};

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

既然有递归，那肯定有迭代

o(*￣▽￣*)o

把递归的代码改一改就好啦~

≡ω≡

有些人是用嘴编程的吼~[捂脸][捂脸][捂脸]

[来看我][来看我][来看我]