Code & Fun

打卡第三天!!!

今天刷的题是Pow(x,n)

implement pow(x,n)

题目相当简洁,看起来好像也不会很难的样子,不过他竟然是一道Medium的题目(万万没想到).
pow(x,n)大家应该都多少有接触过,就是求x的n次方嘛。
我们可以把n分成三种情况去考虑:

  • n > 0 : 可以转化成求myPow(1/x,-n)
  • n == 0 :直接return 1即可
  • n < 0 :这个是我们实现的关键,只要完成这个就可以AC这道题了。

首先,一个最简单的思路就是n个x相乘.

1
2
3
4
double ret = 1
for(int i = 0;i < n;i++)
ret *= x;
return ret

这样需要做n次乘法,时间复杂度是O(n),在LeetCode中,这样做是会超时的,我们需要找到一个 时间复杂度更小的算法。

可以考虑使用分治法去完成:
也就是说,我们要求myPow(x,n)的值,那我们可以转化成求myPow(x,n/2)的值,然后将其返回值乘二即可(n为奇数,还需要 乘多一个x)。

1
2
double ret = myPow(x,n/2);
return (n%2)?(ret*ret*x):(ret*ret);

这是递归的做法,显然这已经能够完成了,这也是我的做法。
这里面还有一个坑点没提到,就是在n < 0的情况下,我们前面的做法是直接return myPow(1/x,-n)的,但是这样是会出错的:
n=-2147483648时,会出现RunTime Error,也就是那个-n是求不出来的,因为int类型的最大值为2147483647。
这里用了一个小技巧:
return myPow(1/x, -(n + 1) ) *1/x;
因为这里的n满足n < 0,所以可以不用考虑正溢出的情况。
完整的代码为:

1
2
3
4
5
6
7
8
9
10
double myPow(double x, int n) {
if (n == 0) return 1;
else if (n > 0) {
double ret = myPow(x,n/2);
return (n%2)?ret*ret*x:ret*ret;
} else {
//n < 0
return myPow(1/x,-(n + 1 )) * 1/x;
}
}

恩,按照惯例,看看dicuss中别人的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double myPow(double x, int n) {
double ans;
unsigned long long;
if ( n < 0 ) {
p = -n;
x = 1/x;
} else {
p = n;
}

while(p) {
if (p & 1)
ans *= x;
x *= x;
p >>= 1;
}

}

看到这个做法的第一眼就想起了某位老师说的:

“有时候你需要从二进制的角度去看问题。”

我们来考虑myPow(a,7)的情况:
7的二进制编码为:0000 0111,也就是7 = 4 + 2 + 1
而 $ a^{7} = a^{4} * a^{2} * a^{1} $
相信上面的代码应该能够很容易的看懂了。
另外我们还可以看到,他用unsigned long long来避免溢出的情况,这也是一个小技巧。


本文首发于Code & Fun