Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

SOLUTION 1:

参见：二分法总结，以及模板：http://t.cn/RZGkPQc

 public class Solution {

     public int sqrt(int x) {

         if (x == 1 || x == 0) {

             return x;

         }

         int left = 1;

         int right = x;

         while (left < right - 1) {

             int mid = left + (right - left) / 2;

             int quo = x / mid;

             if (quo == mid) {

                 return quo;

             // mid is too big

             } else if (quo < mid) {

                 right = mid;

             } else {

                 left = mid;

             }

         }

         return left;

     }

 }

其实这里有一个非常trick地地方：

就是当循环终止的时候，l一定是偏小，r一定是偏大（实际的值是介于l和r之间的）：

比如以下的例子，90开根号是9.48 按照开方向下取整的原则, 我们应该返回L.

以下展示了在循环过程中，L,R两个变量的变化过程

1. System.out.println(sqrt(90));

L R

1 45

1 23

1 12

6 12

9 12

9 10

2. System.out.println(sqrt(20));

1 10

1 5

3 5

4 5

3. System.out.println(sqrt(3));

1 2

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/divide2/Sqrt.java

巴特西

LeetCode:Sqrt(x) 解题报告

Sqrt(x)

SOLUTION 1:

GITHUB:

最新文章

热门文章