一、题目
50. Pow(x, n) - 力扣(Leetcode)
实现 pow(x, n) ,即计算 x
的整数 n
次幂函数(即,x
ⁿ )。
示例 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⁻² = 1/2² = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-
-2
³¹ <= n <= 2
³¹-1
-
n
是一个整数 - 要么
x
不为零,要么n > 0
。 -
-10
⁴<= x
ⁿ<= 10
⁴
二、题目解读
题目要求我们实现 pow(x, n) 函数,即求解x的n次方,当n过大时,肯定是会超时的,这时我们便需要使用到快速幂。
介绍快速幂:
众所周知,如果我们要求a的n次方,最朴素的想法一定是把它们乘起来,这样的复杂度是O(n),显然太差了。
然后我们想到一种优化,如果我们能求得 2的k次方=n的话,我们只需要将a的平方相乘k次,这样的复杂度是O(log2n),但是我们很难找到这样的k。
于是我们将这一想法再一次优化,我们只要能找到 2的k1次方+2的k2次方+...=n就好了,这样的复杂度还是O(log2n)
这一想法可以通过数的二进制位运算轻易解决,比如9的二进制是1001,也就是从右往左数第i位,我们的答案就乘上a的2的i次方
于是就有了快速幂算法。
三、代码
class Solution {
public double myPow(double x, int n) {
return Math.pow(x,n);
}
}
看到一个段子😂
面试的时候遇到这个题目,
然后我思考🤔了片刻,写出了
return pow(x,n);
。面试官问我,为啥这么写?
我说,这是软件工程的代码复用;不重复造轮子;
于是,面试官就要把我挂了😂;
说了一句,我们决定复用公司原来的员工(❁´◡`❁)。
二进制快速幂:
class Solution {
public double myPow(double x, int n) {
boolean neg=n<0;//判断n是正数还是负数
double ans=1;
for(long m=Math.abs((long)n);m!=0;m>>=1){
if(m%2==1){
ans*=x;
}
x=x*x;
}
return neg?1/ans:ans;//负数返回ans的倒数
}
}
二分思想递归,复杂度是对数级的。
class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if (n == -1) {
return 1 / x;
}
double half = myPow(x, n / 2);
double rest = myPow(x, n % 2);
return half * half * rest;
}
}
快速幂递归
class Solution {
public double myPow(double x, int n) {
//x的0次方为:1
if(n==0) return 1.0;
//x的1次方为本身:x
if(n==1) return x;
//x的-1次方为本身的倒数:1/X
if(n==-1) return 1.0/x;
//如果n为偶数 -> 2^10 = 2^5 * 2^5
double temp = myPow(x,n>>1);
double res = temp*temp;
return res*myPow(x,n&1);
}
}
文章来源地址https://www.toymoban.com/news/detail-491691.html文章来源:https://www.toymoban.com/news/detail-491691.html
到了这里,关于LeetCode——Pow(x, n)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!