二分法/分治法：leetcode 50 Pow(x,n)

Jan 7, 2020 · 1 min read · Golang 二分法 ·

本文讲解了 Pow(x,n) 的最优算法以及背后的二分法/分治法思想，本题仍可以利用二进制位运算解决。

实现 Pow(x, n) ，即计算 \(x\) 的 \(n\) 次幂函数 \(x^n\)。

示例1：

1输入：x = 2.00000, n = 10
2输出：1024.00000

示例2：

1输入：x = 2.00000, n = -2
2输出：0.25000
3解释：2^{-2} = (1/2)^2 = 1/4 = 0.25

解法：

 1package main
 2
 3import (
 4	"fmt"
 5)
 6
 7func myPow(x float64, n int) float64 {
 8	if n >= 0 {
 9		return quickMul(x, n)
10	}
11	return 1.0 / quickMul(x, -n)
12}
13
14func quickMul(x float64, n int) float64 {
15	if n == 0 {
16		return 1
17	}
18	y := quickMul(x, n/2)
19	if n%2 == 0 {
20		return y * y
21	}
22	return y * y * x
23}
24
25func main() {
26	fmt.Println(quickMul(1.5, 2)) // 打印值 2.25
27}

翻译:

"English" |