1, 题目

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

  1. 输入: 4
  2. 输出: 2

示例 2:

  1. 输入: 8
  2. 输出: 2
  3. 说明: 8 的平方根是 2.82842...,
  4.     由于返回类型是整数，小数部分将被舍去。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. #python
  2. object Solution {
  3.     def mySqrt(x: Int): Int = {
  5.         if (x==0 || x == 1) {
  6.             return x
  7.         }
  8.         for (i <- Range(1, x)) {
  9.             if (i <= x / i && x / (i + 1) < (i + 1)) {
  10.                 return i
  11.             }
  12.         }
  13.         1
  14.     }
  15. }
  1. #python
  2. class Solution:
  3.     def mySqrt(self, x: int) -> int:
  4.         if x < 2:
  5.             return x
  6.         for i in range(1, x):
  7.             if i <= x / i and x / (i + 1) < i + 1:
  8.                 return i