凌云的博客

成功=工作+游戏+少说空话

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

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


题目

Implement pow(x, n).

题意

实现 pow(x, n)。

解法 1

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

        int unsigned m = n;
        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);
    }
};