69.md

题目地址

https://leetcode-cn.com/problems/sqrtx/

解答1

class Solution:
    def mySqrt(self, x: int) -> int:
        """
            x 的平方根

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

            输入: 8
            输出: 2
            说明: 8 的平方根是 2.82842...,
                 由于返回类型是整数，小数部分将被舍去。
        """
        s = x
        if not x: return 0
        return int(self.sqrts(x, s))

    def sqrts(self, x, s):
        res = (x + s / x) / 2
        if res == x:
            return x
        else:
            return self.sqrts(res, s)

解答2

class Solution:
    def mySqrt(self, x: int) -> int:
        """
            x 的平方根(非最优解，牛顿迭代法）

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

            输入: 8
            输出: 2
            说明: 8 的平方根是 2.82842...,
                 由于返回类型是整数，小数部分将被舍去。
        """
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

解答3

class Solution:
    def mySqrt(self, x: int) -> int:
        """
            x 的平方根(非最优解, 二分搜索，结果整数)

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

            输入: 8
            输出: 2
            说明: 8 的平方根是 2.82842...,
                 由于返回类型是整数，小数部分将被舍去。
        """
        left = 0
        right = math.ceil(x / 2)
        res = 0
        while left <= right:
            mid = left + (right - left) // 2
            tmp = mid * mid
            if tmp == x:
                return mid
            elif tmp < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

解答4

class Solution:
    def mySqrt(self, x: float, precision: int) -> int:
        """
            x 的平方根(二分搜索，结果浮点数)

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

            输入: 8
            输出: 2
            说明: 8 的平方根是 2.82842...,
                 由于返回类型是整数，小数部分将被舍去。
        """
        i, j = 0, x / 2 + 1
        limit = 1 / 10 ** precision
        while i <= j:
            mid = (i + j) / 2
            if mid ** 2 == x:
                return round(mid, precision)
            elif mid ** 2 < x:
                i = mid + limit
            else:
                j = mid - limit
        return round(j, precision)

解答5

class Solution:
    def mySqrt(self, x: float, precision: int) -> int:
        """
            x 的平方根(二分搜索，结果浮点数)

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

            输入: 8
            输出: 2
            说明: 8 的平方根是 2.82842...,
                 由于返回类型是整数，小数部分将被舍去。
        """
        return int(x ** 0.5)