24.总结

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 题解

二分查找

// 方法一：二分查找
// 注意，边界可以从一半开始找，乘出来的结果要用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;
}

---

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