Leetcode-50. Pow(x, 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] 。
解法:快速幂,利用分治的思想,将N次方转换成更小的问题,分成奇数偶数进行讨论,这样的时间复杂度能够降低到O(logN)。需要注意N同时可能是负数。空间复杂度为O(logN),储存logN的元素half值
- Java
注意防止stackoverflow error,深递归导致栈被耗尽,例如1.00000的-2147483648次方,不知道为什么python不会出现这个问题
函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,相当于一次push压栈操作,每当函数返回,相当于一次pop出栈操作。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。
解决方案:
1.把递归调用函数改用while或者for循环来实现。
2.通过尾递归优化。尾递归是指在函数返回调用自身本身,并且return语句不能包含表达式(既return 函数名(参数))。这种情况下,编译器或者解释器,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。
class Solution {
public double myPow(double x, int n) {
if(n<0){
x = 1/x;
n = -n;
}
return this.helper(x,n);
}
private double helper(double x ,int n){
if(n==0) return 1d;
double half = this.helper(x,n/2);
if(n%2==0){
return half*half; // 不写成return this.helper(x*x,n/2),会导致栈溢出
}else{
return x*half*half;
}
}
}
- Python
使用递归
class Solution:
def myPow(self, x: float, n: int) -> float:
if not n: return 1
if n<0: return 1/self.myPow(x,-n)
if n%2:
return x*self.myPow(x,n-1)
return self.myPow(x*x,n/2)