LeetCode

LeetCode-求一个数的n次幂

递归

  • 问题描述：

    求x的n次方power(x, n)，如power(2,4) = 16。

  • 思路：

    很直接的思路，x与自己相乘n次的结果，事假复杂度为O(N)。这个方法有个问题：很多的重复计算。以power(2,4)为例，power(2,4) = (2x2)x(2x2)。(2x2)被计算了两次，当n很大时，就会由更多的重复计算。其实power(2,4) = power(2,2)xpower(2,2)。所以可以很容易写出递归的主体：

    1
    2
    double half = power(x, n/2);
    double res = half*half;

    时间复杂度为O(logN)。而递归终止条件和其他细节可从下图中自然得到：

    【过程图】

  • 实现：

    由过程图可以实现如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    double myPow3(double x, int n){ 
        // 递归终止条件：
        if (n==0) return 1.0;
        // 特殊情况：
        if (x==0.0) return 1.0;
        long long int nn=n;
        // 当x为负数
        if(nn<0){
            nn=-nn;
            x=1/x;
        }
        // 递归主体：
        double half = myPow3(x, nn/2);
        double  ans = half*half;
        // 这个细节在过程图中很容易看出：
        return n%2==0 ? ans : ans*x;
    }

敲黑板：递归直接写很容易出错，把过程图画出来，一些细节就会很容易发现。