LeetCode-50.Pow(x,n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

遍历n，时间复杂度为O(n)，但是Time Limit Exceeded

1 public double myPow(double x, int n) {//my
2         double re = 1;
3         for (int i = 1; i <= Math.abs(n); i++) {
4             re *=x;
5         }
6         return n<0?(1/re):re;
7     }

使用分治的方法，时间复杂度为O(logn)

 1 class Solution {
 2     public double myPow(double x, int n) {//分治 递归 my
 3         long y = n;//一定要是long 否则n=-2147483648时会溢出
 4         if(y<0){
 5             y=-y;
 6         }
 7         double re = calPow(x,y);
 8         return n<0?(1/re):re;
 9     }
10     private double calPow(double x,long n){
11         if(0==n){
12             return 1;
13         }
14         if(1==n){
15             return x;
16         }
17         double re =calPow(x,n/2);
18         re = re*re;
19         if (n%2==1){
20             re*=x;
21         }
22         return re;
23     }
24 }

非递归写法时间复杂度O(logn)

 1  public double myPow(double x, int n) {
 2         long y = n;
 3         if(y<0){
 4             y=-y;
 5         }
 6         double re = 1;
 7         while(0!=y){
 8             long bit = 1&y;
 9             
10             if(0!=(1&y)){
11                 re *= x;
12             }
13             x =x*x;
14             y= y>>1;
15         }
16         return n<0?(1/re):re;
17     }