367. 有效的完全平方数

第二次刷题笔记

问题描述

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16
输出：True

示例 2：

输入：14
输出：False

解题思路

本题是在解决完我第一次刷题笔记中那道题之后推荐的题目，我看这两题似乎很有共通之处，一开始想在第一次的基础上改一改然后提交，后来发觉，有一条捷径，那就是在实现Sqrt()$Sqrt()$函数之后，在后面加上一个判断，如果求出的值half$half$的平方等于输入的num$num$那不就解决这个问题了么。。。。
最后提交结果后，由于本题提交的人很少，居然还打败了100%d的人。

遇见的问题

没有，不过，我有考虑过效率上的问题，本题和前一题，都是按照折半的思路来解决的，时间复杂度大概是log2x$lo{g}_{2}x$,可能会有更有效率的解决方式吧。

答案

public boolean isPerfectSquare(int num) {
         if(num == 1)
            return true;

        long half = num/2;
        long pre_half = num/2;
        while(true){
            if(half*half > num){
                pre_half = half;
                half /= 2;
            }
            else{
                if((half+1)*(half+1) > num)
                    break;
                else{
                    half = (half + pre_half) / 2;
                }
            }
        }

        if(half * half == num )
            return true;
        else
            return false;
    }