清风的技术小屋

不为所动, 做更专业的自己

0%

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:

1
2
Input: 16
Output: true

Example 2:

1
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 是否为完全平方数

参考解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}