367.有效的完全平方数

LeetCode LeetCode 二分查找

发布时间 : 2000-01-10 03:06

字数:1.5k 阅读 :

评论:

367.有效的完全平方数

367.有效的完全平方数

367.1 题目

给你一个正整数 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

367.2 题解

方法一：二分查找

思路

在 [2, num/2] 范围内二分查找，计算中间值的平方与 num 比较。注意使用 long 类型避免溢出。

核心思想：二分查找平方根，避免溢出。

具体步骤：

如果 num < 2，直接返回 true。
在 [2, num/2] 范围内二分查找：
- 计算 mid * mid
- 如果等于 num，返回 true
- 如果小于 num，left = mid + 1
- 如果大于 num，right = mid - 1
未找到则返回 false。

举例：对于 num = 16：

left=2, right=8，mid=5，square=25 > 16，right=4
left=2, right=4，mid=3，square=9 < 16，left=4
left=4, right=4，mid=4，square=16 == 16，返回 true

复杂度分析

时间复杂度：O(log n)，二分查找。
空间复杂度：O(1)，只使用常数变量。

代码

// 方法一：二分查找
// 注意，边界可以从一半开始找，乘出来的结果要用long来装
static bool IsPerfectSquare1(int num)
{
    // 如果 num 小于 2，则它一定是完全平方数，返回 true
    if (num < 2) return true;

    // 定义左边界和右边界
    long left = 2;
    long right = num / 2;

    // 二分查找
    while (left <= right)
    {
        // 计算中间值
        long mid = left + (right - left) / 2;
        // 计算中间值的平方
        long square = mid * mid;

        // 若平方值等于 num，则 num 是完全平方数，返回 true
        if (square == num)
            return true;
        // 若平方值小于 num，则调整左边界
        else if (square < num)
            left = mid + 1;
        // 若平方值大于 num，则调整右边界
        else
            right = mid - 1;
    }

    // 若循环结束仍未找到完全平方数，则返回 false
    return false;
}

方法二：完全平方数数学性质

思路

利用数学性质：完全平方数等于从 1 开始的连续奇数之和。例如 1=1, 4=1+3, 9=1+3+5。依次减去奇数，如果最终为 0 则是完全平方数。

核心思想：n² = 1 + 3 + 5 + ... + (2n-1)

具体步骤：

初始化 i = 1。
当 num > 0 时：
- num -= i
- i += 2
如果最终 num == 0，返回 true；否则返回 false。

举例：对于 num = 16：

num = 16 - 1 = 15，i = 3
num = 15 - 3 = 12，i = 5
num = 12 - 5 = 7，i = 7
num = 7 - 7 = 0，i = 9
num == 0，返回 true

复杂度分析

时间复杂度：O(√n)，最多减去 √n 个奇数。
空间复杂度：O(1)，只使用常数变量。

代码

// 方法二：完全平方数数学性质
// 完全平方数的性质：一个完全平方数等于一系列奇数相加
// 例如：1 = 1, 4 = 1 + 3, 9 = 1 + 3 + 5, 16 = 1 + 3 + 5 + 7, ...
static bool IsPerfectSquare2(int num)
{
    // 初始化奇数
    int odd = 1;
    // 循环迭代，减去连续的奇数，直到 num 为 0
    while (num > 0)
    {
        num -= odd; // 依次减去奇数
        odd += 2; // 获取下一个奇数
    }

    // 若最终 num 为 0，则 num 是完全平方数，返回 true；否则返回 false
    return num == 0;
}

367.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个正整数 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

        #endregion

        #region 测试

        // 示例 1
        int num1 = 16;
        bool result1_1 = IsPerfectSquare1(num1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = IsPerfectSquare2(num1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int num2 = 14;
        bool result2_1 = IsPerfectSquare1(num2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = IsPerfectSquare2(num2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：二分查找
    // 注意，边界可以从一半开始找，乘出来的结果要用long来装
    static bool IsPerfectSquare1(int num)
    {
        // 如果 num 小于 2，则它一定是完全平方数，返回 true
        if (num < 2) return true;

        // 定义左边界和右边界
        long left = 2;
        long right = num / 2;

        // 二分查找
        while (left <= right)
        {
            // 计算中间值
            long mid = left + (right - left) / 2;
            // 计算中间值的平方
            long square = mid * mid;

            // 若平方值等于 num，则 num 是完全平方数，返回 true
            if (square == num)
                return true;
            // 若平方值小于 num，则调整左边界
            else if (square < num)
                left = mid + 1;
            // 若平方值大于 num，则调整右边界
            else
                right = mid - 1;
        }

        // 若循环结束仍未找到完全平方数，则返回 false
        return false;
    }

    // 方法二：完全平方数数学性质
    // 完全平方数的性质：一个完全平方数等于一系列奇数相加
    // 例如：1 = 1, 4 = 1 + 3, 9 = 1 + 3 + 5, 16 = 1 + 3 + 5 + 7, ...
    static bool IsPerfectSquare2(int num)
    {
        // 初始化奇数
        int odd = 1;
        // 循环迭代，减去连续的奇数，直到 num 为 0
        while (num > 0)
        {
            num -= odd; // 依次减去奇数
            odd += 2; // 获取下一个奇数
        }

        // 若最终 num 为 0，则 num 是完全平方数，返回 true；否则返回 false
        return num == 0;
    }

    #endregion
}

367.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com