凌云的博客

LeetCode 算法题 50. Pow(x, n)

分类：algorithm| 发布时间：2016-10-14 11:19:00

---

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

解法 1

class Solution {
public:
    double myPow(double x, int n) {
        unsigned int m = n;
        if (n < 0) {
            x = 1.0 / x;
            m = -m;
        }

        double tbl[32] = {0};
        double result = 1;
        tbl[0] = x;
        for (int i = 1; i < 32; i++) {
            tbl[i] = tbl[i - 1] * tbl[i - 1];
        }

        for(int i = 0; i < 32; i++){
            if (m & (0x1 << i)) result *= tbl[i];
        }

        return result;
    }
};

解法 2

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