367.Valid Perfect Square

367.Valid Perfect Square

难度:Easy

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
Output: true
Example 2:
Input: 14
Output: false

不能用sqrt函数,那么就只能直接循环,好在也不需要求出平方根也可以知道大致在什么位置跳出循环。

class Solution {
public:
bool isPerfectSquare(int num) {
for(int i=1;i<=num;i++)
{
long tmp=i*(long)i;
if(tmp>num) return false;
else if (tmp == num ) return true;
}
return false;
}
};

这里将i转成long防止整型溢出。当tmp大于num时,即i已经超过了平方根,直接返回false即可。

执行用时 :4 ms, 在所有 C++ 提交中击败了81.42%的用户 内存消耗 :8 MB, 在所有 C++ 提交中击败了61.50%的用户