首页 > 其他 > 详细

69. Sqrt(x)

时间:2017-02-15 12:36:24      阅读:177      评论:0      收藏:0      [点我收藏+]

题目:

Implement int sqrt(int x).

Compute and return the square root of x.

链接:   http://leetcode.com/problems/sqrtx/

2/14/2017, Java,不是自己想的。。。

二分法,需要进行第3行的判断

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         if (x <= 1) return x;
 4 
 5         int lo = 0, hi = x;
 6         int mid;
 7         
 8         while( lo <= hi) {
 9             mid = lo + (hi - lo) / 2;
10             if (mid < x / mid) {
11                 lo = mid + 1;
12             } else if (mid > x / mid) {
13                 hi = mid - 1;
14             } else {
15                 return mid;
16             }
17         }
18         return hi;
19     }
20 }

牛顿法,肯定也不是自己想的。

还是注意input = 1的情况

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         if (x <= 1) return x;
 4         
 5         double lastY = x / 2;
 6         double Y = (lastY + x / lastY) / 2;
 7         
 8         while (Y != lastY) {
 9             lastY = Y;
10             Y = (lastY + x / lastY) / 2;
11         }
12         return (int)Y;
13     }
14 }

 

69. Sqrt(x)

原文:http://www.cnblogs.com/panini/p/6400691.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!