LeetCode 0367 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
Output: true

Example 2:

Input: 14
Output: false

题意

• 判断指定的数是否是平方数

思路1

• 无需全部判断，可以直接退出
• 中间计算 i * i 可能溢出，使用 long long 强转

代码1

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

思路2

• 二分查找标准写法
• 注意别越界

class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while(l < r)
        {
            int mid = (r - l) / 2 + l;
            if((long long)mid * mid >= num)  // 防止溢出
                r = mid;
            else
                l = mid + 1;
        }
        if((long long)l * l == num)
            return true;
        else
            return false;
    }
};