50. Pow(x, n)

Posted on | In | 浏览 次
Words count in article: 398 | Reading time ≈ 2

题目

Implement pow(x, n), which calculates x raised to the power n (xn).

  • Example 1: 
    1
    2
    Input: 2.00000, 10
    Output: 1024.00000
  • Example 2: 
    1
    2
    Input: 2.10000, 3
    Output: 9.26100
  • Example 3: 
    1
    2
    3
    Input: 2.00000, -2
    Output: 0.25000
    Explanation: 2-2 = 1/22 = 1/4 = 0.25
    Note:
  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [$−2^{31}$, $2^{31}$ − 1]

解题思路

解法 1 — 暴力破解（Failed）

  • 将n的值分为n>0,n<0,n=0三种情况
  • 递归算出结果
  • 实现代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 解法一 暴力破解
    class Solution {
    public:
        double myPow(double x, int n) {
            double result = 1.0;
            for(int i = 0; i < abs(n); ++i) {
                result *= x;
            }
            return n > 0 ? result : 1 / result;
        }
    };

  • 这种做法测试后果然不能AC，错误分析

    • 时间$O(n)$，当n很大时，超时

    • 未考虑边界条件n =INT_MIN，这个时候-n赋不进n

解法 2 — 分治（AC）

  • 超时问题解决

    • 将$x^n$分解为$x^{n/2} x^{n/2} x^{n\%2}$递归求解
    • 时间复杂度$O(logn)$

  • 边界越界问题解决

    • n = $-2^{31}$时，通过简单的-n来求其相反数将导致溢出，最大正整数为$2^{31}-1$
    • 对于n<0的情况，令$n’ = -(n+1)$ 。求$x^n$等价于求 $1 / (x^{n’}*x)$
  • 实现代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 解法二 分治 + 递归
    class Solution {
    public:
        double myPow(double x, int n) {
            if(n < 0) {
                // 越处理--粗糙版
                // x = 1.0 / x;
                // if(n == INT_MIN)
                // 	return x * myPow(x, -1* (n+1));
                // else
                // 	return myPow(x, -1 * n);
                
                // 越界处理--精简版 	
                return 1.0 / (x * myPow(x, -1 * (n+1)));
            }
            else if(n == 0)
                return 1.0;
            else {
                double tmp = myPow(x, n / 2);
                if(n % 2  == 0)
                    return tmp * tmp;
                else 
                    return tmp * tmp * x;
            }
        }
    };