抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

35 | 面试题:实现一个求解平方根的函数

69. x 的平方根

解法一:二分法

思路:因为是非负整数,x 的平方是单调递增的,所以 x 的一半的平方实际上是大于 x 的。使用二分法可以找到一个相近的位置。

代码中不使用m*m 的原因是为了防止越界。

class Solution {
fun mySqrt(x: Int): Int {
if (x == 0 || x == 1) return x

var left = 1
var right = x
var res = -1
while (left <= right) {
val mid = left + (right - left) / 2
if (mid < x / mid) {
left = mid + 1
res = mid
} else if (mid > x / mid) {
right = mid - 1
} else {
return mid
}
}
return res
}
}

解法二:牛顿迭代法

传说在一个月黑风高的夜晚… 有人发明了一个算法,欲知后情如何,请看:wiki

class Solution {
fun mySqrt(x: Int): Int {
var r = x.toLong()
while (r * r > x) {
r = (r + x / r) / 2
}
return r.toInt()
}
}

数学家的伟大成果。

扩展题:367. 有效的完全平方数

思路依旧是二分,只是说得加上浮点匹配,保留精确度才能找到完全平方数。

class Solution {
    fun isPerfectSquare(num: Int): Boolean {
        if (num == 0 || num == 1) return true

        var left = 1
        var right = num

        while (left <= right) {
            val mid = left + (right - left) / 2
            when {
                mid < num * 1.0f / mid -> {
                    left = mid + 1
                }
                mid > num * 1.0f / mid -> {
                    right = mid - 1
                }
                else -> {
                    return true
                }
            }
        }
        return false
    }
}

0条评论

发表评论