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

leetcode .

题目描述

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

示例 1：

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

输入：x = 2.10000, n = 3 输出：9.26100 示例 3：

输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

计算x^n

法1

循环相乘
r*=x循环n次

• 时间复杂度(O(n))
• 空间复杂度(O(1))

法2

快速幂\

1. 举个例子n^4=n^2*n^2
2. n^8=n^4*n^4
3. 这样我们可以减少循环的次数只需要计算n^2,n^4...n^2^m就行了
4. 比如x^10=x^8*x^2,我们只需要计算到x^8就可以了,

具体实现过程

令一个中间变量t=x
t*=t
当n&1==1时执行
r*=t
循环执行n>>1直到n==0为止\

• 时间复杂度(O(logn))
• 空间复杂度(O(1))

法3

• 时间复杂度(O())
• 空间复杂度(O())

执行结果

快速幂

快速幂算法

// 快速幂
func myPow(x float64, n int) (r float64) {
 if n < 0 {//当n为负数的时候,我们将x=x^-1进行计算就不用定义新的计算方法了
  x = 1 / x
  n = -n
 }
 r = 1
 for t := x; n > 0; {
  if n&1 == 1 {
   r *= t//当为1时计算入值
  }
  t *= t//幂的叠加
  n >>= 1
 }
 return
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.9 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例： 304 / 304