Leetcode No.50 Pow(x, n)
题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。
示例 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 -2^31 <= n <= 2^31-1 -10^4 <= x^n <= 10^4
思路1：暴力破解（超时）
class Solution {
public double myPow(double x, int n) {
int flg=1;
if(x<0&&n%2==1){
flg=-1;
}
x=Math.abs(x);
int p=1;
if(n<0){
p=-1;
n=-n;
}
double rs=1;
while((n--)>0){
rs=rs*x;
System.out.println(rs);
}
if(p<0){
rs=1/rs;
}
return flg*rs;
}
}思路2：快速幂 + 递归
「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^64，我们可以按照：
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32--> x^64
的顺序，从 x开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^64的值，而不需要对 x 乘 63 次 x。
再举一个例子，如果我们要计算 x^77，我们可以按照： x→x^2 →x^4→x^9→x^19→x^38 →x^77的顺序，在 x→x^2，x^2→x^4 ，x^19→x^38 这些步骤中，我们直接把上一次的结果进行平方，而在 x^4→x^9，x^9→x^19，x^38 →x^77 这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。
但如果我们从右往左看，分治的思想就十分明显了：
当我们要计算 x^n时，我们可以先递归地计算出 y=x^⌊n/2⌋ ，其中 ⌊a⌋ 表示对 a 进行下取整；
根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2 ；如果 n 为奇数，那么 x^n = y^2 * x
递归的出口为 n = 0，任意数的 0 次方均为 1。
由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果。
class Solution {
public double quickPow(double x, long n){
if(n==0){
return 1.0;
}
double y=quickPow(x,n/2);
System.out.println(y);
if(n%2==1){
return y*y*x;
}else{
return y*y;
}
}
public double myPow(double x, int n) {
long N=n;
if(n>=0){
return quickPow(x,N);
}else{
return 1.0/quickPow(x,-N);
}
}
}腾讯云开发者
