leetcode：69. x 的平方根

题目

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例：

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解答 & 代码

解法一：二分查找

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        while(left <= right)
        {
            long mid = left + (right - left) / 2;
            if(mid * mid == x)
                return mid;
            else if(mid * mid < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
};

复杂度分析：

• 时间复杂度 O(log x)：即二分查找需要的次数
• 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 69.96% 的用户

解法二：牛顿迭代法

[容易] 69. x 的平方根

解法三：梯度下降法

梯度下降参数更新公式：

迭代，直到（eg. 1e-7）

1. 对于函数，要求其值为 0 时参数 z 的值，要用梯度下降法求解，那么就要设置合适的损失函数，让损失函数不断减小。
2. 因此，损失函数可以设置为 ，这样当 f(z) 取 0 时损失函数最小
3. 因此损失函数关于参数 z 的梯度：
4. 梯度下降更新参数 z：

class Solution {
public:
    double mySqrt(int x) {
        if(x == 0)
            return 0;

        double C = x;
        double z = C / 2;        // z 初始值
        double lr = 0.01;        // 学习率
        while(true)
        {
            double fz = z * z - C;        // 函数 f(z) = z^2 - C

            // 如果达到指定精度，则停止迭代
            if(abs(fz) < 1e-7)
                break;

            double loss = fz * fz;                // 损失函数 loss = fz^2 = (z^2-C)^2
            double dloss_fz = 2 * fz;            // loss 关于 fz 的梯度
            double dfz_z = 2* z;                // fz 关于 z 的梯度
            double dloss_z = dloss_fz * dfz_z;    // loss 关于 z 的梯度
            z = z - lr * dloss_z;                // 梯度更新：z = z - lr*梯度
        }
        return z;
    }
};