This is the 12th day of my participation in Gwen Challenge

Perfect squares of valid numbers (367)

Topic describes

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.

Example 1:

Input: num = 16 Output: trueCopy the code

Example 1:

Input: num = 14 Output: falseCopy the code

prompt

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

Thought analysis

To find the perfect square of a square, or to find the square root of a number, many times you can use dichotomy, the default number is from small to large, so through dichotomy search, the number of searches is very small.

If we use mid * mid to determine whether it is equal to the target value, we may cause mid * mid to cross the boundary. Of course, we can also use long to handle the problem. Num /mid == mid && num % mid == 0

Binary search has certain routines, first define low and high. The judgment condition of the while loop is always low <= high. For low == high, special processing is made when necessary, and the return value is always mid. Low = mid + 1 and high = mid – 1;

For the non-deterministic search, the pre – and post-detection method is used to determine the search interval. We deal with hits first, and then we deal with left and right half look-ups.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public boolean isPerfectSquare(int num) { // If k decimal is needed, what is the solution??
        if (num == 0 || num == 1) {return true;
        }
        int low = 0;
        int high = (num + 1) /2; / / 5
        while (low <= high){
            int mid = low + (high - low)/2;
            if (mid == 0) {return false;
            }

            if (num/mid == mid && num % mid == 0) {Num % mid == 0
                return true;
            } else if (num/mid > mid){ / / September 18
                low = mid + 1;
            } else {
                high = mid - 1; }}return false;
    }
Copy the code

The square root of x 69.

Topic describes

Implement the int SQRT (int x) function. Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Example 1:

Input: 4 Output: 2Copy the code

Example 2:

Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

Thought analysis

So this is going to be a dichotomy, and we’re going to do the same thing, but we’re going to take decimals, we’re going to take integers, and we’re going to pay attention to the fact that x/mid is greater than = mid, so we’re going to have an equal sign.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public int mySqrt(int x) {  / / 5 2
        if (x <= 1) {return x;
        }
        int low = 0;
        int high = x/2+1; / / 3
        while (low <= high){
            int mid = low + (high - low)/2;
            if (x / mid == mid && x % mid == 0) {return mid;
            } else if (x / mid >= mid){ // It's important to add equal signs like 5/2 = 2
                low = mid + 1;
                if (x / low < low){
                    returnmid; }}else {
                high = mid - 1;
            }
            if (low == high){
                if (low * high == x){
                    returnlow; }}}return -1;

    }
Copy the code

conclusion

Both square roots and perfect squares can be solved using dichotomy, and we need to master dichotomy. Binary search has certain routines, first define low and high. The judgment condition of the while loop is always low <= high. For low == high, special processing is made when necessary, and the return value is always mid. Low = mid + 1 and high = mid – 1;

For the non-deterministic search, the pre – and post-detection method is used to determine the search interval. We deal with hits first, and then we deal with left and right half look-ups.