Code & Func
2017-09-26

打卡第三天!!!

今天刷的题是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
double ret = 1
2
for(int i = 0;i < n;i++)
3
ret *= x;
4
return ret

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

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

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

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

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

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

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

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

上一条动态