C/C++教程

Leetcode No.69 Sqrt(x)开根号(c++实现)

本文主要是介绍Leetcode No.69 Sqrt(x)开根号(c++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 题目

https://leetcode.com/problems/sqrtx/

2. 分析

2.1 牛顿迭代法

牛顿迭代法是一种求解非线性方程的一种数值方法。具体原理可以参考:https://blog.csdn.net/u014485485/article/details/77599953
具体代码如下:

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) { return 0; }
        int r = x;
        while (r > x / r) {
            r = x / r + (r - x/ r) / 2;
        }
        return r;
    }
};

代码参考:https://leetcode.com/problems/sqrtx/discuss/25057/3-4-short-lines-Integer-Newton-Every-Language

2.2 二分法

具体代码如下:

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

代码参考:https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution

这篇关于Leetcode No.69 Sqrt(x)开根号(c++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!