LeetCode 50 Pow(x, n)

    
        标签：
        
            LeetCode
        
    发布于：2021-05-29 10:02:57
    编辑于：2021-05-29 10:27:56
    浏览量：1494

分析

一道中等难度的数学题。

要注意的是 x 可以为负数。

递归解法

class Solution {
public:
    unordered_map<int, double> m;
    double x;
    double myPow(double x, int n) {
        this->x = x;
        return helper(n);
    }
    
    double helper(int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        if (n == -1) return 1 / x;
        if (m.find(n) != m.end()) return m[n];
        double res = helper(n/2) * helper(n-n/2);
        m[n] = res;
        return res;
    }
};

0 ms 6.8MB

复杂度 O(log n)

迭代解法

把 n 看成二进制形式，很明显，例如 7 可以表示成 0111，即7=0*8+1*4+1*2+1*1，则 2^7 即 2^(0*8) * 2^(1*4) * 2^(1*2) * 2^(1*1)。

以下别人的示例代码：

class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1;
        while(n){
            if(abs(n%2)==1){
                ans = (n>0) ? ans*x : ans/x;
            }
            x=x*x;
            n=n/2;
        }
        return ans;
    }
};

复杂度也是 O(log n)。

Links: leetcode-50-pow(x,-n)