力扣69x的平方根

简介: 力扣69x的平方根

力扣69x的平方根

思路就是:

1.建立一个vector数组去保存数据,数据范围为1-n/2,在这个范围内,是可以计算出所有的n的平方根的值,除了两个情况,一个是n=0和n=1(这两种情况放在主函数判断)

2.在搜索的时候在数组部会出现两种情况,一种是存在整数解,一种是不存在整数解。

存在整数解直接输出对应编号在打印出数组中对应编号的值即可。

不存在的话就判断小的数的平方比目标值小,大的数比目标数大,取较小的那个数即可。

#include<iostream>
#include<vector>
using namespace std;
vector<int>a;
int mySqrt(int n)
{
    int left = 0;
    int right = a.size()-1;
    while(left<=right)
    {
        int middle = (left + right)/2;
        if(a[middle]*a[middle]>n)
        {
            if(a[middle-1]*a[middle-1]<n)
            {
                return middle-1;
            }
            right = middle - 1;
        }
        else if(a[middle]*a[middle]<n)
        {
            if(a[middle+1]*a[middle+1]>n)
            {
                return middle;
            }
            left = middle + 1;
        }
        else if(a[middle]*a[middle]==n)
        {
            return middle;
        }
    }
    return 0;
}
int main()
{
    int x;
    cin >> x;
    if(x==1||x==0)
    {
        cout << x;
        return 0;
    }
    for(int i=1;i<=x/2;i++)
    {
        a.push_back(i);
    }
    // for(vector<int>::iterator it = a.begin();it!=a.end();it++)
    // {
    //     cout << *it;
    // }
    // cout << endl;
    // cout << x << endl;
    int res = mySqrt(x);
    cout << a[res];
    return 0;
}


目录
相关文章
|
3天前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
8天前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
6 1
|
29天前
【力扣】69. x 的平方根
【力扣】69. x 的平方根
|
8月前
【Leetcode-67. 二进制求和-69.x的平方根】
【Leetcode-67. 二进制求和-69.x的平方根】
24 0
|
29天前
leetcode-69:x 的平方根
leetcode-69:x 的平方根
37 0
|
9月前
|
存储
leetcode:69. x 的平方根
利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。
59 0
YI
|
11月前
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
67 0
|
12月前
|
Java Python
leetcode.69:x的平方根
leetcode.69:x的平方根
58 0
|
前端开发 Go 对象存储
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
|
前端开发 算法 JavaScript
LeetCode 未知数的平方根使用JavaScript解题|前端学算法
LeetCode 未知数的平方根使用JavaScript解题|前端学算法
115 0
LeetCode 未知数的平方根使用JavaScript解题|前端学算法