power and square

Posted on   |   In   |  

求一个数的n次幂和平方根

Power(x, n)

link
实现求一个数的n次幂
解法一:二分法
显然我们知道这个公式:
$x^n = x^{\frac{n}{2}}*x^{\frac{n}{2}}*x^{n\%2}$

此处需要注意的是n为负数的情况。
由此写出如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    double myPow(double x, int n) {
        if(n < 0)   return 1/power(x, abs(n));
        else    return power(x, n);
    }
private:
    double power(double num, int m){
        if(m == 0)  return 1;
        
        double x = power(num, m/2);
        
        double ret = x*x;
        
        if(m%2 == 0)    return ret;
        else        return ret*num;
    }
};

解法2:
对于1个数的幂，可以将它的指数转换为二进制的形式，就是把n看成是以2为基的位构成的，因此每一位是对应x的一个幂数，然后迭代直到n到最高位。比如说第一位对应x，第二位对应x*x,第三位对应x^4,…,第k位对应x^(2^(k-1)),可以看出后面一位对应的数等于前面一位对应数的平方，所以可以进行迭代。因为迭代次数等于n的位数，所以算法的时间复杂度是O(logn)。
下面来看一个实例
$3^11 = 3^{(1011)b} = 3^{1 + 2 + 8} = 3^1 * 3^2 *3^8$
这里没有加入越界的判断，参阅文章2给出了越界的判断
参阅:http://bangbingsyb.blogspot.com/2014/11/leetcode-powx-n.html
http://blog.csdn.net/linhuanmars/article/details/20092829

1
2
3
4
5
6
7
8
9
10
11
12
13
double myPow(double x, int n) {
    bool powNegative = n < 0?true:false;
    
    n = abs(n);
    double res = 1;
    for(int i = 31; i >= 0; i--){
        res *= res;
        if(n>>i & 1)
            res *= x;
    }
    if(powNegative) return 1/res;
    else    return res;
}

Sqrt(x)

link
给定一个数字，要求它的平方根，显然要确定平方根所处的范围，刚开始自己给出的范围是[0, INT_MAX],发现还有改进[0, sqrt(INT_MAX)],最后改成[0, x/2 + 1]

$$\begin{align} (x/2 +1)^2 & >= x \\ \frac{x^2}{4} + x +1 & >= x \\ \frac{x^2}{4} + 1& >= 0 \\ \end{align}$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
   int mySqrt(int x) {
        if(x < 0) return -1;
        if (x == 0) return 0;
        
        int lb = 0;
//这里故意让上界超出，是为了减少上界的判断，因为有可能上界就是所求
        int ub = x/2 +2;
        while(ub - lb > 1 ){
            int mid = (lb + ub)/2;
            if (mid <= x/mid)
                lb = mid;
            else
                ub = mid;
        }
        
        return lb;    
    }

};