leetcode-367-Valid Perfect Square

chenjx85

发布于 2018-05-21 18:42:38

5910

发布于 2018-05-21 18:42:38

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

题目描述：

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、上述代码也可以改成牛顿迭代法，不断逼近。

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

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

function