LeetCode_69. x 的平方根(二分法和数学公式代换 Java实现)

题目描述：69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

解题思路：

思路1：二分法

看到题目后的第一个想法便是二分法，直接用，也没啥好多想的。

class Solution {
    public int mySqrt(int x) {
        int right=x,left=0,ans=-1;
        while(left<=right){
            int curr=left+(right-left)/2;
            if((long)curr*curr <= x){
                ans=curr;
                left=curr+1;
             
            }else{
                right=curr - 1;  
            }
        }
        return ans;
    }
}

思路2：数学代换公式

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}

最后，附上题目链接：
https://leetcode-cn.com/problems/sqrtx/