leetcode刷题网站,leetcode刷题指南

1. 题目链接69. x 的平方根 2. 题目描述

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

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

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

示例 1

输入x  4输出2

示例 2

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

提示

0 < x < 231 - 1 3. 解法1暴力枚举 3.1 算法思路

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

如果i*ix直接返回i如果i*i>x说明返回的结果是前一个数i-1 3.2 C算法代码

class Solution {public:    int mySqrt(int x) {        //两个较大的数相乘可能会超出int的范围为了防止溢出使用long long类型        long long i0;        for(i0;i<x;i)        {            //如果两个数想乘正好等于x直接返回i            if(i*ix) return i;            //如果第一次出现两个数相乘大于x,返回前一个数            if(i*i>x) return i-1;        }        return -1;    }};

4. 解法2二分查找 4.1 算法思路

设x的平方根的最终结果为index

index左右两次数据的特点

[0,index]之间的元素平方之后都是小于等于x的[index1,x]之间的元素平方之后都是大于x的 4.2 C算法代码

class Solution {public:    int mySqrt(int x) {        if(x<1) return 0;        int left1,rightx;        while(left<right)        {            long long midleft(right-left1)/2;            if(mid*mid<x) leftmid;            else rightmid-1;        }        return left;    }};