Leetcode355. 有效的完全平方数

题目

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

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

示例 1：

输入：16
输出：True

示例 2：

输入：14
输出：False

解题思路

利用二分查找法寻找答案，其初始下限是1， 上限是INT32_MAX的立方根(hardcode)与num的最小值。为了防止溢出，变量使用long类型。

C++解法

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;
class Solution {
public:
    bool isPerfectSquare(int num) {
        long low = 1;
        long high = min(num, 46341);
        long mid = 0;
        long result = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            result = mid * mid;
            if (result == num) { return true; }
            else if (result < num) { low = mid + 1; }
            else {  high = mid - 1; }
        }
        return false;
    }
};
int main(int argc, const char * argv[]) {
    // insert code here...
    Solution solution;
    for (int i = 1; i < 100; ++i) {
         cout << i << " is " <<  (solution.isPerfectSquare(i) ? "" : "not ")  << "perfect square. " << endl;
    }
    cout << solution.isPerfectSquare(2147483647) << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-perfect-square