LeetCode第69题 – x 的平方根

104 views

题目

解答

方案一

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 的平方根

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud