Jamzen的技术博客
0%

LeetCode.x的平方根

发表于 分类于 Valine：

实现int sqrt(int x)函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

  • 示例 1：输入: 4，输出: 2
  • 示例 2：输入: 8，输出: 2

牛顿迭代法：

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
object Sqrt {
     def main(args: Array[String]): Unit = {
          println(sqrt(0))
          println(sqrt(1))
          println(sqrt(2))
          println(sqrt(3))
          println(sqrt(4))
          println(sqrt(5))
          println(sqrt(15))
          println(sqrt(16))
          println(sqrt(18))
          println(sqrt(20))
          println(sqrt(29))
          println(sqrt(2147395599))
     }

     /**
      * 牛顿迭代法：
      * f(x) = x^2 - N
      * => f(x) - f(x1) = 2x1(x - x1)
      * => f(x) = 2x1x-2x1^2 + x1^2 - N
      * => f(x) = 2x1x -x1^2 - N = 0
      * => x = (x1 + N/x1)/2
      */
     def sqrt(num: Int): Int = {
          if (num <= 1) return num
          var x1 = num / 2
          while (Math.min((x1 + num / x1) / 2, x1) != x1) {
               x1 = Math.min((x1 + num / x1) / 2, x1)
          }
          x1
     }
}