【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找—day3

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找—day3,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

在这里插入图片描述

在这里插入图片描述

题目描述

链接: 69. x 的平方根/Sqrt(x)

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

题目分析:

代码分析:

❌错误代码分析:(2023/1/25)

class Solution {
    public int mySqrt(int x) {
        //特例判断,因为x/2>=根号x,在x>=2的时候成立
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;//防止溢出

            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

  • 2023/1/25:因为没有考虑乘法溢出:mid*mid<=x,当mid过大时乘法溢出。(一开始还忘记了在mid = left+(right-left+1);中的+1,导致了死循环,实在不该,谨记判断是否+1就看只剩两个元素时,mid的取值和区间划分能否缩小区间?若不能,必定死循环
  • 在这里插入图片描述

✅正确代码:

class Solution {
    public int mySqrt(int x) {
        //特例判断,因为x/2>=根号x,在x>=2的时候成立
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;//防止加法溢出
            if (mid <= x / mid) {//防止乘法溢出
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}



write in the end:

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142455.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!