首页 > 代码库 > leetcode------Pow(x, n)(3)

leetcode------Pow(x, n)(3)

标题

Pow(x, n)

通过率26.1%
难度中等

Implement pow(xn).

  以为只是单纯的求xn,习惯了用java里面的math.pow(x,n),所以我认为传进来的值都是比较正常的,谁知道竟然会传n<0的数。。。。。直接泪奔,然后再尝试。。。发现栈溢出,也就是说单纯的递归或者非递归针对此题已经不行了。

考虑分治法,因为不管怎么都是n个x相乘,先分成两半去乘不是更好,整个算法的时间复杂度T(n)=2T(n/2)+1,由主方法得出O(lgn)。

那么会出现一个关键的问题就是n不能被2整除,也就是处理奇数偶数。偶数就是最后的两半相乘,奇数就是两半相乘后再乘以x。

附加:依然要处理n的正负问题:

java代码如下:

 1 public class Solution { 2     //n maybe a fu shu  3     public double pow(double x, int n) { 4          5         if (n < 0) { 6             return 1 / power(x, -n); 7         } else { 8             return power(x, n); 9         }10 }11 public double power(double x, int n) {12         if (n == 0)13             return 1;14  15         double v = power(x, n / 2);16  17         if (n % 2 == 0) {18             return v * v;19         } else {20             return v * v * x;21         }22     }23 }

 

leetcode------Pow(x, n)(3)