leetcode15 Sqrt(x)

灰太狼 2021-12-14 04:47 142阅读 0赞

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.

给一个非负数x整形，然后给其开方，得到结果，如果结果是一个非整形，需要只取整数部分。

我直接就用了java中的Math类中的sqrt函数，然后对其调用结果，进行了强制类型转化，去掉小数点后面的值。

代码实现如下：

class Solution {
        public int mySqrt(int x) {
            return (int)Math.sqrt(x);
        }
    }

Runtime: 1 ms, faster than 100.00% of Java online submissions for Sqrt(x).
    Memory Usage: 32.2 MB, less than 100.00% of Java online submissions for Sqrt(x).

然而我想看一下java中sqrt的源码，但是它是`StrictMath`类中的一个静态本地方法，具体的实现没有办法看到。

discuss中的一些解法：

关于sqrt(x)的数学思想：https://en.wikipedia.org/wiki/Integer\_square\_root\#Using\_only\_integer\_division

class Solution {
        public int mySqrt(int x) {
             long r = x;
            while (r*r > x){
                r = (r + x/r) / 2;
            }
    
            return (int) r;
        }
    }

class Solution {
        public int mySqrt(int x) {
             if(x <= 0) return 0;
            int l = 1, r = x, res = 1;
            while(l < r) {
                int mid = (l + r) / 2;
                if(mid > x/mid) {
                    r = mid;
                } else {
                    res = mid;
                    l = mid + 1;
                }
            }
            return res;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20211213/0b8feafbabf2434998732e2aaba71017.png