算法系列之幂运算

本题来自Leetcode
题目传送门
难度：中等
编程语言：Go

1. 背景

看了不少其他人提交的答案，发现Golang的答案特别少，且很多都存在同一个问题：精度。

Go的浮点数精度范围有限，对于超过精度的返回值会不准确，但貌似很多人并没有意识到这个问题，或者说不知道怎么处理于是略过了这个问题。

本文会按照：题目介绍-> 解题思路分析 -> 源码展示的方式，来完成这一作业。

2. 题目介绍

实现 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

提示：

1. -100.0 < x < 100.0

2. -2^{31} <= n <=2^{31}-1

3. -10^4 <= x^n <= 10^4

3. 解析思路

简单方法，直接调用内置math函数库。 重复造轮子方法：按照快速降幂的思路，将n折半，计算因子扩大为2次幂。n折半后是奇数，则需要单独✖️计算因子。

所谓降幂，其实就是利用了幂函数的运算法则：x^n =(x²⁾(n/2) ，来减少需要运算的次数。尤其是在幂n比较大时，具备良好的性能优势。

4. 源码展示

公用方法，保留结果的8位精度。

func roundFloat(r float64) float64 {
    return float64(int(r*10000000)) / 10 / 1000000
}

简单方法实现

func myPowSimple(x float64, n int) float64 {
    return roundFloat(math.Pow(x, float64(n)))
}

快速降幂：

func myPowFast(x float64, n int) float64 {
    switch {
    case n == 0 || x == 1:
         return 1
    case x == 0:
            return 0
    }
    if n < 0 {
        n = -n
        x = 1 / x
    }
    result := 1.0
    for i := n; i > 0; i = i / 2 {
        if i%2 != 0 {
           result *= x
        }
        x *= x
    }
    return roundFloat(result)
}

Leetcode运算结果： 两种方法均得到以下数据：

执行用时: 0ms
内存消耗: 1.9 MB

生活依然要继续，每天拿出半个小时，放下焦虑，用行动来积累更好的自己，我们一起加油！