Niuke programming problem -- double pointer of 101 must be brushed

Supplementary knowledge

Double pointer

Double pointers in a broad sense , It refers to the problem solved by traversing two variables on a linear structure . In a narrow sense ,

• about Array , It refers to the problem that two variables move towards each other on the array , Also known as 「 Left and right pointer 」 problem ;
• about Linked list , It refers to the problem that two variables move in the same direction on the linked list , Also known as 「 Speed pointer 」 problem ;

Left and right pointer

First, judge whether to use left and right pointers or fast and slow pointers , This can be selected according to the data structure , If you give an array , Then you can consider using left and right pointers . The left and right pointers in the array actually refer to two index values ,⼀ Generally, it is initialized to left = 0, right =nums.length - 1 .

Sliding window algorithm framework ：

int	left	=	0,	right	=	0;
while	(right	<	s.size())	{`
	# Increase the window 
	window.add(s[right]);				
	right++;
	while	(window	needs	shrink)	{
		//	 shrink ⼩ window ⼝								
		window.remove(s[left]);								
		left++;
		}
}

Speed pointer

【 The main data structure storage method is Linked list 、 Linked list 、 Linked list 】
Speed pointer ⼀ Generally, the header node pointing to the linked list is initialized head, Move forward with a quick pointer fast before , Slow pointer slow After , Ingenious solution ⼀ Some problems in the linked list .

The specific content and title have been sent before , Interested partners can check Xiao Zeng took you to brush leetcode– Left and right pointers in the double pointer chapter ( One ) Xiao Zeng took you to brush leetcode -- The fast and slow pointer of double pointer ( Two )

1、 Merge two ordered arrays

Title Description ： Give an ordered array of integers A And an ordered array of integers B , Please array B Merge into array A in , Into an ordered ascending array

Input ：
[4,5,6],[1,2,3]
Return value ：
[1,2,3,4,5,6]
explain ：A The array is [4,5,6],B The array is [1,2,3], The daemon will pre A Capacity for [4,5,6,0,0,0],B Still for [1,2,3],m=3,n=3, Passed to function merge Inside , Then ask the students to complete merge function , take B Data consolidation of A Inside , Finally, the background program outputs A Array

Ideas ： Since it is two arrays that have been ordered , If you can use a new auxiliary array , That's easy. We can use the idea of merging and sorting , Merge the ordered two sub arrays together . But this problem requires us to be in the array A Add above , That's because of the array A The second half is equivalent to empty , Then we can consider using the idea of merging and sorting in reverse , Start with the larger . For two arrays, select the larger value each time , Therefore, you need to use two double pointers that traverse forward at the same time .

Specific steps ：
step 1： Use three pointers ,i Pointing to the array A The largest element of ,j Pointing to the array B The largest element of ,k Pointing to the array A At the end of space .
step 2： Start with the largest element of the two arrays , Until a certain end , Take out a larger value at a time and put it into the array A The end of space , Then the pointer moves forward once .
step 3： If the array B End of traversal first , Array A The first half already exists , Never mind ; But if the array A End of traversal first , You need to put the array B The remaining first half is added to the array in reverse order A First half part , Similar to the last step of merging and sorting .

Code implementation ：

import java.util.*;
public class Solution {
    
    public void merge(int A[], int m, int B[], int n) {
    
        //  Define three pointers 
        int i = m-1,j = n-1,index = m+n-1;
        //  Satisfaction is greater than 0 The situation of 
        while(i>=0 && j>=0){
    
            //  If A The array is greater than B Array , Will A Put the array elements at the end 
            if(A[i]> B[j]){
    
                A[index--] = A[i--];
            }else{
    
            //  conversely , take B Put the array at the end 
                A[index--] = B[j--];
            }
        }
        //  If A Array traversal ends first , You need to B The rest of the array is added based on the reverse order A in 
        while(j>=0){
    
            A[index--] = B[j--];
        }
  
    }
}

2、 Determine whether it is a palindrome string

Title Description ： Given a length of n String , Please write a function to judge whether the string is palindrome . If it is a palindrome, please return true, Otherwise return to false.
String palindrome means that the positive order of the string is consistent with its reverse order character by character .

Example 1
Input ：“absba”
Return value ：true
Example 2
Input ：“ranko”
Return value ：false

Ideas ： Direct head and tail double pointer
Palindrome string forward traversal and reverse traversal results are the same , So we can prepare two collision pointers , A forward traversal , A reverse traversal .

// Head pointer 
int left = 0;
// Tail pointer 
int right = str.length() - 1;
// Head and tail to the middle  
while(left < right){
     
    ......
}

Specific steps
step 1： Prepare two pointers , One at the beginning of the string , One at the end of the string .
step 2： The pointer at the head goes back , The pointer at the end goes forward , Compare whether the two characters passing by are equal in turn , If it is not equal, it is not palindrome directly .
step 3： Until the two pointers meet in the middle , All are consistent, that is, palindromes . Because the first pointer reaches the second half , It happened to be the way the tail pointer walked , The two just exchanged positions , Compare equal or same .

public boolean judge (String str) {
    
        //  Define the beginning and end pointers 
        int left = 0,right = str.length() -1;
        while(left < right){
    
            if(str.charAt(left) != str.charAt(right))
                return false;
            left ++ ;
            right --;
        }
        return true;
    }

3、 Merge range

Title Description ： Give a set of intervals , Please merge all overlapping intervals .
Please make sure that the merged intervals are arranged in ascending order according to the starting point of the interval .

Example 1
Input ：[[10,30],[20,60],[80,100],[150,180]]
Return value ：[[10,60],[80,100],[150,180]]
Example 2
Input ：[[0,10],[10,20]]
Return value ：[[0,20]]

Their thinking : Greedy thoughts

Greedy thoughts It belongs to a kind of dynamic programming thought , The basic principle is to find the optimal solution of each local substructure in the whole , And finally combine all these local optimal solutions to form an optimal solution as a whole .

First, consider what kind of intervals can be merged ： Intersecting interval 【 The head of the latter interval is smaller than the tail of the previous interval 】

// The intervals overlap , Update end 
if(intervals[i].start <= res.back().end) 
    res.back().end = max(res.back().end, intervals[i].end);

Then we must have orderly intervals to a certain extent to facilitate comparison （ The interval has two boundary values , Complete order is impossible , But it can be sorted according to the first interval ）, At this time, as long as we traverse to the crossing situation , Just use greedy thoughts , Always merge , Until we can't merge .

Specific steps ：
step 1： Since the overlapping intervals are required to be arranged in ascending order according to the starting position , Let's sort all the intervals first according to the starting position . Use sort Function to sort , Overloaded comparison mode is comparison interval Structural start Variable .
step 2： The first interval after sorting must be the interval with the lowest starting point , We count it into the return array res, Then traverse the subsequent interval .
step 3： During subsequent traversal , If the starting point value is less than res The end value of the last interval in , That must be overlap , Take the maximum end value of both to update res The last interval in .
step 4： If the starting point value is greater than res The end value of the last interval in , There must be no overlap , There will be no overlapping interval at the end in the future , Because the starting point behind will only be bigger , So you can add it res.

import java.util.*;

public class Solution {
    
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals.size() == 0)
            return res;
        //  Sort the first interval , Overload comparison 
        Collections.sort(intervals, new Comparator<Interval>(){
    
            public int compare(Interval a1, Interval a2){
    
                if(a1.start != a2.start)
                    return a1.start - a2.start;
                else
                    return a1.end -a2.end;
            }
        } );
        //  Put in the first smallest interval 
        res.add(intervals.get(0));
        int count = 0;
        //  Continue traversing 
        for(int i=1; i< intervals.size(); i++){
    
            Interval a1 = intervals.get(i);
            Interval a0 = res.get(count);
            if(a1.start > a0.end){
    
                res.add(a1);
                count++;
            }else{
    
                //  There is overlap 
                res.remove(count);
                Interval s = new Interval(a0.start, a1.end);
                if(a1.end < a0.end){
    
                    s.end = a0.end;
                }
                res.add(s);
            }  
        }
        return res;
    }
}

4、 Minimum cover substring

Title Description ： Give me two strings s and t, Ask for in s Find out the shortest inclusion in t Consecutive substrings of all characters in .
for example ：
S ="XDOYEZODEYXNZ"S=“XDOYEZODEYXNZ”
T =“XYZ"T=“XYZ”
The shortest substring found is "YXNZ”“YXNZ”.

Example Input ：“abcAbA”,“AA” Return value ：“AbA”

Ideas ： You can slide the window directly + hash Table to count

A sliding window is an array 、 character string 、 A segment on a linear structure such as a linked list , It's like a window , This window can slide from beginning to end on the above linear structure in turn , And the beginning and end of the window can shrink . When we deal with sliding windows , Double pointers are often used to solve , The left pointer maintains the left boundary of the window , Maintain the right pointer of the window , They move the maintenance window at different rates in the same direction .

A hash table is a key based method （key） Direct access to values （value） A data structure of . And this direct access means just knowing key You can be in O(1)O(1)O(1) Get... In time value, Therefore, hash table is often used to count frequency 、 Quickly check whether an element has appeared, etc .

The string contains only uppercase and lowercase letters , Then the character set is known and Limited , In this case, we can consider quickly finding the hash table of whether an element has appeared —— Only one hash table needs to be maintained , The string T The characters in are used as key value , When the character is in T One occurrence in... Corresponds to value Value reduction 1：

for(int i = 0; i < T.length(); i++)
    // The initialization hash table is negative , Add positive when looking 
    hash[T.charAt(i)] = -1; 
// Later, if in the string S If you find the corresponding character in, you can add it back 
char c = S.charAt(fast);
// Target character match +1
hash[c]++;
// Then use the double pointer to maintain the sliding window , In the window , In the hash table value Is greater than 0：
for (int i = 0; i < hash.length; i++) {
    
    if (hash[i] < 0)
        return false;
}
return true;
// In this window T All strings in , At this point, you can try to narrow the window , Because the double pointer traverses to the right synchronously , Therefore, reducing the window can only reduce the left boundary .

Specific steps ：
step 1： Create hash table , Traversal string T, Count the frequency of each character , The frequency meter is negative .
step 2： Iterate through the string in turn S, If it matches, add the corresponding characters in the hash table 1.
step 3： Maintain a window during traversal , If all elements in the hash table are greater than 0, It means that we have found all , Then the window shrinks and moves to the left , Find the smallest Window , If this condition is not met, the window moves right to continue matching . The smallest window needs to be updated when the window moves , To get the shortest substring .
step 4： If it matches to the end , window left（ For the initial -1） There is no right shift , It means that we didn't find , Just return an empty string .
step 5： Finally, use the string interception function , The shortest substring that meets the conditions can be obtained by intercepting the window just recorded .

import java.util.*;


public class Solution {
    
    /** * * @param S string character string  * @param T string character string  * @return string character string  */
    boolean check(int[] hash) {
     // Check if there is ⼩ On 0 Of 
        for (int i = 0; i < hash.length; i++) {
    
            if (hash[i] < 0)
                return false;
        }
        return true;
};
    public String minWindow (String S, String T) {
    
        // write code here
        int cnt = S.length() +1;
        // hash  Table records the target string T Characters of 
        int[] hash = new int[128];
        for(int i = 0; i< T.length(); i++)
            //  The initialization hash table is negative , Look for positive 
            hash[T.charAt(i)] -= 1;
        //  The sliding window 
        int slow = 0, fast = 0;
        int left = -1, right =-1 ; // Record the left and right intervals 
        for(; fast < S.length(); fast++){
    
            char c = S.charAt(fast);
            hash[c] ++;
            while(check(hash)){
    
                //  It's covered , contract the window 
                if( cnt > fast -slow +1){
    
                    cnt = fast -slow +1;
                    left = slow;
                    right = fast;
                }
                c  = S.charAt(slow);
                hash[c]--;
                slow ++; //  The window shrinks 
            }
        }
        if(left == -1){
    
            return "";
        }  
        return S.substring(left , right +1);
    }
}

5、 Reverse string

Title Description ： Write a program , Accept a string , Then output the inverted string of the string .（ The string length does not exceed 1000）

Example ： Input ：“abcd” Return value ：“dcba”

Ideas ： String inversion is the reverse order , The sequence is reversed , That is, the front character is replaced by the back , The following characters are replaced by the front , In that case, we will exchange the sequence symmetrically , At this time, we need to use the collision double pointer , Traverse from front to back at the same time .

Specific steps ：
step 1： Prepare two pointers , Start from the beginning and end of the string at the same time .
step 2： Exchange the characters pointed to by both each time , Until they meet , In this way, the beginning and end of the string can be exchanged , Complete inversion .

import java.util.*;


public class Solution {
    
    /** *  Reverse string  * @param str string character string  * @return string character string  */
    public String solve (String str) {
    
        // write code here
        char[] s = str.toCharArray();
        int left = 0, right = str.length()-1;
        while(left < right){
    
            char c = s[left];
            s[left] = s[right];
            s[right] = c;
            left ++;
            right --;
        }
        return new String(s);
    }
}

6、 Longest non repeating subarray

Title Description : Given a length of n Array of arr, return arr The length of the longest non repeating element subarray of , No repetition means that all numbers are different .
Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray

Example ： Input ：[2,3,4,5] Return value ：4 explain ：[2,3,4,5] Is the longest subarray

Input ： [2,2,3,4,3] Return value ： 3 explain ： [2,3,4] Is the longest subarray

Ideas ： The idea of sliding windows
Since you want to find the length of a continuous subarray that does not repeat , We can use sliding windows , Make sure that there is no repetition in the window , Then the right edge of the window keeps sliding to the right , If a duplicate array appears in the window , It indicates that the newly added element is the same as the previous one , You only need to shrink the left edge of the window to the right to ensure that there is no repetition in the window .

And ensure that the elements in the window are not repeated , We can use according to key Value quick access hash table ,key The value is the element in the window ,value For the number of times , As long as the number of new elements added to the window is not 1, It's repetition .

while(mp.get(arr[right]) > 1) 
    // Window left , At the same time, subtract the number of occurrences of the number 
    mp.put(arr[left],mp.get(arr[left++])-1); 

Specific steps ：
step 1： Build a hash table , Used to count the number of occurrences of array elements .
step 2： The left and right bounds of the window start from the beginning of the array , Every time the window moves to the right first , And count the frequency of elements entering the window .
step 3： Once the occurrence frequency of the right boundary element is greater than 1, You need to move the left boundary to the right until there is no repetition in the window , When removing the element on the left from the window, you need to reduce its frequency in the hash table 1, Ensure that the frequencies in the hash table are the frequencies in the window .
step 4： Each cycle , Maintain the maximum window length .

import java.util.*;


public class Solution {
    
    /** * * @param arr int Integer one-dimensional array  the array * @return int integer  */
    public int maxLength (int[] arr) {
    
        //  Sliding window ideas 
        //  use hash Table records non repeating numbers in the window 
        HashMap<Integer, Integer> mp = new HashMap<>();
        int res = 0;
        //  Set the left and right boundaries of the window 
        for(int left = 0, right = 0; right < arr.length ; right ++){
    
            //  Record the number of times 
            if(mp.containsKey(arr[right])){
    
                mp.put(arr[right],mp.get(arr[right])+1);
            }
            else
                mp.put(arr[right],1);
            //  When the number of occurrences is greater than 1, Need to slide 
            while(mp.get(arr[right])>1){
    
                //  Move window right 
                mp.put(arr[left],mp.get(arr[left++])-1);
            }
            res = Math.max(res, right-left+1);
        }
        return res;
    }
}

7、 The container with the most water

Title Description ： Given an array height, The length is n, Each number represents the height of a point in the coordinate axis ,height[i] In the first i The height of the point , Excuse me, , Choose from 2 Height and x How much water can the container composed of shafts hold at most
1. You can't tilt the container
2. When n Less than 2 when , Deemed not to form a container , Please return 0
3. The data ensure that the maximum amount of water can be accommodated will not exceed the shaping range , That is, it will not exceed 231-1

As input height by [1,7,3,2,4,5,8,2,7], So as shown in the figure below :

Input ：[1,7,3,2,4,5,8,2,7] Return value ：49

thought ： Double pointer + Greedy thoughts
This problem uses the short board principle of the bucket , The shorter side controls the maximum amount of water , Therefore, the current volume can be obtained by multiplying the shorter side length by the distance between the two sides of the bottom . But how to find the maximum value ？

You can use greedy thoughts ： We all know that the volume is related to the shortest side length and the bottom side length , And the long bottom edge must take the head and tail as the edge , But the head and tail are not necessarily high enough , It may be higher in the middle but shorter at the bottom , So we can use the colliding double pointer to lean towards the middle , In this way, the length of the bottom edge will be shortened , Therefore, if you want to have a larger volume, you can only increase the shortest length , At this point, we move the shorter side every time the pointer moves , Because under the greedy thought, the longer side is more likely to have a larger volume than the shorter side .

// Give priority to shorter edges 
if(height[left] < height[right])
    left++;
else
    right--;

Specific steps ：
step 1： Give priority to the exclusion of special cases that cannot form containers .
step 2： Initialize double pointers to the beginning and end of the array , Use the above formula to calculate the current volume each time , Maintain a maximum volume as the return value .
step 3： The colliding double pointer leans towards the middle , But according to greed , Each time the pointer pointing to the shorter side leans towards the middle , The other pointer remains unchanged .

import java.util.*;


public class Solution {
    
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param height int Integer one-dimensional array  * @return int integer  */
    public int maxArea (int[] height) {
    
        // write code here
        if(height.length < 2)
            return 0;
        int res = 0;
        int left = 0;
        int right = height.length -1;
        while(left < right){
    
            //  Calculate water capacity 
            int capacity = Math.min(height[left], height[right]) *(right - left);
            //  Maintenance maximum 
            res = Math.max(res, capacity);
            //  Give priority to shorter edges 
            if(height[left] < height[right])
                left++;
            else 
                right--;
        }
        return res;
        }
}

8、 The rain problem

Title Description ： Given an array of integers arr, It is known that all values are nonnegative , Think of this array as a column height map , Calculate columns arranged in this way , How much rain can be received after rain .( The height of the area outside the array is treated as 0)

Input ：[3,1,2,5,2,4] Return value ：5
explain ： Array [3,1,2,5,2,4] A diagram showing the height of the column , under these circumstances , Can connect 5 Units of rain , Blue is rain , As shown in the figure .

We all know the short board problem of the bucket , The shortest board controls the amount of water in the bucket . This problem is similar , We can think of the whole picture as a bucket , On both sides are the plates of the bucket , The lower part in the middle is the bottom of the bucket , The maximum amount of water in the bucket is controlled by the shorter side . But higher edges may appear in the bucket , For example, the fourth column in the above figure , It is higher than the edge of the bucket , In this case, does it divide a bucket into two buckets , And the middle side is the side of two buckets .

With this idea , It's easy to solve this problem , Because the bucket here has two sides , Therefore, we can consider using the colliding double pointer to lean towards the middle .

Specific steps ：
step 1： Special case of checking whether the array is empty
step 2： Prepare double pointer , Point to the beginning and end of the array , Represents the first two boundaries
step 3： The pointer traverses the middle , The lower column is the bottom , Subtracting the bottom from the shorter boundary is the water receiving capacity of this column , Meeting a higher column is a new boundary , Update boundary size .

import java.util.*;


public class Solution {
    
    /** * max water * @param arr int Integer one-dimensional array  the array * @return long Long integer  */
    public long maxWater (int[] arr) {
    
        //  Exclude empty arrays 
        if(arr.length == 0)
            return 0;
        long res = 0;
        //  Left and right hands 
        int left =0;
        int right = arr.length -1;
        //  The boundary height of the middle area 
        int maxL = 0;
        int maxR = 0;
        //  Until the left and right pointers meet 
        while(left < right){
    
            //  Maintain the maximum boundary 
            maxL = Math.max(maxL, arr[left]);
            maxR = Math.max(maxR, arr[right]);
            //  Determine the amount of water in the grid 
            if(maxR > maxL)
                res += maxL - arr[left++];
            else
                res += maxR- arr[right--];
        }
        return res;
    }
}