当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

LeetCode69.x的平方根.🌟🌟🌟🌟🌟简单

算法系统课 免费

问题描述

原题链接：69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

限制：

  • 0 <= x <= 231 - 1

代码

Java

    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        while(l <= r){
            if(r - l <= 1){
                return r * r > x ? l : r;
            }
            int mid = l + ( r - l) /2;
            if((long)mid*mid > x){
                r = mid - 1;
            } else if((long)mid*mid == x){
                return mid;
            } else {
                l = mid;
            }
        }

        return -1;
    }

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x
        while l <= r:
            if r - l <= 1:
                return l if r * r > x else r
            mid = l + (r - l) // 2
            if mid * mid > x:
                r = mid - 1
            elif mid * mid == x:
                return mid
            else:
                l = mid
        return -1

C++

class Solution {
public:
    int mySqrt(int x) {
        int l = 0;
        int r = x;
        while (l <= r) {
            if (r - l <= 1) {
                return r * r > x ? l : r;
            }
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid > x) {
                r = mid - 1;
            } else if ((long long)mid * mid == x) {
                return mid;
            } else {
                l = mid;
            }
        }
        return -1;
    }
};

Go

func mySqrt(x int) int {
    l := 0
    r := x
    for l <= r {
        if r-l <= 1 {
            if r*r > x {
                return l
            } else {
                return r
            }
        }
        mid := l + (r-l)/2
        if mid*mid > x {
            r = mid - 1
        } else if mid*mid == x {
            return mid
        } else {
            l = mid
        }
    }
    return -1
}

发表回复

后才能评论

评论(11)

  • 我来吃饭啦 永久会员 2024年6月15日 上午9:01
    • 使得保证hh永远大于x
      class Solution:
      def mySqrt(self, x: int) -> int:
      l = 0
      h = x
      while l <= h:
      if h – l <= 1:
      return l
      mid = l + (h – l)//2
      if mid      mid > x:
      h = mid
      elif mid*mid < x:
      l = mid
      else:
      return mid
      return -1
  • ？ 普通 2024年3月3日 上午11:39

    打卡

  • Yuki 永久会员 2024年1月23日 下午1:08

    DAY 2
    2/3
    https://flowus.cn/share/e47ad9b3-8389-414f-8163-7881ce0e7661
    【FlowUs 息流】69. x 的平方根

  • 重明鸟 永久会员 2023年10月15日 下午6:55 
    class Solution {
    public int mySqrt(int x) {
        if(x == 0) { // 因为用÷，小心除0异常
            return 0;
        }
        int l = 0;
        int r = x;
        while(l < r-1) { // 区间仅俩数时单独讨论
            int mid = l+(r-l)/2;
            if(mid < x/mid) {
                l = mid; // l = mid 仍可能是目标值
            } else if (mid > x/mid) { // x改÷防止溢出
                r = mid-1;
            } else {
                return mid;
            }
        }
        if(r > x/r) {
            return l;
        } else {
            return r;
        }
    }
}
  • DataSpace 普通 2023年9月25日 上午11:45

    打卡

  • 泡芙 永久会员 2023年8月24日 上午11:31 
    //求下界
class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        while (l <= r) {
            // 只剩下一个数时，就是目标值
            // if (l == r) {
            //     return l;
            // }

            // 由于l=mid，当只剩下2个数时就会进入死循环
            // 剩下2个数时判断哪个数是目标值
            if (r - l <= 1) {
                return r * r > x ? l : r;
            }
            int mid = l + (r - l) / 2;
            if ((long)mid * mid > x) {
                r = mid - 1;
            } else if ((long)mid * mid < x) {
                l = mid; // 注意：不能写mid+1,此时的mid不能跳过
            } else {
                return mid;
            }
        }
        return -1;
    }
}
  • 阿尚 普通 2023年8月15日 下午11:43 
    class Solution {
    public int mySqrt(int x) {
       //求下界：相当于求小于等于target的最右边的数
        int left = 0, right = x, ans = -1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)mid * mid <= x){//判断条件
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return ans;
    }
}
  • Brown 普通 2023年7月11日 下午8:11

    打卡
    class Solution {
    public int mySqrt(int x) {
    int l = 1;
    int r = x;
    int candidate = 0;
    while(l <= r){
    int mid = l + (r – l) / 2;
    if((long) mid * mid > x){
    r = mid – 1;
    }else if((long) mid * mid < x){
    candidate = mid;
    l = mid + 1;
    }else{
    return mid;
    }
    }
    return candidate;
    }
    }class Solution {
    public int mySqrt(int x) {
    int l = 1;
    int r = x;
    int candidate = 0;
    while(l <= r){
    int mid = l + (r – l) / 2;
    if((long) mid * mid > x){
    r = mid – 1;
    }else if((long) mid * mid < x){
    candidate = mid;
    l = mid + 1;
    }else{
    return mid;
    }
    }
    return candidate;
    }
    }

  • 帅气的冬瓜 普通 2023年6月2日 下午5:42

    打卡

  • sasuke 普通 2023年4月11日 下午3:07

    您好，这个不能用sqrt()直接开根取整数 这种解法吗？

    • shuaidi 永久会员 @ sasuke 2023年4月11日 下午3:09

      不可以哦，你这样的话，就失去了做这道题的意义了哈，而且题目要求也限制你不能使用库函数哦

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理