LeetCode 367: isValidSquare 是否是完全平方数（Java）

nanchen2251 发布于2019-08-14 15:53 / 1988人阅读

摘要：题目给一个正整数，判断它是不是完全平方数。给的是型的正整数，所以下界是，上界是最大正整数的平方根。但要注意一定要用乘法来判断相等时的情况。下面是代码数学技巧所有的完全平方数都可以被表示成奇数和。

题目：给一个正整数，判断它是不是完全平方数。

解法：

二分法。给的是int型的正整数，所以下界是1，上界是最大正整数Integer.MAX_VALUE的平方根。但要注意一定要用乘法来判断相等时的情况。下面是代码：

  public static int mySqrt(int x) {
        if(x == 0) return 0;
        int left = 1, right = Integer.MAX_VALUE;
        while(true){
            int mid = left + (right-left)/2;
            if(mid > x/mid)
                right=mid-1;
            else{
                if(mid+1>x/(mid+1))
                    return (int)mid;
                left=mid+1;
            }
        }
    }
    
    public static boolean isPerfectSquare(int num) {
        if(num == 0) return true;
        int left = 1, right = mySqrt(Integer.MAX_VALUE);
        while(right >= left){
            int mid = left + (right-left)/2;
            if(mid*mid == num)
                return true;
            else if(mid*mid > num)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }

2.数学技巧：所有的完全平方数都可以被表示成奇数和1+3+5+7+9 ...。

public boolean isPerfectSquare(int num) {
     int i = 1;
     while (num > 0) {
         num -= i;
         i += 2;
     }
     return num == 0;
 }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66089.html

LeetCode 367. 有效的完全平方数

摘要：给定一个正整数，编写一个函数，如果是一个完全平方数，则返回，否则返回。注意不要使用任何内置的库函数，如。示例输入输出示例输入输出该题实现起来很简单，数学上有个公式所以直接粗暴的解法就是循环减去每个奇数另外还可以用二分的思维给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。注意：不要使用任何内置的库函数，如 sqrt。示...

jubincn 2019-08-23 11:26 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 319 灯泡开关[数学] HERODING的LeetCode之路

摘要：解题思路这题本质就是数学，需要分析，每个灯泡会被翻转的时机正好是他的约数次遍历的时候，那么我们其实知道，对于每个数的约数都是成对出现的，除非是完全平方数，会有奇数个约数，所以，最后完全平方数的灯泡会亮，题目也就变成了找 ...

liujs 2021-11-16 11:45 评论0 收藏0