Implement int sqrt(int x).
Compute and return the square root of x.
题意很简单，求一个数的开方，这里都是int型的 最近一直在上课学R，偷懒没有刷leetcode，隔了这些天手生了，一道easy做了好久，还用的不怎么样的方法，接下来要坚持每天至少一道，又不会太费时间，很想念前些天上洗手间路上都可以思考，这是多么一件事半功倍的事情，记住题目就好，不需要时时刻刻盯着电脑，思考就可以啦！ 自己的思路如下： 相当于取了两个指针 start和end，start起始为0， end起始为x本身，然后每次取二者和的中间值，看其平方是否大于或者小于x, 然后决定赋值给start或者end， 在真正执行代码过程中，这个思路可能写的复杂了，踩了很多坑， start最后收敛的可能不准，所以分别取ceil和floor测试是否平方是x, 如果仍然不是，那么再看其上下差2的取值区间，因为有很多并不是平方就完全等于x,而是向下取整了。所以判断的时候，也相应的当 res+i 的平方开始大于x的时候，就是分界线，这时候取 res+i-1，即前一个数就是所求 class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ # use the method of bisection if x == 0: return 0 start=0 end=x while (end - start) > 0.1 : temp = (start + end)*(start + end)/4.0 if temp > x: end = (start + end)/2.0 #elif temp < x: # start = (start + end)/2.0 else: start = (start + end)/2.0 #return int(round((start + end)/2.0)) restemp = int(math.ceil(start)) restemp2 = int(math.floor(start)) if restemp*restemp == x: res = restemp else: res = restemp2 if res*res != x: for i in [-1, -2, 1, 2]: if (res+i)*(res+i) > x: res = res+i-1 break if res > 0: return res #restemp*restemp,x,int(restemp*restemp) == x,res,restemp,restemp2 else: return 1 这里敲黑板， 牛顿迭代法，真好用！！ 提供两篇博文，几分钟就可以理解实践了 牛顿迭代法图解 牛顿迭代法公式的推导 以上两篇博文分别下拉就看见相关内容了