Java教程

Leetcode--Java--367. 有效的完全平方数

本文主要是介绍Leetcode--Java--367. 有效的完全平方数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
进阶:不要 使用任何内置的库函数,如 sqrt 。

样例描述

示例 1:

输入:num = 16
输出:true
示例 2:

输入:num = 14
输出:false

思路

二分法

  1. 在1~num之间二分,看是否能找到根号下num。
    在这里插入图片描述
  2. 细节:不用根号函数,可以用两数相乘来表示,然后又为了防止溢出,将相乘形式改写成除法形式。最后判断取根号后的数相乘是否等于num即可。
  3. l = mid记得让求mid加一,同时为了防止溢出,要转化为long。

代码

class Solution {
    public boolean isPerfectSquare(int num) {
        long l = 1, r = num;
        while (l < r) {
            long mid = l + r  + 1 >> 1;
            //除法形式,防止溢出
            if (mid <= num / mid) {
               l = mid;
            } else {
                r = mid - 1;
            }
        }
        //根号值做乘法
        return r * r == num; 
    }
}
这篇关于Leetcode--Java--367. 有效的完全平方数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!