- 367.有效的完全平方数
- 题目描述
- 思路:库函数、暴力遍历、二分查找
- 库函数
- Python实现
- Java实现
- 暴力遍历
- Python实现
- Java实现
- 二分查找
- Python实现
- Java实现
367.有效的完全平方数 题目描述
有效的完全平方数
思路:库函数、暴力遍历、二分查找 库函数
最朴素的解法是用库函数。
Python实现class Solution: def isPerfectSquare(self, num: int) -> bool: # 库函数 return float.is_integer(pow(num, 0.5))Java实现
class Solution { public boolean isPerfectSquare(int num) { // 库函数 int x = (int) Math.sqrt(num); return x * x == num; } }暴力遍历
假定num为有效的完全平方数,则一定存在正整数x使得xx=num。于是可以从1开始遍历正整数,寻找是否存在满足xx=num的正整数x。在遍历过程中,如果存在正整数x使得xx>num,则不可能再出现正整数x使得xx=num成立,不再继续遍历。
Python实现class Solution: def isPerfectSquare(self, num: int) -> bool: # 暴力遍历 x, square = 1, 1 while square <= num: if square == num: return True x += 1 square = x * x return FalseJava实现
class Solution { public boolean isPerfectSquare(int num) { // 暴力遍历 long x = 1, square = 1; while (square <= num) { if (square == num) { return true; } ++x; square = x * x; } return false; } }二分查找
可以使用二分查找对暴力遍历进行优化,由于num是正整数,所以如果正整数x满足x*x=num,则x一定满足1 <= x <= num。所以可以使用1和num作为两个边界。
Python实现class Solution: def isPerfectSquare(self, num: int) -> bool: # 二分查找 left, right = 0, num while left <= right: mid = (left + right) // 2 square = mid * mid if square < num: left = mid + 1 elif square > num: right = mid - 1 else: return True return FalseJava实现
class Solution { public boolean isPerfectSquare(int num) { // 二分查找 int left = 0, right = num; while (left <= right) { int mid = (right - left) / 2 + left; long square = (long) mid * mid; if (square < num) { left = mid + 1; } else if (square > num) { right = mid - 1; } else { return true; } } return false; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)