50. Pow(x, n)

发表于 | 分类于

每日一题 2019 - 04 - 01

题目：

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

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
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 [−2^31, 2^31 − 1]

解法：

这个题让实现幂函数pow，可以考虑使用移位来解决，但是在求负指数幂的时候容易引起精度的缺失，所以可以先将负指数幂转成正指数幂计算，输出结果时候求倒数。

当然这个题最关键的部分在于我们求幂积的过程，为了保证不超时，我们可以考虑如下算法：

  • 先转幂数为二进制数字，随后写出数学推导，例如：
  • 按照上面思路，我们就可以极大的减小时间复杂度，保证指数幂的变动有限次

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double myPow(double x, int n) 
    {
        double ans=x,res=1.0;
        long long m=n;
        m=abs(m);
        while(m>0)
        {
            if(m&1==1) res*=ans;
            m=m>>1;
            ans*=ans;
        }
        if(n>0)
            return res;
        else
            return 1.0/res;
    }
};
0%
undefined