This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

367. Valid perfect Squares – Force buckle (LeetCode) (leetcode-cn.com)

Given a positive integer num, write a function that returns true if num is a perfect square and false otherwise.

Advanced: Do not use any built-in library functions such as SQRT.

The sample a

Input: num = 16 Output: trueCopy the code

Example 2

Input: num = 14 Output: falseCopy the code

Tip:

  • 1 <= num <= 2^31 - 1

Thought analysis

violence

If num is a perfect square, there must be an integer XXX that makes x * x=numx * x=num, and we just have to start at 1.

Binary search

We know that 1≤x≤num1≤x≤num1≤x≤num, so we just use 1 and num as the boundary of binary search.

AC code

class Solution {
    fun isPerfectSquare(num: Int): Boolean {
        var left = 0L
        var right = (num / 2).toLong() + 1
        var target = num.toLong()
        while (left <= right) {
            val mind: Long = (left + right) / 2
            val square = mind * mind
            when {
                square == target -> return true
                square < target -> left = mind + 1
                else -> right = mind - 1}}return false}}Copy the code

conclusion

I have seen the official solution and Newton iterative method. To tell the truth, I have seen this solution for several times, but I have not gone to see it. After a good look today, I feel that I am studying mathematics in school again.

367. Valid perfect Squares — Generic formula method — Valid Perfect squares — Force buckle (LeetCode) (leetcode-cn.com)

reference

Valid perfect Squares – Valid Perfect squares – Force buckle (LeetCode) (leetcode-cn.com)

367. Valid Perfect Squares – General term Formula method – Valid Perfect Squares – Force buckle (LeetCode) (leetcode-cn.com)

Two solutions to one problem: “Dichotomy” & “Mathematics” – Valid perfect squares – LeetCode (leetcode-cn.com)