Jamzen的技术博客
0%

LeetCode.Pow

发表于 分类于 Valine：

实现 pow(x, n) ，即计算 x 的 n 次幂函数。说明: -100.0 < x < 100.0, n是32位有符号整数，其数值范围是[−231, 231−1]。

  • 示例 1:
    输入: 2.00000, 10 输出: 1024.00000
  • 示例 2:
    输入: 2.10000, 3 输出: 9.26100
  • 示例 3:
    输入: 2.00000, -2 输出: 0.25000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
object Pow {

     def main(args: Array[String]): Unit = {
          println(pow2(0.00001, 2147483647))
          println(pow2(2.00000, -1024))
          println(pow2(2.00000, 10))
     }

     /**
      * 时间复杂度O(n)
      */
     def pow(x: Double, n: Int): Double = {
          if (n == 0) return 1
          var res = 1.0
          for (i <- 0 until (if (n < 0) n else -n) by -1) {
               res = res * x
          }
          if (n < 0) 1 / res else res
     }

     /**
      * 快速幂，时间复杂度O(logn)
      */
     def pow2(x: Double, n: Int): Double = {
          if (n == 0) return 1
          if (n == 1) return x
          var res = x
          var i = 1L
          while (i * 2 <= Math.abs(n.toLong)) {
               res = res * res
               i = i * 2
          }

          if (n > 0) {
               res * pow2(x, (Math.abs(n.toLong) - i).toInt)
          } else {
               (1 / res) / pow2(x, (Math.abs(n.toLong) - i).toInt)
          }
     }
}