leetcode-69-Sqrt(x)

题目描述:

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;  
}   

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

作为Scala语法糖的设计模式

Scala算是一门博采众家之长的语言,兼具OO与FP的特性,若使用恰当,可以更好地将OO与FP的各自优势发挥到极致;然而问题也随之而来,倘若过分地夸大OO特性,...

36350
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列1

Java面试系列1 1 静态变量和实例变量的区别? 静态变量也称作类变量,由static修饰,如:static int s; s就是静态变量,它只能通过类来访...

28350
来自专栏AzMark

Python列表与元组

16130
来自专栏Java呓语

工厂方法模式(延迟到子类来选择实现)

1、工厂方法模式理念介绍 2、它与简单方法模式的区别 3、推荐使用工厂方法的场景 4、在Android 源码中的应用

8540
来自专栏程序员宝库

关于 Java 你不知道的 10 件事

作为 Java 书呆子,比起实用技能,我们会对介绍 Java 和 JVM 的概念细节更感兴趣。因此我想推荐 Lukas Eder 在 jooq.org 发表的原...

31050
来自专栏代码世界

Python之面向对象二

面向对象的三大特性: 继承 继承是一种创建新类的方式,在python中,新建的类可以继承一个或多个父类,父类又可称为基类或超类,新建的类称为派生类或子类 pyt...

41270
来自专栏向治洪

Scala入门

Scala入门 Scala简介 ps:在最新的薪资调查中,Scala程序员的工资是平均最高的Scala工资。 Scala是一门多范式的编程语言,一种类似java...

20370
来自专栏Phoenix的Android之旅

重构 - 完全不用 if-else 可能吗?

上次那篇重构-为什么 if-else 不是好代码 说到代码中的 if-else会随着代码量的增加,在迭代的过程中变的越来越难以维护, 然后用工厂模式的思路可以把...

9420
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(1)第7章 面向对象编程(OOP)《Kotlin极简教程》正式上架:

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统、集合类以及泛型相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函...

10120
来自专栏带你撸出一手好代码

编程语言函数多返回值处理方式排名

一个函数一个返回值 , 这好像跟祖宗定下的规则似的,各个时代主流编程语言几乎都严格遵守着。然而, 在实际情况下, 程序员写代码经常会碰到一个函数会返回多个返回值...

41370

扫码关注云+社区

领取腾讯云代金券