50. Pow(x,n) 次方运算

题目

实现一个 pow(x,n) 计算 x 的 n 次幂。

解析

常规计算即可，如果 n 为负，对 x 多次扩展后除以 0 即可。这么计算会超时，考虑更大的步进。
要求 x^n即是 x^(n/2) * x(n/2) 。这样一来，我们就将这个运算做了一个递归。

1. 如果 n 为偶数，直接 x^(n/2) * x^(n/2)
2. 如果 n 为奇数，则还要额外乘一个 x
3. 当 n 为 0 时，直接返回 1

伪代码

函数原型 func(x,n) double

rst = func(x,n/2)
rst*=rst
if n%2 == 1
  rst*=x
return rst

代码

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1.0
    }
    if x == 1.0 {
        return 1.0
    }
    if n < 0 {
        return 1.0 / quick(x, -n)
    }
    return quick(x,n)
    
}

func quick(x float64, n int) float64 {
        if n == 0 {
        return 1.0
    }
    rst:= quick(x,n/2)
    rst*=rst
    if n%2== 1{
        rst*=x
    }
    return rst
}

image.png

后记

1. 死脑筋，一直想从前往后算，递归啊，分治啊