526互联

剑指Offer 16. 数值的整数次方

发布时间 2023-08-26 16:23:44作者: 小星code

题目链接： 剑指Offer 16. 数值的整数次方

题目描述：

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

解法思路：
思路一：直接写一个循环，进行相乘，对于n<0的情况，将结果取倒数，但是这样写会超时。

思路二：采用二次幂的方法：
当 n 为正数时：

  • n 为偶数时：xn = xn/2 * xn/2
  • n 为奇数时：xn = xn/2 * xn/2 * n

当 n 为负数时候：提前取 x 的倒数和 n 的相反数

代码：

func myPow(x float64, n int) float64 {
    if n < 0 {
        x = 1/x
        n *= -1
    }
    return pow(x, n)
}

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