LeetCode 367. 有效的完全平方数

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
2. 解法二：牛顿迭代
相似题目

题目描述

✅ 367. 有效的完全平方数

思路分析

解法一：二分查找（推荐）

核心思路：

在区间 [1, num] 上二分查找平方根。

使用 long 计算中间值平方，避免溢出。

若存在 mid * mid == num 则为完全平方数。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示 num 的数值大小。

空间复杂度：O(1)。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) {
            return false;
        }

        long left = 1;
        long right = num;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long sq = mid * mid;

            if (sq == num) {
                return true;
            }
            if (sq < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

func isPerfectSquare(num int) bool {
	if num < 1 {
		return false
	}

	left := int64(1)
	right := int64(num)

	for left <= right {
		mid := left + (right-left)/2
		sq := mid * mid

		if sq == int64(num) {
			return true
		}
		if sq < int64(num) {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return false
}

解法二：牛顿迭代

核心思路：

使用牛顿法逼近平方根：x_{k+1} = (x_k + n / x_k) / 2。

迭代到 x * x <= n 后判断是否相等。

复杂度分析：

时间复杂度：O(log n)，收敛速度快。

空间复杂度：O(1)。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) {
            return false;
        }

        long x = num;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }

        return x * x == num;
    }
}

func isPerfectSquare(num int) bool {
	if num < 1 {
		return false
	}

	x := int64(num)
	for x*x > int64(num) {
		x = (x + int64(num)/x) / 2
	}

	return x*x == int64(num)
}

相似题目

题目	难度	考察点
69. x 的平方根	简单	二分查找
633. 平方数之和	中等	双指针
279. 完全平方数	中等	动态规划
441. 排列硬币	简单	二分查找
50. Pow(x, n)	中等	快速幂

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/88914829