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

我的方法一：暴力法（超时）

步骤：

1. 即将n个x直接相乘
2. 当n为负数时，其实求的是1/x的abs(n)次方

初始值和边界条件

1. n=0，返回1
2. n的最小值是-2³¹，n的最大值是2³¹-1，在运算时，如果n为负数，会转正，所以-2³¹转正后，还是-2³¹
   这块需要考虑如何解决越界的问题
   2.1 方法一，使用8位的long long保存4位的int，注意有些平台long是4位
   2.2 方法二，先n转正，然后将n转为unsigned int，这样-2³¹变为了2³¹

复杂度

时间复杂度：O(N)
空间复杂度：O(1)

代码

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0){
            return 1;
        }

        long long N = n;
        if(n < 0){
            N = -N;
            x = 1 / x;
        }

        double ret = 1;
        for(long long i = 0; i < N; i++){
            ret *= x;
        }
        return ret;
    }
};

其他人的方法

分治法

比如计算x⁶⁴，可以通过x→x² →x⁴ →x⁸ →x¹⁶ →x³² →x⁶⁴
计算6次就可以获得，暴力法需要计算64次

步骤

1. 如暴力法，需要考虑n是负数和越界的问题
2. xⁿ = x^n/2 * x^{(n - n/2)}
3. 一直递归的求下去

初始值

边界条件

1. n=0时，返回1

复杂度

时间复杂度：O(lgn)
空间复杂度：O(lgn)，递归本身依靠的栈的操作

代码

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

        return myPow(x, N);
    }

    double myPow(double x, long long n) {
        if(n == 0){
            return 1;
        }

        int half = n / 2;
        double half_ret = myPow(x, half);
        if(n % 2 == 0){
            return half_ret * half_ret;
        }else{
            return half_ret * half_ret * x;
        }
    }
};