leetcode-367-Valid Perfect Square

题目描述:

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

要完成的函数:

bool isPerfectSquare(int num) 

说明:

1、这道题目不难。给定一个整数,判断是不是平方数。

2、首先处理边界条件,小于等于0的必定不是,1是平方数。

3、从2开始,一直到num/2,判断这些数的平方是不是num,如果平方完结果大于num,那肯定不是。

(num/2)^2的结果必定大于num,当num>4时。(可证)

代码如下:

    bool isPerfectSquare(int num) 
    {
        if(num<=0)
            return false;
        else if(num==1||num==2147395600)//**
            return true;
        else if(num>2147395600&&num<=2147483647)//**
            return false;
        int i=2;
        while(i<=num/2)
        {
            if(i*i==num)
                return true;
            else if(i*i>num)
                return false;
            i++;
        }
        return false;
    }

4、我们都知道int型整数能表示的最大整数是2^31-1,也就是2147483647,而我们能找到的最大平方数是2147395600=46340^2,在大于后者而小于前者中间还存在很多数。倘若我们对于这些数也采取i*i的方法去判断,那会溢出的。

所以笔者采取了上述代码//**那两行的方法去特殊处理,防止溢出导致的错误判断。

5、上述代码也可以改成二分查找,更快一点。

6、除了上述的传统方法外,我们还可以用一些数学上的方法。

我们都知道等差数列,1+3+5+……+2n-1(一共n个数)=n^2。

所以利用这一点我们可以构造出如下代码:

    bool isPerfectSquare(int num) 
    {
        int i = 1;
        while (num > 0) 
        {
            num-=i;
            i+=2;
        }
        if(num==0)
            return true;
        else
            return false;
    }

上述代码实测都是2ms,可能是由于测试集比较简单,beats 100% of cpp submissions。

7、上述代码也可以改成牛顿迭代法,不断逼近。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

4256
来自专栏java一日一条

Java和Android的LRU缓存及实现原理

Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Ja...

991
来自专栏aCloudDeveloper

LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium

题目: Given an array of integers, find two numbers such that they add up to a spec...

20710
来自专栏java一日一条

Java程序员们最常犯的10个错误

Arrays.asList()会返回一个ArrayList对象,ArrayList类是Arrays的一个私有静态类,而不是java.util.ArrayList...

531
来自专栏web编程技术分享

【干货】用大白话聊聊JavaSE — ArrayList 深入剖析和Java基础知识详解(二)1. 新建一个MyList类2. 构造函数设计3. add方法实现4. remove方法实现

2996
来自专栏java学习

ArrayList集合常用的方法详细讲解

在前面我们学习了数组,数组可以保存多个元素,但在某些情况下无法确定到底要保存多少个元素,此时数组将不再适用,因为数组的长度不可变。例如,要保存一个...

1734
来自专栏LanceToBigData

JavaSE(八)之集合概述

前几天其实一直在学习关于linux的内容和kvm虚拟化的知识。今天有时间来回顾一下集合相关的知识,接下来我将带大家一起来回顾一起集合关联的知识。 不要辜负自己花...

1845
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

19910
来自专栏前端儿

表达式求值(1)

Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值...

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

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

1883

扫码关注云+社区