LeetCode - Easy - 367. Valid Perfect Square

Topic

• Binary Search
• Math

Description

https://leetcode.com/problems/valid-perfect-square/

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as

sqrt

.

Example 1:

Input: num = 16
Output: true
           

Example 2:

Input: num = 14
Output: false
           

Constraints:

• 1 <= num <= 2³¹ - 1

Analysis

方法一：将符合要求的數緩存好，再二分查找。

方法二：巧用奇數數列求和公式。

1 = 1 1 = 1 1=1

4 = 1 + 3 4 = 1 + 3 4=1+3

9 = 1 + 3 + 5 9 = 1 + 3 + 5 9=1+3+5

16 = 1 + 3 + 5 + 7 16 = 1 + 3 + 5 + 7 16=1+3+5+7

25 = 1 + 3 + 5 + 7 + 9 25 = 1 + 3 + 5 + 7 + 9 25=1+3+5+7+9

36 = 1 + 3 + 5 + 7 + 9 + 11 36 = 1 + 3 + 5 + 7 + 9 + 11 36=1+3+5+7+9+11

. . . . . . ...

1 + 3 + . . . + ( 2 n − 1 ) = ( 2 n − 1 + 1 ) ⋅ n 2 = n 2 1+3+. . .+(2n-1)=\frac{(2n-1 + 1)\cdot n}{2}=n^2 1+3+...+(2n−1)=2(2n−1+1)⋅n​=n2

方法三：二分查找法

方法四：牛頓疊代法

Submission

package com.lun.easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ValidPerfectSquare {

	private static List<Integer> squareList;

	static {
		squareList = new ArrayList<>();

		int i = 1, product;
		while (true) {
			if ((product = i * i) < 0)
				break;

			squareList.add(product);
			i++;
		}
	}

	// 方法一：将符合要求的數緩存好，再二分查找
	public boolean isPerfectSquare(int num) {
		return Collections.binarySearch(squareList, num) >= 0;
	}

	// 方法二：奇數數列求和
	public boolean isPerfectSquare2(int num) {
		int i = 1;
		while (num > 0) {
			num -= i;
			i += 2;
		}
		return num == 0;
	}

	// 方法三：二分查找法
	public boolean isPerfectSquare3(int num) {
		int low = 1, high = num;
		while (low <= high) {
			long mid = (low + high) >>> 1;
			if (mid * mid == num) {
				return true;
			} else if (mid * mid < num) {
				low = (int) mid + 1;
			} else {
				high = (int) mid - 1;
			}
		}
		return false;
	}

	// 方法四：牛頓疊代法
	public boolean isPerfectSquare4(int num) {
		long x = num;
		while (x * x > num) {
			x = (x + num / x) >> 1;
		}
		return x * x == num;
	}

}

           

Test

import static org.junit.Assert.*;
import org.junit.Test;

public class ValidPerfectSquareTest {

	@Test
	public void test() {
		ValidPerfectSquare obj = new ValidPerfectSquare();

		assertTrue(obj.isPerfectSquare(1));
		assertTrue(obj.isPerfectSquare(4));
		assertTrue(obj.isPerfectSquare(9));
		assertTrue(obj.isPerfectSquare(16));
		assertTrue(obj.isPerfectSquare(25));
		assertTrue(obj.isPerfectSquare(36));
		assertTrue(obj.isPerfectSquare(49));
		assertFalse(obj.isPerfectSquare(50));
	}

	@Test
	public void test2() {
		ValidPerfectSquare obj = new ValidPerfectSquare();

		assertTrue(obj.isPerfectSquare2(1));
		assertTrue(obj.isPerfectSquare2(4));
		assertTrue(obj.isPerfectSquare2(9));
		assertTrue(obj.isPerfectSquare2(16));
		assertTrue(obj.isPerfectSquare2(25));
		assertTrue(obj.isPerfectSquare2(36));
		assertTrue(obj.isPerfectSquare2(49));
		assertFalse(obj.isPerfectSquare2(50));
	}

	@Test
	public void test3() {
		ValidPerfectSquare obj = new ValidPerfectSquare();

		assertTrue(obj.isPerfectSquare3(1));
		assertTrue(obj.isPerfectSquare3(4));
		assertTrue(obj.isPerfectSquare3(9));
		assertTrue(obj.isPerfectSquare3(16));
		assertTrue(obj.isPerfectSquare3(25));
		assertTrue(obj.isPerfectSquare3(36));
		assertTrue(obj.isPerfectSquare3(49));
		assertFalse(obj.isPerfectSquare3(50));
		assertFalse(obj.isPerfectSquare3(Integer.MAX_VALUE));
	}

	@Test
	public void test4() {
		ValidPerfectSquare obj = new ValidPerfectSquare();

		assertTrue(obj.isPerfectSquare4(1));
		assertTrue(obj.isPerfectSquare4(4));
		assertTrue(obj.isPerfectSquare4(9));
		assertTrue(obj.isPerfectSquare4(16));
		assertTrue(obj.isPerfectSquare4(25));
		assertTrue(obj.isPerfectSquare4(36));
		assertTrue(obj.isPerfectSquare4(49));
		assertFalse(obj.isPerfectSquare4(50));
	}

}