【力扣】69. 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


解题方案

暴力破解

  • C
int mySqrt(int x) {
    for(long i = 0; i < 65536; i++)
    {
        if(i * i <= x && (i + 1) * (i + 1) > x)
        {
            return i;
        }
    }
    return 0;
}


二分法

  • C
int mySqrt(int x) {
    int left = 0, right = x / 2, mid = 0; 
    if (x == 0) 
    {
        return 0;
    }
    if (x == 1) 
    {
        return 1;
    }
    while (left < right)
    {
        mid = left + (right - left + 1) / 2;
        if (mid > x / mid)
        {
            right = mid - 1;
        }
        else
        {
            left = mid;
        }
    }
    return left;
}



相关文章
|
8月前
|
存储
leetcode:69. x 的平方根
利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。
47 0
YI
|
10月前
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
62 0
力扣69x的平方根
力扣69x的平方根
41 0
|
前端开发 Go 对象存储
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
|
前端开发 算法 JavaScript
LeetCode 未知数的平方根使用JavaScript解题|前端学算法
LeetCode 未知数的平方根使用JavaScript解题|前端学算法
112 0
LeetCode 未知数的平方根使用JavaScript解题|前端学算法
|
算法 Serverless
LeetCode 67二进制求和&68文本左右对齐&69x的平方根
给你两个二进制字符串,返回它们的和(用二进制表示)。
171 0
LeetCode 67二进制求和&68文本左右对齐&69x的平方根
|
Serverless
LeetCode 69. x 的平方根
LeetCode 69. x 的平方根
LeetCode 69. x 的平方根
怒刷力扣(x的平方根)
X的平方根,看到这个题的第一感觉就是倒推,使用平方的形式。但是最关键还是要想到二分法来计算这个过程。
77 0
怒刷力扣(x的平方根)