[leetcode]: 367. Valid Perfect Square

约定不等于承诺〃 2022-06-15 07:40 104阅读 0赞

# 1. 题目 #

Given a positive integer num, write a function which returns True if num is a perfect square else False.  
Note: Do not use any built-in library function such as sqrt.

> Example 1:  
> Input: 16  
> Returns: True
> 
> Example 2:  
> Input: 14  
> Returns: False

给一个正整数，判断它是否恰好为某个数的平方。  
要求不能使用内置的sqrt函数。

# 2.分析 #

我最初的解法： 二分查找，时间复杂度O(logn)

后来看solution还有另外两种解法：  
1) 1+3+5+…+2n-1=(1+2n-1)\*n/2=n^2  
所以平方刚好是上述一个等差数列的和  
2) 牛顿迭代法求平方根 参考**[维基百科][Link 1]**  
推导公式就不详写了，求解平方根的迭代公式为  
![这里写图片描述][SouthEast]

# 3.代码 #

注意使用long long 数据类型，因为乘法可能会超过int32范围  
二分查找

bool isPerfectSquare(int n) {
        if (n < 4)
            return n == 0 || n == 1;
        long long start = 1;
        long long end = n / 2;
        while (start <= end) {
            long long mid = start + (end - start) / 2;
            if (mid*mid == n)
                return true;
            else if (mid*mid > n)
                end = mid - 1;
            else
                start = mid + 1;
        }
        return false;
    }

等差数列的和

class Solution {
    public:
        bool isPerfectSquare(int num) {
            if (num == 0)
                return true;
            for (int i = 1; num > 0; i += 2)
                num -= i;
            return num == 0;
        }
    };

牛顿迭代法求平方根

class Solution {
    public:
        bool isPerfectSquare(int num) {
            if (num < 4)
                return num == 0 || num == 1;
            long long x = num / 2;
            while (x*x > num) {
                x = (x + num / x) / 2;
            }
            return x*x == num;
        }
    };

[Link 1]: https://en.wikipedia.org/wiki/Newton%27s_method
[SouthEast]: /images/20220615/ddbe6ba7a4ba40abaaf4368222c5f98d.png