LeetCode-069-x的平方根

Posted on | Edited on | In | Views:

LeetCode-069-x的平方根

1. 题目：

x 的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

2. 解题

使用牛顿迭代法。

参考文章：如何通俗易懂地讲解牛顿迭代法？

使用牛顿迭代会比二分法进行更少的计算次数。

首先我们设函数:$$f(x) = x^2 - a(a是要求平方根的常数)$$

则求导为：
$$
f’(x) = 2x
$$

根据
$$
f(x_n)+f’(x_n)(x - x_n) = 0
$$

得到迭代公式：
$$
x_{n+1} = x_n - f(x_n)/f’(x_n)
$$
当满足条件x^2 <= a && (x+1)^2 > a时得到结果，需要注意x^2会导致int溢出问题，我们使用long来避免这个问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int mySqrt(int x) {
        if (x < 0)
            return -1;
        if (x <= 1)
            return x; 
        //　猜想数
        long res = x/2;
        while (!(res * res <= x && (res + 1) * (res + 1) > x)) {
            res = (res + x/res) / 2;
        }
        return (int)res;
    }
}