NC32 求平方根

二刷

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if(x == 0){ return 0;}
        if(x<=3){return 1;}
        if(x<=8){return 2;}
        long y = x;
        long left = 0;
        long right = y;
        while(left<right){
            long mid = (left + right) /2;
            if(mid*mid<=y && (mid+1)*(mid+1)>y) return (int)mid;
            else if(mid*mid > y) right = mid-1;
            else if(mid*mid < y) left = mid + 1;
        }
        // 出循环了 说明 left = right
        return (int)left;
    }
}

1.
暴力

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if(x == 0){ return 0;}
        if(x<3){return 1;}
        int res = 0;
        for(int i=0; i<x ;i++){
            if( i*i == x ){res = i; break;}
            else if(i*i > x){res = i-1; break;}
        }
        return res;
    }
}

2.
二分法
使用逆向运算 避免溢出 要么使用 long

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if(x == 0){ return 0;}
        if(x<=3){return 1;}
        if(x<=8){return 2;}
        int res = 0;
        int left = 0;
        int right = x;
        while(left<=right){
            int mid = (left + right) >> 1;
            if(mid <= x / mid && (mid+1) > x / (mid+1)){res = mid; break;}
            if(mid > x/mid ){right = mid-1;}
            if(mid < x/mid ){left = mid+1;}
        }
        return res;
    }
}