解答
方案一
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } for (int i = 2, length = Math.min(46342, x / 2 + 2); i < length; ++i) { int value = i * i; if (value == x) { return i; } if (value > x || value < 0) { return i - 1; } } return 0; } }
方案二
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } for (int i = Math.min(46340, x / 4 + 1); i > 1; --i) { long value = i * i; if (value == x) { return i; } if (value > 0 && value < x) { return i; } } return 0; } }
方案三
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } for (int length = Math.min(46342, x / 2 + 2); true;) { int value = length * length; if (value == x) { return length; } if (value < x && value > 0) { return length; } length = (length + x / length) / 2; } } }
方案四
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } for (int start = 1, end = Math.min(46342, x / 2 + 2); true;) { int mid = (start + end) / 2; if (mid == start || mid == end) { return mid; } int value = mid * mid; if (value == x) { return mid; } if (value < 0 || value > x) { end = mid; } else { start = mid; } } } }
方案五
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } if (x < 4) { return 1; } int min = 0; int max = x; while (max - min > 1) { int m = (max + min) / 2; if (x / m < m) { max = m; } else { min = m; } } return min; } }
要点
方案一和方案二是直接求解。
方案三,使用牛顿迭代法,不过实现并不优雅。
方案四,使用二分查找或者折半查找,不过实现并不优雅,使用除法来协助判定当前迭代的值是否满足要求,应该可以规避溢出的问题。
方案五,同样使用了二分查找,相对要优雅一点。
在实现时,需要注意边界值,比如从0,1,2,3,4以及46342、46340。
整型最大值的平方根,取整之后为46340,因此可以作为迭代的上限值。
准备的用例,如下
@Before public void before() { t = new Solution(); } @Test public void test001() { assertEquals(2, t.mySqrt(8)); } @Test public void test002() { assertEquals(2, t.mySqrt(4)); } @Test public void test003() { assertEquals(1, t.mySqrt(3)); } @Test public void test004() { assertEquals(1, t.mySqrt(2)); } @Test public void test005() { assertEquals(2, t.mySqrt(5)); } @Test public void test006() { assertEquals(46340, t.mySqrt(2147483647)); }
若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第69题 – x 的平方根