本题来自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
提示:
-
-100.0 < x < 100.0
-
-2^{31} <= n <=2^{31}-1
-
-10^4 <= x^n <= 10^4
3. 解析思路
简单方法,直接调用内置math函数库。 重复造轮子方法:按照快速降幂的思路,将n折半,计算因子扩大为2次幂。n折半后是奇数,则需要单独✖️计算因子。
所谓降幂,其实就是利用了幂函数的运算法则:x^n =(x2)(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
生活依然要继续,每天拿出半个小时,放下焦虑,用行动来积累更好的自己,我们一起加油!
网友评论