Pow(x,n) 快速幂

终于要到端午节啦 mikey终于要回到幸福的家啦啦啦啦啦啦啦啦~~~~

实现Pow(x,n)，即计算 x 的整数 n 次幂函数

解法一：递归 自顶向下

class Solution {public double myPow(double x, int n) {long N = n;if(N<0){return pow(1/x,-N);}return pow(x,N);}private double pow(double x,long n){if(n==0){return 1.0;}if(n==1){return x;}if(n%2==1){return x*pow(x,n-1);}return pow(x*x,n/2);}
}

解法二：把指数看成二进制形式 自底向上

快速幂算法的核心思想是利用指数的二进制表示来减少乘法的次数。

class Solution {public double myPow(double x, int n) {long N = n;if(N<0){N = -N;x = 1/x;}double res = 1.0;while(N>0){if((N%2)==1){res*=x;}N/=2;x*=x;}return res;}
}