LeetCode 367 - 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

Related Topics: Math, Binary Search

原问题: 367. Valid Perfect Square

中文翻译版: 367. 有效的完全平方数

解决方案

本题换种说法就是：求正整数 num 的平方根 x，且 x 的平方等于 num，如何求正整数的平方根，可以用二分查找进行求解，这个可以参考LeetCode原题 69. Sqrt(x)（解题报告：LeetCode 69 - Sqrt(x)），二分查找后得到的平方根 x，只需判断 x 的平方是否等于 num 即可判断 num 是否为完全平方数

参考解题代码

#include <iostream>
using namespace std;


class Solution {
public:
    bool isPerfectSquare(int num) {
        long long low, mid, high;

        low = 0;
        high = (long)num + 1;
        while (low < high) {
            mid = low + (high - low) / 2;
            if (mid * mid < num)
                low = mid + 1;
            else
                high = mid;
        }

        // if it doesn't find square of number
        if (low * low != num)
            return false;

        return true;
    }
};


int main()
{
    int num;
    Solution solu;

    // max of int
    // num = 2147483647;
    num = 14;
    cout << num << " is perfect square: "
         << solu.isPerfectSquare(num) << endl;
    return 0;
}