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

preface

Today’s topic, in order, should be question 8 string conversion integer (ATOI), but this question is completely on the string boundary conversion investigation, I think there is no algorithm thought, so this time skip question 8.

Today’s topic 1

Given an integer x, return true if x is a palindrome integer; Otherwise, return false.

Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Example 1:

Input: x = 121 Output: true

Example 2:

Input: x = -121 Output: false Description: Read from left to right. The value is -121. Read from right to left, 121-. So it’s not a palindrome number.

Example 3:

Input: x = 10 Output: false Description: Read from right to left, 01. So it’s not a palindrome number.

Example 4:

Input: x = -101 Output: false

Advanced: Can you solve this problem by not converting integers to strings?

Train of thought

The meaning of palindromes has already been introduced in the longest anaphora substring

Here palindromes are similar in that both positive (left to right) and backward (right to left) are integers

The question is also based on the double-pointer method to determine whether before and after the same

If the number is negative, return false because it must not be a palindrome because it has’ – ‘

public boolean isPalindrome(int x) {
    if( x < 0) {return false;
    }
    String s = String.valueOf(x);
    int left = 0, right = s.length()-1;

    while(left <= right){
        if(s.charAt(left) == s.charAt(right)){
            left++;
            right--;
        }else{
            return false; }}return true;
}
Copy the code

Execution time: 6 ms, beating 96.93% of users in all Java commits

Memory consumption: 37.9 MB, beating 46.32% of all Java commits

Method 2

A palindrome is an integer that reads in positive order (from left to right) and backward order (from right to left)

In other words, when the number is flipped to the same value as before, you can use the integer flipping idea above

public boolean isPalindrome(int x) {
    if( x < 0) {return false;
    }
    int temp = x;
    long result = 0;
    while(x ! =0) {int cuur = x %10;
        result = result * 10 + cuur;
        x = x /10;
    }
    return temp == result;
}
Copy the code

Execution time: 5 ms, beating 98.60% of all Java commits

Memory consumption: 37.8 MB, beating 54.14% of all Java commits

Today’s Topic 2

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container.

Example 1:

,8,6,2,5,4,8,3,7 input: [1] output: 49 explanation: the figure in the vertical line represents the input array,8,6,2,5,4,8,3,7 [1]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.

Example 2:

Input: height = [1,1

Example 3:

Input: height = [4,3,2,1,4

Example 4:

Input: height = [1,2,1

Tip:

n == height.length 2 <= n <= 105 0 <= height[i] <= 104

Train of thought

So if we start with two Pointers one to the beginning and one to the end, then the bottom of the container is the largest,

Then as the pointer moves inward, the bottom of the container becomes smaller. In this case, the only way to make the container hold more water is to work on the height of the container.

So how do you decide which pointer to move? We can see that whether the left pointer moves one to the right or the right pointer moves one to the left, the base of the container is the same, it’s reduced by one.

After this case, we want to let the pointer containers area increases, make mobile container after high as far as possible big, so we choose the pointer to pointer refers to high small mobile, so that we will retain the container higher the edge, and gave up the smaller the edge, to get more opportunities.

Save the maximum volume after each move, and then move the pointer, why move the small pointer can be?

That’s because height is determined by the middle of the two sides,

So if you move the higher side, even if you meet the higher side, the volume will not increase

If you move a short one it could get bigger or it could get smaller

implementation

public int maxArea(int[] height) {
    int result = 0;
    int left = 0, right = height.length -1;
    while(left < right){
        // Move the pointer which is shorter on both sides
        if(height[left] < height[right]){
            result = Math.max(result, height[left]*(right - left));
            left++;
        }else{ result = Math.max(result, height[right]*(right - left)); right--; }}return result;
}
Copy the code

Execution time: 3 ms, beating 92.67% of all Java commits

Memory consumption: 51.8 MB, beating 64.99% of all Java commits

summary

It can be seen from the force buckle 9/10, double pointer is very common in solving problems, but also very useful, through several questions obviously feel much faster than brute force cracking, similar to the sum of three numbers described in the previous article are the use of double pointer.

Double pointer, or with more than three pointer problems are a certain rule, these problems have constantly compressed the characteristics of the search distance, and then encounter similar problems can be familiar with the road.

Learn more today and say less tomorrow. Come on!