LeetCode小白菜笔记[17]：Sqrt(x)

69. Sqrt(x) [easy]

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

题目要求很简单，就是对整数开根号。

先试试最枚举的暴力方法，看看有没有时间限制：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        i = 0
        while (i+1) * (i+1) <= x:
            i += 1
        return i

time limit excess 。。。果然有时间限制。考虑其他方法。实际上这就是一个对于从0~n的整数里面查找满足条件的整数的问题，既然是查找，那就可以二分来做。另外，考虑这个问题可以看做是函数求零点，或者说是方程求根问题，而且要求是整数，对精度要求这么低，可以牛顿迭代。

考虑牛顿迭代，对于 $f (x) = 0$ ，可以构造 $y = f (x)$ ，求其零点。对于一个guess，比如 $x_{0}$ ，那么有在此处的切线：

y = f^{^{'}} (x_{0}) (x - x_{0}) + f (x_{0})

点斜式方程，这个线性方程的零点就是：

x = - \frac{f (x_{0})}{f^{^{'}} (x_{0})} + x_{0}

如果我们对于这个零点作为下一个guess，重复以上步骤，这就是牛顿迭代，所以上式中的 $x$ 和 $x_{0}$ 可以写成 $x_{n + 1}$ 和 $x_{n}$ ，就变成了迭代公式。对于本问题，一个特例就是：

y = f (x) = x^{2} - a

，其中a就是我们要求根的那个数字。所以迭代公式为：

x_{k + 1} = \frac{1}{2} (x_{k} + \frac{a}{x_{k}})

以a为第一次guess，可以迭代，因为精度要求是整数部分即可，又由于牛顿迭代的误差是越来越小的，又因为二次函数是凸的，切线应该在下面，所以数值应该是逐渐减小的，因此找到第一个整数部分的平方小鱼等于a的即可，code如下：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        rt = x
        while int(rt) * int(rt) > x:
            rt = 0.5 * ( rt + x / rt )
        return int(rt)

就这几句。。。结果通过。但是比较慢，125ms，超过百分之4.5，后来发现，第一个guess不必从x开始，可以从x/2+1即可，再测试，结果：

69ms，12.17%，还是比较慢，但是有提高。

2018年2月10日01:45:36

夜深了，睡觉~