LeetCode第[50]题(Java)：Pow(x, n)

题目：求x的n次幂

难度：Medium

题目内容：

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

翻译：

实现计算x的n次幂。

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]

我的思路：呃，没啥好思路，只会硬刚

1、幂等于0，则直接返回1，负幂则转为正然后将x变为1/x；

2、循环相乘。。。

我的代码：

 1     public double myPow(double x, int n) {
 2         if(n == 0)
 3             return 1;
 4         if(n<0){
 5             n = -n;
 6             x = 1/x;
 7         }
 8         
 9         double ans = x;
10         while (n-- > 1) {
11             ans *= x;
12         }
13         
14         return  ans;
15     }

我的复杂度：O（n）

结果——291 / 304 test cases passed. Time Limit Exceeded（超时）

Last executed input:

0.00001 2147483647

内心os：看来O（n）的方式不行。得用O（logn）？那么就是递归？这个用递归也是O（n）啊。。。

编码过程中的问题：

1、一开始直接使用的是x*=x，发现通过率比较低，并且报错的结果很大，才发现这样不是求幂而是求开多少次平方。。。

答案代码：

 1     public double myPow(double x, int n) {
 2         
 3         if(n == 0)
 4             return 1;
 5         if (n == Integer.MIN_VALUE) {
 6             return 1/x*myPow(x, n+1);
 7         }
 8         if(n<0){
 9             n = -n;
10             x = 1/x;
11         }
12         
13         return (n%2 == 0) ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
14     }

答案复杂度：O（logN）

答案思路：果然是利用递归。。。

前面和我一样的，不过在最后递归的时候做了判断：

如果n是偶数，那么就取（x²）^（n/2）

如果n是奇数，则取 x*（x²）^（n/2）

这段代码干什么用的？

        if (n == Integer.MIN_VALUE) {
            return 1/x*myPow(x, n+1);
        }

如果n为-2³¹，那么此时取反的话由于n是int则不能表示成2³¹，

所以有两种解决办法：

1、和我一样，直接写个判断把一个x提出来再继续算。

2、直接将整个方法提取出来，另外写一个递归方法，此方法的参数写成（double x， long n）就不存在越界的情况了。