367. 有效的完全平方数 :「二分」&「数学」

简介: 367. 有效的完全平方数 :「二分」&「数学」

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 367. 有效的完全平方数 ,难度为 简单


Tag : 「二分」、「数学」


给定一个 正整数 numnum ,编写一个函数,如果 numnum 是一个完全平方数,则返回 truetrue ,否则返回 falsefalse


进阶:不要使用任何内置的库函数,如  sqrt


示例 1:


输入:num = 16
输出:true
复制代码


示例 2:


输入:num = 14
输出:false
复制代码


提示:


  • 1 <= num <= 2^{31} - 11<=num<=2311


二分



假如答案为 ansans,那么以 ansans 为分割点的数轴上具有二段性:


  • 小于 ansans 的一段 xx 必然不满足 x * x \geq numxxnum
  • 大于等于 ansans 的一段 xx 必然满足 x * x \geq numxxnum


因此可以通过「二分」来找到分割点 ansans


代码:


class Solution {
    public boolean isPerfectSquare(int num) {
        long l = 0, r = num;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (mid * mid <= num) l = mid;
            else r = mid - 1;
        }
        return r * r == num;
    }
}
复制代码


  • 时间复杂度:O(\log{n})O(logn)
  • 空间复杂度:O(1)O(1)


数学



我们知道对于一个完全平方数而言,可以写成如下形式:


num = n^2 = 1 + 3 + 5 + ... + (2 * n - 1)num=n2=1+3+5+...+(2n1)


因此另外一种做法是对 numnum 进行不断的奇数试减,如果最终能够减到 00,说明 numnum 可展开成如 1+3+5+...+(2*n-1)1+3+5+...+(2n1) 的形式,numnum 为完全平方数。


代码:


class Solution {
    public boolean isPerfectSquare(int num) {
        int x = 1;
        while (num > 0) {
            num -= x;
            x += 2;
        }
        return num == 0;
    }
}
复制代码


  • 时间复杂度:O(\sqrt{n})O(n)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.367 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
6月前
|
人工智能 算法 BI
数学知识:质数与约数
数学知识:质数与约数
70 0
|
6月前
|
算法
简记二分算法模板与代码案例:整数二分和浮点数二分
本文介绍了两种算法模板,分别是整数二分和浮点数二分。
50 0
|
6月前
|
算法 测试技术 C#
【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和
【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和
|
6月前
|
算法 测试技术 C#
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
6月前
|
测试技术
【数学】【记忆化搜索 】【动态规划】964. 表示数字的最少运算符
【数学】【记忆化搜索 】【动态规划】964. 表示数字的最少运算符
|
算法 C语言 C++
【数论】最大公约数、约数的个数与约数之和定理
先来科普下什么是约数:当a能被b整除,我们就说b为a的约数,b的倍数为a
120 0
数学问题之(矩阵加速递推快速幂)
数学问题之(矩阵加速递推快速幂)
|
机器学习/深度学习 人工智能
数学问题之(矩阵快速幂)
数学问题之(矩阵快速幂)
容斥原理 (两个例题)
容斥原理 (两个例题)
145 0