有效的完全平方数
难度:
标签:
题目描述
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：
输入：num = 14 输出：false 解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
提示：
1 <= num <= 231 - 1
代码结果
运行时间: 17 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Java Stream的范围和函数式编程特性来实现。
* 我们可以在IntStream.rangeClosed(1, num/2+1)的范围内进行遍历，
* 然后通过mapToLong(i -> (long)i * i)计算平方，
* 如果找到等于num的情况，则返回true。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public boolean isPerfectSquare(int num) {
return IntStream.rangeClosed(1, num / 2 + 1)
.mapToLong(i -> (long) i * i)
.anyMatch(square -> square == num);
}
}解释
方法:
这个题解使用二分查找的方法来判断一个数是否为完全平方数。具体思路如下：
1. 如果给定的数num等于1，直接返回True，因为1是完全平方数。
2. 初始化左边界l为1，右边界r为num-1。
3. 当l<=r时，进行以下循环：
a. 计算中间值mid为(l+r)//2。
b. 如果num除以mid的结果等于mid，说明找到了完全平方数，返回True。
c. 如果num除以mid的结果小于mid，说明mid太大，将右边界r更新为mid-1。
d. 否则，num除以mid的结果大于mid，说明mid太小，将左边界l更新为mid+1。
4. 如果循环结束没有找到完全平方数，返回False。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
您在题解中的二分查找算法中提到如果`num / (mid * 1.0) == mid`则返回True，但考虑到浮点数的精度问题，这种比较是否总是准确的？
▷🦆
在二分查找的过程中，您提到如果`num / mid < mid`则右移右边界到`mid - 1`，请问这样的更新逻辑是否有可能跳过真正的完全平方数？
▷🦆
您的算法中为什么选择将右边界`r`初始化为`num - 1`而不是`num`，这样的初始化对查找的效率和结果有什么影响？
▷🦆
给定的提示中`num`的最大值是`2^31 - 1`，在这种情况下，mid的计算可能会导致整型溢出。您的代码中如何处理这种可能的溢出问题？
▷