leetcode--69. xの平方根
テーマ:69.xの平方根
リンク:https://leetcode-cn.com/problems/sqrtx/
xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.
例1:
例2:
私の最初の反応は二分ですね.これでいいかどうか分かりません.二区分間【1,k】は、中点値の二乗がkより大きい場合は、半間区間を外し、そうでない場合は半間区間をとり、区間端点値が一差になるまで二分を継続する.
python:
リンク:https://leetcode-cn.com/problems/sqrtx/
int sqrt(int x)
関数を実装します.xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.
例1:
: 4
: 2
例2:
: 8
: 2
: 8 2.82842...,
, 。
私の最初の反応は二分ですね.これでいいかどうか分かりません.二区分間【1,k】は、中点値の二乗がkより大きい場合は、半間区間を外し、そうでない場合は半間区間をとり、区間端点値が一差になるまで二分を継続する.
python:
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0 or x==1:
return x
low=1
high=x
while high-low>1:
mid=(low+high)//2
if mid*mid>x:
high=mid
else:
low=mid
return low