preface

Is everyone asleep? Haven’t slept words to a simple topic before sleep to help sleep 🐶🐶

Topic describes

367. Valid perfect squares

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

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

Example 1:

Input: 16 Output: TrueCopy the code

Example 2:

Input: 14 Output: FalseCopy the code

Their thinking

They ask you to determine that a given positive integer num is a perfect square.

First, let’s review the definition of a perfect square:

Perfect square means multiplying yourself by an integer such as 11,22,3, *3, and so on. A number is called a perfect square if it can be expressed as the square of an integer. A perfect square is non-negative, and a perfect square has two terms. Be careful not to be confused with perfectly flat mode. Perfect squares.

Then we can think roughly of centralized solutions to this problem:

Violent solution

We use the for loop directly to determine if the condition is satisfied in the range of half num, and return true if it is, and false if it is not.

dichotomy

Mid =parseInt((left+right)/2); mid=parseInt((left+right)/2); Mid –, mid++, temp == num, and so on.

The mathematical method

Any square number can represent the following odd sequence sum:

1 + 3 + 5 + 7 +… + (2 N – 1) = N ^ 2

According to the laws of mathematics.

Newton iteration

According to the following formula:

x= (x+tmp_x/x)/2
Copy the code

Newton iteration method

The problem solving code

violence

var isPerfectSquare = function(num) {
    if(num == 1) return true;
    const mid = num / 2;
    for(let i = 1; i <= mid; i++){
        if(i*i == num){
           return true;
        }
    }
    return false;
}
Copy the code

dichotomy

var isPerfectSquare = function(num) {
    if(num == 1) return true;
    let left = 1,right = num;
    while(left <= right){
        let mid = parseInt((left+right)/2);
        let temp = mid*mid;
        if(temp == num){
             return true;
        }else if(temp > num){
             right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return false;
}
Copy the code

The mathematical method

var isPerfectSquare = function(num) {
        let i = 1;
        while(num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;
}
Copy the code

Newton iteration method

var isPerfectSquare = function(num) {
    if(num == 1){
        return 1;
    }
    var tmp = num;
    while(num*num > tmp){
        num = (num+tmp/num)/2 | 0;
    }
    return num*num == tmp;
};
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign