leetcode 367. Valid Perfect Square 平方数的判断

骑猪看日落 2022-06-07 02:45 170阅读 0赞

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

直接遍历肯定超时，但是想不到更好地办法，网上看到一个很简单的做法，真实大受启发。

需要注意的地方是循环条件要写成*\* i <= num / i \**，不要写成 i \* i <= num，否者会出现问题

代码如下：

/*
     * 直接遍历肯定超时
     * */
    class Solution
    {
        public boolean isPerfectSquare(int num) 
        {
            if(num<=1)
                return true;
    
            for(int i=2;i<=num/i;i++)
            {
                int one=i*i;
                if(one==num)
                    return true;            
            }
            return false;
        }
    }

下面是C++的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        bool isPerfectSquare(int num)
        {
            if (num <= 1)
                return true;
            for (int i = 2; i <= num/i; i++)
            {
                int one = i*i;
                if (one == num)
                    return true;
            }
    
            return false;
        }
    };