算法 LC 数学 - Pow(x, n)

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

题解

思路1: 快速幂 + 递归
当我们要计算x^n 时我们可以先递归地计算出y=x^(n/2),n/2向下取整
根据递归计算的结果，如果n为偶数，那么x^n = y^2 ,如果n为奇数，x^n = y^2 *x
递归的边界为n=0，任意数的0 次方均为1

// OC
+ (double)myPow1:(double)x n:(int)n {
    return n>=0 ? [self quickMul1:x n:n] : 1.0/([self quickMul1:x n:-n]);
}

+ (double)quickMul1:(double)x n:(int)n {
    if (n == 0) {
        return 1.0;
    }
    double y = [self quickMul1:x n:n/2];
    return n%2==0 ? y*y : y*y*x;
}

// Swift

    static public func myPow1(_ x: Double, _ n: Int) -> Double {
        return n>=0 ? quickMul1(x, n) : 1.0/quickMul1(x, -n)
    
    }
    
    static func quickMul1(_ x:Double, _ n: Int) -> Double {
        if n == 0 {return 1.0}
        let y:Double = quickMul1(x, n/2)
        return n%2==0 ? y*y : y*y*x
    }

思路2:快速幂 + 二进制拆分

n = 2^(i0) + 2^(i1) + ... + 2^(ik)
x^n = x^( 2^(i0)) * x^( 2^(i1)) + ... +x^ (2^(ik))

x^77次方对应的二进制 (1001101) 和每个二进制位的权值如下

最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77

折半计算，每次把n缩小一半,计算下一位置的权值
当n为奇数时,则结果乘上这个二进制位上的权值
判断n是正数还是负数。如果是正数，直接返回结果; 如果是负数,返回 1 / res;

// OC

+ (double)myPow2:(double)x n:(int)n {
    return n>=0 ? [self quickMul2:x n:n] : 1.0/([self quickMul2:x n:-n]);
}

+ (double)quickMul2:(double)x n:(int)n {
    double weight = x;
    double res = 1.0;
    while (n != 0) {
        if (n%2 == 1) {
            res *= weight;
        }
        weight *= weight;
        n = n/2;
    }
    return res;
}

// Swift

    static public func myPow2(_ x: Double, _ n: Int) -> Double {
        return n>=0 ? quickMul2(x, n) : 1.0/quickMul2(x, -n)
    
    }
    
    static func quickMul2(_ x:Double, _ n: Int) -> Double {
        var power = n
        //  权值初值为x, 即二进制位第1位的权值为x^1
        var weight = x
        var res = 1.0
        while power != 0 {
            // 如果当前二进制位为1， 让结果乘上这个二进制位上的权值,
            // 该位权值在上一轮迭代中已经计算出来了
            if power%2 == 1 {
                res *= weight
            }
            weight *= weight // 计算下一个二进制位的权值
            power = power/2
        }
        
        return res
        
    }

参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwo102/

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