打卡第三天！！！

今天刷的题是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来避免溢出的情况，这也是一个小技巧。