leetcode 50. Pow(x, n)

leetcode 50. Pow(x, n)

题目描述

50. Pow(x, n)

实现 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 n 是一个整数 -104 <= xn <= 104

解题思路

法1

方法1:
快速幂

1. 将n作为二进制数,当二进制位为1是需要计算进结果(原有的数字乘以当前快速幂的值)

2. 使用循环查看每一个二进制位是否为1,并计算快速幂结果

3. 需要注意的是一种特殊情况,就是负指数的情况,我们先要计算求幂数的倒数,在计算他的n次方

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

执行结果

法1

首先处理了指数为 0 的情况，返回 1.0。然后处理了负指数的情况，通过将 x 取倒数，将指数转为正数。接下来使用循环进行指数的计算，每次将指数右移1位，并将 x 的值平方，如果当前指数最小二进制位为1，则将结果乘以 x。最后返回计算得到的结果。

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

 // 处理负指数的情况
 if n < 0 {
  x = 1 / x
  n = -n
 }

 result := 1.0
 for n > 0 {
  // 满足条件，将结果乘以 x
  if n&1==1 {
   result *= x
  }
  x *= x
  n>>=1
 }

 return result
}

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

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

法2

法3