当前位置：首页 > news >正文

LeetCode题练习与总结：有效的完全平方数--367

news 2024/11/2 11:04:57

一、题目描述

给你一个正整数 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 <= 2^31 - 1

二、解题思路

由于不能使用内置的 sqrt 函数，我们需要寻找一种不使用开方的方法来判断一个数是否是完全平方数。
一个简单的方法是使用二分查找。我们知道，如果一个数 num 是完全平方数，那么它的平方根一定在 1 到 num/2 + 1 的范围内。
我们可以在这个范围内进行二分查找，每次计算中间值的平方，如果平方结果等于 num，则说明 num 是完全平方数；如果平方结果大于 num，则说明平方根在左侧区间；如果平方结果小于 num，则说明平方根在右侧区间。
当查找区间为空时，如果仍未找到平方根，则说明 num 不是完全平方数。

三、具体代码

class Solution {public boolean isPerfectSquare(int num) {// 边界情况if (num < 2) {return true;}long left = 2, right = num / 2, mid, square;while (left <= right) {mid = left + (right - left) / 2;square = mid * mid;if (square == num) {return true;} else if (square > num) {right = mid - 1;} else {left = mid + 1;}}return false;}
}

在这段代码中，我们使用了 long 类型来避免在计算 mid * mid 时可能发生的整数溢出。同时，我们通过 left + (right - left) / 2 来计算中间值，以避免直接使用 (left + right) / 2 可能导致的整数溢出。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始时，我们设置 left 为 2，right 为 num / 2。
在二分查找的过程中，每次循环都会将查找区间缩小一半。
假设需要经过 k 次循环才能结束二分查找，那么有 2^k = right - left + 1。
因为 right 的初始值为 num / 2，所以 k 最多为 log(num)（这里 log 表示以 2 为底的对数）。
因此，时间复杂度为 O(log(num))。

2. 空间复杂度

在整个算法中，我们只使用了常数个额外空间，即 left、right、mid 和 square 这几个变量。
这些变量所占用的空间不会随着输入 num 的大小而改变。
因此，空间复杂度为 O(1)。

综上所述，该算法的时间复杂度为 O(log(num))，空间复杂度为 O(1)。

五、总结知识点

类定义：
- 使用 class 关键字定义一个名为 Solution 的类。
方法定义：
- 在类中定义一个名为 isPerfectSquare 的公共方法，它接受一个整数参数 num 并返回一个布尔值。
基本数据类型：
- 使用 int 类型来定义方法的参数和返回类型。
- 使用 long 类型来避免在计算过程中可能出现的整数溢出。
边界条件处理：
- 在方法开始时，检查 num 是否小于 2，因为 0 和 1 都是完全平方数。
二分查找算法：
- 使用二分查找算法来寻找可能的平方根，这是一种有效的查找算法，适用于有序数据集。
循环结构：
- 使用 while 循环来实现二分查找，条件是 left 小于等于 right。
数学运算：
- 使用乘法运算 * 来计算 mid 的平方。
- 使用除法运算 / 来初始化 right 变量。
- 使用加法和减法运算来更新 left 和 right 的值。
条件判断：
- 使用 if-else 语句来判断 square 是否等于 num，以及如何调整 left 和 right 的值。
类型转换：
- 将 num 除以 2 的结果转换为 long 类型，以避免在计算 right 时发生整数溢出。