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

时间:2021-03-01 19:14:57

题目:求x的n次幂

难度:Medium

题目内容

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

翻译

实现计算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、循环相乘。。。

我的代码:

     public double myPow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
} double ans = x;
while (n-- > 1) {
ans *= x;
} return ans;
}

我的复杂度: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,发现通过率比较低,并且报错的结果很大,才发现这样不是求幂而是求开多少次平方。。。

答案代码

     public double myPow(double x, int n) {

         if(n == 0)
return 1;
if (n == Integer.MIN_VALUE) {
return 1/x*myPow(x, n+1);
}
if(n<0){
n = -n;
x = 1/x;
} return (n%2 == 0) ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}

答案复杂度:O(logN)

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

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

如果n是偶数,那么就取(x2(n/2)

如果n是奇数,则取 x*(x2(n/2)

这段代码干什么用的?

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

如果n为-231,那么此时取反的话由于n是int则不能表示成231

所以有两种解决办法:

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

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