Pow(x, n)

https://leetcode.com/problems/powx-n/description/

Implement pow(x,n)

Thoughts

分治，比如2^9分成2^4 * 2^4 * 2，2^4再分成2^2*2^2直到n == 1。n是奇数时还有个额外的x要乘，n为负数时用且n为奇数时做额外除x。n为INT_MIN时可能导致的 *溢出问题，因此不建议当n < 0时让n = -n, x = 1/ x的方法，而是直接让pow(x / 2) / x 比较好。

Code

/*
 * @lc app=leetcode id=50 lang=cpp
 *
 * [50] Pow(x, n)
 */
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        double res = myPow(x, n / 2);
        res *= res;
        if (n % 2 == 0) return res;
        if (n < 0) return res / x;
        return res * x;
    }
};

Analysis

Errors: 1. n = min_value溢出

时间复杂度O(lgN), 空间O(1).