LeetCode69 x的平方根

发表于 | 分类于 |
字数统计: 183 | 阅读时长 ≈ 1

链接： https://leetcode.cn/problems/sqrtx/

题意

给定x，计算x的算术平方根（整数）

解法

  1. 二分，注意边界
  2. 牛顿迭代法
    不断计算 x 和 x / root 的平均值，并将结果赋给root
    直到符合精度
    也可以看作是基本不等式 x + a /x >= 2sqrt(a)

代码

二分

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

牛顿迭代

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int mySqrt(int x) {
        double root = x;
        while(fabs(root * root - x) > 1e-5) {
            root = root + x / root;
            root /= 2;
        }
        return int(root);
    }
};