題目 : 69. Sqrt(x)
Given a non-negative integerx, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.- For example, do not use
pow(x, 0.5)in c++ orx ** 0.5in python.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
1.
x = 8
解題思路
依照題目所說的取最接近小於等於該開根號後所得出的整數部分，所以答案是i
class Solution:
def mySqrt(self, x: int) -> int:
# 先將例外的例子，如0和1先行做判斷
# 0和1的根號分別都是0和1，所以可以直接回傳本身的數字
if x == 0 or x == 1:
return x
# 思路如上圖所示
for i in range(x):
if i*i <= x and x < (i+1)*(i+1) :
return i