• Leetcode刷题详解——x的平方根


    1. 题目链接:69. x 的平方根

    2. 题目描述:

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

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

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

    示例 1:

    输入:x = 4
    输出:2
    
    • 1
    • 2

    示例 2:

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

    提示:

    • 0 <= x <= 231 - 1

    3. 解法1(暴力枚举)

    3.1 算法思路:

    依次枚举[0,x]之间的所有数:

    • 如果i*i==x,直接返回i
    • 如果i*i>x,说明返回的结果是前一个数i-1

    3.2 C++算法代码:

    class Solution {
    public:
        int mySqrt(int x) {
            //两个较大的数相乘可能会超出int的范围,为了防止溢出,使用long long类型
            long long i=0;
            for(i=0;i<=x;i++)
            {
                //如果两个数想乘正好等于x,直接返回i
                if(i*i==x) return i;
                //如果第一次出现两个数相乘大于x,返回前一个数
                if(i*i>x) return i-1;
            }
            return -1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    4. 解法2(二分查找)

    4.1 算法思路:

    x平方根的最终结果为index

    index左右两次数据的特点:

    • [0,index]之间的元素,平方之后都是小于等于x
    • [index+1,x]之间的元素,平方之后都是大于x

    请添加图片描述

    4.2 C++算法代码:

    class Solution {
    public:
        int mySqrt(int x) {
            if(x<1) return 0;
            int left=1,right=x;
            while(left
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    Dataset之GermanCreditData:GermanCreditData数据集的简介、下载、使用方法之详细攻略
    Python专题复习整理
    给openlab搭建web网站
    Devart ODBC Driver for BigCommerce 2.0.1
    springboot+mybatis-plus-join+mysql实现连表查询
    php连接上mysql数据库该的配置方法
    (零代) MDD 开创低代码领行设计模式
    Hadoop:认识MapReduce
    c语言:查漏补缺(二)
    C/C++语言知识
  • 原文地址:https://blog.csdn.net/weixin_51799303/article/details/134022575