069 sqrt(x)
69. Sqrt(x)
题目: https://leetcode.com/problems/sqrtx/
难度:
Medium
思路：
一看，觉得很容易，一写，超时：
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
i = 0
while i * i <= x :
if i * i == x:
return i
elif i * i < x and (i+1) * (i+1) > x:
return i
i += 1
看一眼tag， binary search，难道从x/2之类的开始搜起来？话说还想到求sqrt有个🐂的牛顿法？
莫名其妙过了的代码：
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 1 : return 1
if x == 0 : return 0
l, r = 0, x - 1
while l <= r:
mid = l + ((r - l) >> 2)
if mid * mid <= x and (mid+1)*(mid+1) > x:
return mid
elif mid * mid > x:
r = mid - 1
else:
l = mid + 1
或者
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 1:
return 1
if x == 0:
return 0
l, r = 0, x-1
while l <= r:
mid = l + ((r - l) >> 2)
if (mid * mid - x == 0):
return mid
elif (mid * mid - x > 0):
r = mid - 1
else:
l = mid + 1
return r
牛顿法
参见wikipedia，to be done：自己推导一遍 https://zh.wikipedia.org/wiki/牛顿法
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
res = 1.0
while abs(res * res - x) > 0.1:
res = (res + x / res) / 2
return int(res)
