Valid Perfect Square
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
1 <= num <= 231 - 1
思路一：从 1 开始求平方，暴力计算
public boolean isPerfectSquare(int num) {
for (long i = 1; i <= num; i++) {
long val = i * i;
if (val < num) {
continue;
} else if (val == num) {
return true;
} else {
return false;
}
}
return false;
}
思路二：用二分法，比思路一减少计算次数，注意用 long 存储数值，防止溢出
public boolean isPerfectSquare2(int num) {
long left = 1;
long right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long val = mid * mid;
if (val == num) {
return true;
} else if (val < num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}