leetcode Valid Perfect Square

leetcode Valid Perfect Square

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

题目地址：leetcode Valid Perfect Square

题意：给定一个数n，要求不使用sqrt函数判断该数是否为完全平方数

思路：二分。。  L = 1 ,  R = num / 2 +1开始枚举即可。。。

C++

class Solution {
public:
	bool isPerfectSquare(int num) {
		long long L = 1, R = (num >> 1) + 1;
		while (L <= R) {
			long long m = L + ((R - L) >> 1);
			long long mul = m * m;
			if (mul == num) return true;
			else if (mul > num) R = m - 1;
			else L = m + 1;
		}
		return false;
	}
};

Java

public class Solution {
    public boolean isPerfectSquare(int num) {
        long L = 1, R = (num >> 1) + 1;
		while (L <= R) {
			long  m = L + ((R - L) >> 1);
			long  mul = m * m;
			if (mul == num) return true;
			else if (mul > num) R = m - 1;
			else L = m + 1;
		}
		return false;
    }
}

Python

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        L, R = 1, (num >> 1) + 1
        while L <= R:
            m = L + ((R - L) >> 1)
            mul = m ** 2
            if mul == num:
                return True
            elif mul > num:
                R = m - 1
            else:
                L = m + 1
        return False

 

本题是leetcode 367  Valid Perfect Square题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/