leetcode——69.x的平方根

超出时间限制。。

class Solution:
    def mySqrt(self, x: int) -> int:
        for i in range(0,x//2+2):
            if x>=i**2 and x<(i+1)**2:
                return i

好气哦。。。加油想想怎么改进。。。

修改以后通过，但是还是太好，修改了将近40分钟，好没有效率啊：

class Solution:
    def mySqrt(self, x: int) -> int:
        i=x
        m=[x]
        while i>=0:
            if i**2>x:
                m[0]=i
                i=i//2
            elif x>=i**2 and x<(i+1)**2:
                return i
            else:
                i=(i+m[0])//2

执行用时 :144 ms, 在所有 Python3 提交中击败了5.80%的用户

内存消耗 :13.9 MB, 在所有 Python3 提交中击败了5.22%的用户

 

别人的做法好简单，我就是太愚钝。。。。。。

                                                                                                                        ——2019.9.25

 

---

做是做出来了

public int mySqrt(int x) {
        int n = x/2;
        if(n == 0){
            return x;
        }
        return sqrt(x,n);
    }

    private int sqrt(int x, int n) {
        if(x/n == n || (x/n>n && x/(n+1) < (n+1))){
            return n;
        }else if(x/n<n){
            return sqrt(x,n/2);
        }else{
            int m = n;
            while(x/n!=n){
                if(x/n==n){
                    return x;
                }else if(x/n>n){
                    n = n + m/2;
                }else{
                    n = n - m/2;
                }
                m = m/2;
                if(m == 0){
                    if(x/n<n){
                        while(x/n<n){
                            n--;
                        }
                        return n;
                    }else if(x/n>n){
                        while (x/n>=n){
                            n++;
                        }
                        return n-1;
                    }
                }
            }
            return n;
        }
    }

public int mySqrt(int x) {
        int left = 1,right = x/2;
        int mid;
        int last_mid = 1;
        if(x<2) return x;
        while(left<=right){
            mid = left+(right-left)/2;
            if(x/mid > mid){
                left = mid+1;
                last_mid = mid;
            }else if(x/mid < mid){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return last_mid;
    }

——2020.8.4