你好,游客 登录 注册 搜索
背景:
阅读新闻

【leetcode】Pow(x, n) - IT-Homer 专栏

[日期:2013-04-12] 来源:  作者: [字体: ]

Question:

Implement pow(xn).



Answer 1:  O(n)

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(n == 0) return 1;
        if(x == 0) return 0;
        
        bool flag = false;      // is negative
        if(n < 0) {
            flag = true;
            n = -n;
        }
        
        /*
        double ret = 1;
        for(int i = 0; i < n; ++i){        // error when n is max integer, such as n = 2147483647 overflow
            ret *= x;
        }
        */
        
        double tmp = x;
        double ret = 1;
        while(n > 0) {
            if(n & 1 == 1){     // or (n & 1) or (n % 2) or (n % 2 == 1)
                ret *= tmp;
            }
            tmp *= tmp;
            n >>= 1;
        }
        return flag ? 1.0/ret : ret;
    }
};
注意点:

题目非常简单,担忧许多细节需要考虑

1) x = 0 或 n = 0

2) n 为正或负数

3) n为正整数边界值(error 错误)



Answer 2:  O(log(n))

class Solution {
public:
    
    double pow2(double x, int n){
        if(n == 0){
            return 1;
        }
        
        double mul = pow2(x, n/2);
        
        if(n & 1) {
            return x * mul * mul;
        } else {
            return mul * mul;
        }
    }
    
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(n < 0){
            return 1.0 / pow2(x, -n);
        } else {
            return pow2(x, n);
        }
    }
};
注意点:

1) 递归二分法

2) n为正/负数






收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻