前端算法题解 leetcode50-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
示例 3:.
输入: x = 2.00000, n = -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
解题思路-分情况讨论
本题可以分几种情况讨论:\
- 如果
x = 1
,那么无论n
的值是多少,结果都是1
- 如果
n = 0
,那么无论x
的值是多少,结果都是1
- 如果
n = 1
,那么无论x
的值是多少,结果都是x
- 如果
x = -1
,那么如果n
是偶数,结果是1
,否则结果是-1
- 如果
n > 0
,则结果为1 *= x
n
次 - 如果
n < 0
,则结果为1 /= x
n
次
代码实现
var myPow = function(x, n) { if(x === 1 || n === 0){ return 1 } if(x===-1){ return n % 2 ? -1 : 1 } let res = 1 if(n>0){ for(let i = 0;i<n;i++){ res *= x } return res } for(let i = 0;i<-n;i++){ res /= x if(x>0 && res<0.000005){ return res } } return res }
解题思路-分治
上面的解题思路虽然能解题,但是因为要真实的进行每一次计算,所以效率比较低。那如何才能提高效率呢?
这里我们可以采用类似二分的方法,将 x
的 n
次方拆分为 x^(n/2) * x^(n/2)
,以此来加速计算的过程。每次拆分一半,直到 n = 0
。因为每次的处理逻辑是相同的,所以可以利用递归函数递归调用自己,而退出条件就是 n = 0
。
代码实现
var myPow = function(x, n) { if(n == 0){ return 1 } if(n < 0){ return 1 / myPow(x, -n) } if(n % 2){ return x * myPow(x, n - 1) } return myPow(x * x, n / 2) }
至此我们就完成了 leetcode-50-Pow(x, n),更多关于前端算法 Pow(x, n)题解的资料请关注我们其它相关文章!
赞 (0)