leetcode-69-Sqrt(x)

chenjx85

发布于 2018-05-21 18:34:09

7970

发布于 2018-05-21 18:34:09

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated

要实现的函数：

int mySqrt(int x)

代码：

#include<climits>
int mySqrt(int x) 
{
    if(x>=2147395600&&x<=INT_MAX)//**
    return 46340;//**
    for(int i=0;i<=x;i++)
    {    
        if((i*i<=x)&&((i+1)*(i+1)>x))
        return i;
    }
}

说明：

1、本题目采用上述代码很容易实现，但是有一个问题就是时间花费巨大，采用二分查找会好很多……

2、本题目若是要求输出sqrt(x)的完整结果，而不仅仅是整数部分，那么应该采取牛顿迭代法或者泰勒公式展开的方法。最开始就考虑了泰勒展开的方法，后来重新看了下题目，发现打扰了走错路了……

3、c++对于立即数的存储和处理采用的是int类型。

cout<<46341*46341<<endl;的时候，会提示“interger overflow”，因为INT_MAX比46341*46341小。

同理，如果if(46341*46341>INT_MAX)cout<<“good“<<endl;代码运行不会输出good的，因为这时候已经溢出了，结果不会大于INT_MAX的。

之所以要提这一点，是因为最开始的代码中，没有//**标记的那两行。

各位同学想想若是直接去掉了这两行，当x=INT_MAX的时候，mySqrt(x)执行结果会是什么？

后续：

参考CSDN博主小村长的二分查找代码，如下，beats 23.97% of cpp submissions

int mySqrt(int x) 
{       
    if(x>=2147395600&&x<=INT_MAX)//**
    return 46340; //**
    double begin = 0;  
    double end = x;  
    double result = 1;  
    double mid = 1;  
    while(abs(result-x) > 0.000001)
    {
        mid = (begin+end)/2;  
        result = mid*mid;  
        if(result > x)   // 二分的范围  
        end = mid;  
        else
        begin = mid;  
    }  
    return (int)mid;  
}

上述代码//**那两行同样道理。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-04-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

c++