专栏首页chenjx85的技术专栏leetcode-367-Valid Perfect Square

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 条评论
登录 后参与评论

相关文章

  • leetcode-507-Perfect Number

    chenjx85
  • leetcode-342-Power of Four

    chenjx85
  • leetcode-504-Base 7

    chenjx85
  • leetcode-507-Perfect Number

    chenjx85
  • 算法细节系列(32):有趣的数学

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 敢死队

    这里牵涉一个是否要考虑按照顺序的问题。 如 132 和 123 表示的是一种情况,对于这种情况要进行排除 我的思路是 集中从小到大排序。

    用户4492257
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • JAVA递归

         //斐波那契      // num 第几个数      // search(num - 1)临近的第一个+move(num - 2)临近的...

    用户2192970
  • 挑战数据结构和算法——整数的二进制表示中1的个数

    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题涉及到二进制的处理,在本题使用到&操作和>>操作...

    zhaozhiyong
  • 【leetcode刷题】T203-完美数

    https://leetcode-cn.com/problems/perfect-number/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券