Leetcode 69:x的平方根

题目描述:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842...,由于返回类型是整数,小数部分将被舍去。

解法一:暴力法

思路:暴力法的思路很简单,就是从1开始遍历到x。

(1)如果index的平方小于等于x,则继续遍历。

(2)如果index平方大于x,则直接返回index-1。

注意:关于index的类型,如果使用int,则在判断条件处使用index <= x/index来作为条件,防止溢出。如果index类型是long,则判断条件处可使用index*index<=x。

代码:

class Solution {
    public int mySqrt(int x) {
        int index =1;
        while(index <= x/index){
            index ++;
        }
        return index-1;
    }
}

解法二:二分查找。

思路:

对x进行二分查找,在每次进行二分查找的过程中,只需要比较中间元素的平方值和x的大小即可。如果mid的平方比x大,则让right = mid-1;如果mid的平方比x小,则left = mid + 1。

注意:为了防止溢出,在判断的时候采用mid == x/mid来判断是否相等。

代码:

class Solution {
    public int mySqrt(int x) {
        int left = 1, right = x;
        int mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(mid < x/mid){
                left = mid + 1;
            }else if(mid == x/mid){//避免乘法溢出
                return mid;
            }else{
                right = mid -1;

            }
        }
        return right;
    }
}

解法三:牛顿迭代法。

思路:

如果n^2=x,则可以变为n=x/n。如果n的平方就是x,那么n和x/n的值是相等。以12为例:12=2 * 6 ,如果n=2是x的平方根,那么x/n就应该等于n,然而并不是,那么此时就可以取n和x/n的平均值,也就是4,这样就可以更加逼近12。因为2的平方是4,6的平放方是36,而4的平方则是16,更加接近12。通过这样不断地迭代,就可以得到最终的结果。因此,总结出公式:假设变量为val,则每次迭代 val = ( val + x / val) /2。

代码:

class Solution {
    public int mySqrt(int x) {
        long right = x;
        while(right * right > x){
            right = (right + x/right)/2;
        }
        return (int)right;
    }
}

还有一种办法就是直接使用Java的库:Math.sqrt()。

上一篇:【SNMP】Linux系统下安装net-snmp


下一篇:69. x 的平方根