69. x 的平方根 [easy]

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

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

通过次数168,836 | 提交次数435,526

Second Try

2020-07-03

不来一波牛顿法不死心, 不过推理过程还是出现各种问题，基础的数学能力退化太严重了。

# 不来一波牛顿法不死心
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:  # 不然又出现除0，浪费了一次提交。。
            return 0 
        x0, c = x, x  # 起点选为c
        x1 = x0/2.0 + c/(2.0 * x0)  # 需要用浮点数才行 
        while x0 - x1 > 10 ** -6:
            # print(x0, x1)
            x0, x1 = x1,  x1/2.0 + c/(2.0 * x1) 
        # print(x0, x1, x1**2)
        return int(x1)

执行用时：24 ms, 在所有 Python 提交中击败了95.05%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了10.00%的用户

First Try

2020-07-02

还是用二分法查找点，使得a^2 <= x。难点依然是确定最后使用left还是right，经过一轮分析直接使用right就行了，跟之前0035题的插入位置相反。

牛顿迭代法还是不太想去了解，用上编程就是想无脑一波流。。。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        
        left, right = 0, x
        while left <= right:
            mid = (left + right) / 2
            if mid * mid < x:
                left = mid + 1
            elif mid * mid > x:
                right = mid - 1
            else:
                return mid
        # 在left = right = mid之后
        # 1. 如果 mid * mid < x, 则 left = mid + 1, 导致left * left 大于 x， 而right * right < x
        # 2. 如果 mid * mid > x, 则 right = mid - 1, 导致right * right 小于x, 而left * left > x
        # 3. 如果 right = mid - 1导致right小于0，则right应该保持为0
        # 但是由于x为非负整数，好像并没有情况可以使得right小于0，所以不需要处理
        return right

执行用时：32 ms, 在所有 Python 提交中击败了72.64%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了10.00%的用户

69. x 的平方根 [easy]​

Second Try​

First Try​

69. x 的平方根 [easy]

Second Try

First Try