大前端

前端学习之家-大前端

【每日一题034】leetcode-69

目录

  • 题目
  • 思路
  • 相关思考
  • 代码(C++/原创)
  • 代码(C++/力扣)
  • 代码(C++/改进力扣)

题目

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

思路

1.直接暴力解题,从1开始尝试到x/2
2.按照评论区的二分查找思路进行搜索
3.改进评论区的该查找,在相同的内存消耗下减少运行的时间

相关思考

1.暴力解题过程中发现i*i会溢出,改成了longlong类型后通过了,后来参考评论里面发现可以修改i*i>x条件为i>x/i,可以达到同样的效果并且不会产生溢出
2.在力扣评论区的基础上进行改进,主要思路是在中间加入相等的判断(即该数是一个完全平方数),达到了运行时间0ms,消耗内存不变。

代码(C++/原创)

class Solution {
public:
    int mySqrt(int x) {
        int half=x/2;
        int i=0;
        if(x==0) return 0;
        if(x==1) return 1;
        for(i=1;i<=half;i++)
        {
            if (i>x/i)
            break;
        }
        return i-1;

    }
};

代码(C++/力扣)

int mySqrt(int x) 
    {
        if(x == 1)
            return 1;
        int min = 0;
        int max = x;
        while(max-min>1)
        {
            int m = (max+min)/2;
            if(x/m<m)
                max = m;
            else
                min = m;
        }
        return min;
    }

代码(C++/改进力扣)

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        if(x==1) return 1;
        int min=0,max=x;
        while(max>min+1)
        {
            int m=(min+max)/2;
            if(m==x/m) return m;  //在此处分为三种情况,分别是相等、大于和小于
            else if(m>x/m) max=m;
            else min=m;
        }
        return min;//由上面的判断条件可得此时min和max只差1,而x的精准平方根处于这两数之间,而题意让我们舍去小数部分,所以可以得出min是最终所求的结果

    }
};

发表评论:

Copyright Your WebSite.Some Rights Reserved.