【LeetCode】Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

题意:题目要求实现sqrt()函数,当然不能直接使用sqrt啦(不然就没意义了)

C++:考虑 long int,非负输入,考虑好0

class Solution {
public:
    int mySqrt(int x) {
        if(x==1||x==0)return x==1?1:0;
        long long int i;
        for(i=2;i*i<=x;i++);
        return i-1;
    }
};

Python3:牛顿迭代法(具体学习可以参考马同学:https://blog.csdn.net/ccnt_2012/article/details/81837154

这种算法的原理很简单,我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根,这个函数的导数是2x。也就是说,函数上任一点(x,f(x))处的切线斜率是2x。那么,x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x),也就是(x+a/x)/2。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x<=1:
            return x
        r = x
        while r > x/r:
            r = (r + x / r) // 2
        return int(r)

 

上一篇:三角函数及部分微积分函数图象整理


下一篇:Crack SFS 2X license file