“实现函数,计算x的n次幂。”
题目链接:
来源:力扣(LeetCode)
链接:50. Pow(x, n) - 力扣(LeetCode) (leetcode-cn.com)
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。
示例 1:
输入: x = 2.00000, n = 10
输出: 1024.00000
示例 2:
输入: x = 2.10000, n = 3
输出: 9.26100
这道题可以使用快速幂+递归的方法解题。
快速幂算法,本质就是分治算法,将大问题分解成小问题,然后递归解决。
快速幂算法:
比如要计算x8,可以按照x → x2 → x4 → x8的顺序,从x开始,每次将上一次的结果进行平方,3次后就可以得到x8的结果,而不需要对x乘8次x。
如果幂是偶数,比如x9,可以按照x → x2 → x4 → x9的顺序,这些步骤中,还是按照将上一次结果平方,而在x4 → x9的步骤中,需要将上一个结果进行平方,还需要额外乘一个x。
综上所述,可以推到出规律,如果要计算xn,首先判断n的奇偶:
接着就可以递归地得到结果了。
代码参考:
public class Solution {
//递归
public double MyPow(double x, int n) {
return (n >= 0) ? res(x, n) : 1 / res(x, n);
}
private double res(double x, int n)
{
if(n == 0)
return 1;
double y = res(x, n / 2);
return (n % 2 == 0) ? y * y :y * y * x;
}
}
时间复杂度 : O(log n)
其中n为遍历的层数。
空间复杂度: O(log n)
其中n为遍历的层数。
这道题还有更秀的一行解题法:
public class Solution {
public double MyPow(double x, int n) {
return Math.Pow(x,n);
}
}
是不是秀的头皮发麻。。。