• Table of Contents

367. 有效的完全平方数

力扣原题链接（点我直达）

第一种，int型溢出

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16 输出：True 示例 2：

输入：14 输出：False

Line 8: Char 11: runtime error: signed integer overflow: 1073741824 * 1073741824 cannot be represented in type ‘int’ (solution.cpp

bool isPerfectSquare(int num) {
    int mid=1,low = 1,high=num;
    while (low<=high)
    {
        mid = low + (high - low) / 2;
        if (mid * mid == num)//这里会溢出，当int为INT_MAX时，mid*mid肯定超过INT_MAX了
        {
            return true;
        }
        else if (mid*mid >num)
        {
            high = mid-1;
        }
        else 
        {
            low = mid+1;
        }

    }
    return false;
}

第二种，从46340-1直接搜索

INT_MAX 足最大为 2^32 -1 大约为 2147483647，他的平方差是 46340，直接搜索 从 1-46340搜索就行

46340*46340 = 2,147,395,600

46341*46341 = 2,147,488,281

    bool isPerfectSquare(int num) {
    int mid=1,low = 1,high=46340;
    while (low<=high)
    {
        mid = low + (high - low) / 2;
        if (mid * mid == num)
        {
            return true;
        }
        else if (mid*mid >num)
        {
            high = mid-1;
        }
        else 
        {
            low = mid+1;
        }

    }
    return false;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了72.54%的用户

内存消耗 :8.1 MB, 在所有 C++ 提交中击败了26.74%的用户

第三种 ，一个完全平方数必是连续奇数的和

1+3+5+7+9+…+(2n-1)=n^2

    bool isPerfectSquare(int num) {
    int i = 1;
    while (num > 0)
    {
        num -= i;
        i += 2;
    }
    return num == 0;
    }

执行用时 :4 ms, 在所有 C++ 提交中击败了72.54%的用户

内存消耗 :7.9 MB, 在所有 C++ 提交中击败了67.91%的用户