Personal tech blog: www.zhenganwen.top

Classic algorithms

Manacher algorithm

The original problem

Manacher algorithm is derived from the title “Finding the length of the longest loop substring in a string”. For example, the longest substring of abCDCB is BCDCB, which has a length of 5.

We can iterate over each character in the string, and when we get to a character, compare whether the character to the left of the character is the same as the character to the right of the character, if they are the same, continue to compare the character to the right of the character to the left of the character, if they are the same, continue to compare… Let’s call this process “spreading out.” When expansion does not move, the substring of all characters that pass through is the longest loop substring centered on the currently traversed character.

Each time we iterate, we get the length of the longest substring, use a global variable to hold the largest one, and then we get the solution. But analyzing the time complexity of this method: when it comes to the first character, it can only be expanded by 1; When it comes to the second character, it expands by at most two; … ; At most (n-1)/2+1 when you reach the middle character of the string; So the time complexity is 1+2+… + (n – 1) / 2 + 1 is O (n ^ 2). But Manacher’s algorithm does O(N).

The following concepts are defined in Manacher algorithm:

  • Palindrome radius: The maximum number of characters in a string that can expand outward is called the palindrome radius of that character. Such asabcdcbIn the characterd, can expand onecAnd you can expand another oneb, and then you get to the right edge of the string, and then you add the character itself, the characterdThe palindrome radius of is 3.
  • Palindrome radius arraypArr: Contains the palindrome radius of each character in the string. Such ascharArr="abcdcb", includingcharArr[0]='a'None of them expand, but they dopArr[0]=1; whilecharArr[3]='d'Up to 2, counting itselfpArr[3]=3.
  • Most right palindrome right boundaryR: The index of the right-most character that the operation expands to during traversal. Such asCharArr = "abcdcb", when traversing toaWhen, can only expandaBy itself, it doesn’t expand out, soR=0; When traversingbWhen, also can expand onlybItself, so updateR=1; But when you go over todCan expand two characters outward tocharArr[5]=b, soRUpdate to 5.
  • The palindrome center corresponding to the right boundary of the rightmost palindromeC:CwithRIs corresponding and updated simultaneously. Such asabcdcbTo traverse thedWhen,R=5.CischarArr[3]='d'The subscript3.

For example abCDcb, BCDCB belongs to a substring, but what if the substring is even? Like Cabbac, the “expanded” logic defined above does not mean that every character has a palindrome radius of 0, but in reality cabBAC’s longest substring is 6. Because we are the “expansion” is the logic of the default will be back to the text string as odd to see the length of the string, so we before using Manacher algorithm also need to deal with a string, here’s a tip, which is between the beginning and the end of the string and each character with a special symbol, can the input string so unified into the odd length of the string. For example, if abba is treated with #a#b#b#a, then charArr[4]=’#’ palindrome radius is 4, i.e. the maximum length of the original string is 4. The corresponding code is as follows:

public static char[] manacherString(String str){
  char[] source = str.toCharArray();
  char chs[] = new char[str.length() * 2 + 1];
  for (int i = 0; i < chs.length; i++) {
    chs[i] = i % 2= =0 ? The '#' : source[i / 2];
  }
  return chs;
}
Copy the code

Next, it analyzes how the BFPRT algorithm accelerates the solution of palindrome radius of subsequent characters by using pArr, R and C calculated in the traversal process.

First of all, in case 1, the traversed character’s subscript cur is to the right of R (another R=-1 at first). In this case, the solution of the maximum palindrome radius of the character pArr[cur] cannot be accelerated and can only be solved step by step by expanding outward.

In case 2, the traversed character subscript cur is to the left of R. In this case, the solving process of pArr[cur] can be accelerated by using the palindrome radius information of the character traversed previously. Make the symmetric points cur and R about C cur’ and L respectively:

  • If the left edge of the maximum extent of expansion from cur’ does not exceed L, then pArr[cur]=pArr[cur’].

    The proof is as follows:

    We have a record of the number of steps that can be expanded at cur’ (pArr[cur’]), meaning that the character Y ‘at cur’+pArr[cur’] is not equal to the character x’ at cur’ -parr [cur’]. According to the definition of R and C, the characters from L to R are symmetric with respect to C, that is, the largest subroutine that can be expanded by cur is the same as the largest subroutine that can be expanded by cur’, so it can be directly concluded that pArr[cur]=pArr[cur’].

  • If the left edge of the maximum range that expands from cur’ exceeds L, then pArr[cur]=R-cur+1.

    The proof is as follows:

    A character x to the right of R, x is symmetric with respect to cur y, x,y is symmetric with respect to C x’,y’. By definition of C and R we have x factorial. = x ‘; Since x’,y’ is inside and symmetric with respect to cur’, we have x’=y’, which follows x! = y ‘; And y,y prime is symmetric with respect to C, and is in L and R, so y is equal to y prime. To sum up, there is x! =y, so the palindrome radius of cur is R-cur+1.

  • The left margin of the largest expansion centered on cur’ is exactly L, so pArr[cur] >= (R-cur+1)

    In this case, the cur’ can be expanded by cur’-L, so the range that can be expanded by cur is R-cur. But whether or not the cur gets bigger depends on whether x and y are equal. And all we can get is x! =x’, y=y’, x’! =y’, the relation between x and y cannot be derived, only that the palindrome radius of cur is at least R-cur+1 (counting itself), and it is necessary to continue trying to expand outward to solve pArr[cur].

To sum up, there are four cases of pArr[cur] calculation: violent expansion, equal to pArr[cur’], equal to R-cur+1, and further expansion from R-cur+1. The process of using this algorithm to solve the original problem is to traverse the list of each character, each character is trying to enlarge to the largest outward and update the R (grow), increase the amount of each R is the number of characters to enlarge the R arrived at tail string can determine the problem solution, so every time time complexity is expanding operations to check the number of times the sum, That is, the range of R (-1 to 2N, since N+1 # characters were added to the string when processing the string), O(1+2N)=O(N).

The overall code is as follows:

public static int maxPalindromeLength(String str) {
  char charArr[] = manacherString(str);
  int pArr[] = new int[charArr.length];
  int R = -1, C = -1;
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < charArr.length; i++) {
    pArr[i] = i > R ? 1 : Math.min(pArr[C * 2 - i], R - i);
    while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
      if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
        pArr[i]++;
      } else {
        break; }}if (R < i + pArr[i]) {
      R = i + pArr[i]-1;
      C = i;
    }
    max = Math.max(max, pArr[i]);
  }
  return max-1;
}

public static void main(String[] args) {
  System.out.println(maxPalindromeLength("zxabcdcbayq"));
}
Copy the code

The code above condenses the branching of the four cases down to 7 to 14 lines. PArr [I]=1; pArr[I]++ =1; pArr[I]++ =1; Otherwise, the pArr[I] of the current character is either pArr[I ‘] (2* c-i), r-i +1, or >= r-i +1. The value of pArr[I] can be set to the smallest of the three cases. Then check if you can expand directly pArr[I]++ can.

The resulting Max is the radius of the longest substring of the processed string (length=2N+1), and max-1 is exactly the length of the longest substring of the original string.

Advanced problem

You are given a string that requires as few characters as possible to make it a palindrome string.

When R reaches the end of the string for the first time, take the symmetry point L of R with respect to C, and reverse the string before L.

BFPRT algorithm

Given an array of integers, return the KTH smallest number.

This problem can take advantage of the Dutch flag improved partition and random quicksort idea: Randomly choose a number, compared to the number of array divided into <, =, > three sections, = part number array which is a small number of easy to learn, then the < (small number if the first K in < section) or > (small number if the first K > section) part of the number of recursion, the process until = part number is the first K small number in the array. It is not difficult to do this and find the mathematical expectation of time complexity is O(NlogN) (base 2). However, this is a mathematical expectation after all, and there may be some deviation in the actual engineering performance, while BFPRT algorithm can achieve the time complexity is O(NlogN).

BFPRT algorithm firstly divides the array into N/5 small parts according to the group of 5 elements (less than 5 elements form a part by themselves at last), sorts the inner parts of these small parts, and then takes out the median of each small part and sorts again to get the median:

The procedure for BFPRT to solve this problem is basically similar to the procedure described at the beginning, but the step of “randomly selecting a number for comparison” is replaced by the final number as shown in the figure above.

O(NlogN) proof, why is the time complexity of this problem completely changed to O(NlogN) after the random choice of partition is changed to the choice logic defined by BFPRT? Here are the steps of the algorithm:

BFPRT algorithm, receive an array and a K value, return a number in the array

  1. The array is divided into twoN/5Five small sections, five numbers for each sectionO(1), all parts are neededO(N/5)=O(N)
  2. So let’s take the median of each of these piecesN/5, recursively call BFPRT algorithm to get the first of these numbers(N/5)/2The small number (that is, the median of these numbers) is denoted aspivot
  3. In order topivotFor comparison, divide the entire array into two<pivot , =pivot , >pivotThree regions
  4. Determine what region the KTH smallest number is in, if it’s in=The field returns directlypivot, if the<or>The BFPRT algorithm is recursively called for the number of this region
  5. base case: When the BFPRT algorithm is recursively called, it is found that there is only one number in this area, so this number is the number we are looking for.

Code examples:

public static int getMinKthNum(int[] arr, int K) {
  if (arr == null || K > arr.length) {
    return Integer.MIN_VALUE;
  }
  int[] copyArr = Arrays.copyOf(arr, arr.length);
  return bfprt(copyArr, 0, arr.length - 1, K - 1);
}

public static int bfprt(int[] arr, int begin, int end, int i) {
  if (begin == end) {
    return arr[begin];
  }
  int pivot = medianOfMedians(arr, begin, end);
  int[] pivotRange = partition(arr, begin, end, pivot);
  if (i >= pivotRange[0] && i <= pivotRange[1]) {
    return arr[i];
  } else if (i < pivotRange[0]) {
    return bfprt(arr, begin, pivotRange[0] - 1, i);
  } else {
    return bfprt(arr, pivotRange[1] + 1, end, i); }}public static int medianOfMedians(int[] arr, int begin, int end) {
  int num = end - begin + 1;
  int offset = num % 5= =0 ? 0 : 1;
  int[] medians = new int[num / 5 + offset];
  for (int i = 0; i < medians.length; i++) {
    int beginI = begin + i * 5;
    int endI = beginI + 4;
    medians[i] = getMedian(arr, beginI, Math.min(endI, end));
  }
  return bfprt(medians, 0, medians.length - 1, medians.length / 2);
}

public static int getMedian(int[] arr, int begin, int end) {
  insertionSort(arr, begin, end);
  int sum = end + begin;
  int mid = (sum / 2) + (sum % 2);
  return arr[mid];
}

public static void insertionSort(int[] arr, int begin, int end) {
  if (begin >= end) {
    return;
  }
  for (int i = begin + 1; i <= end; i++) {
    for (int j = i; j > begin; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      } else {
        break; }}}}public static int[] partition(int[] arr, int begin, int end, int pivot) {
  int L = begin - 1;
  int R = end + 1;
  int cur = begin;
  while(cur ! = R) {if (arr[cur] > pivot) {
      swap(arr, cur, --R);
    } else if (arr[cur] < pivot) {
      swap(arr, cur++, ++L);
    } else{ cur++; }}return new int[]{L + 1, R - 1};
}

public static void swap(int[] arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

public static void main(String[] args) {
  int[] arr = {6.9.1.3.1.2.2.5.6.1.3.5.9.7.2.5.6.1.9};
  System.out.println(getMinKthNum(arr,13));
}
Copy the code

If the time complexity is O(NlogN) (base 2) and the execution steps of BFPRT are analyzed (assuming the time complexity of BFPRT is T(N)) :

  1. First array 5 groups of 5 and internal sorting, sorting the 5 numbers isO(1), all groups are sorted asO(N/5)=O(N)
  2. A median group is formed by drawing the median from each group in Step 1N/5Number, recursive callbfprtFind out theN/5The number of the first(N/5)/2The small number (the median) isT(N/5)And remember topivot
  3. For step 2pivotFor comparison, the array is divided into less than, equal to, and greater than three fields, becausepivotIt’s the median in the median group, so the median group hasN/5/2=N/10The number of thanpivotSmall, thisN/10The numbers are respectively the median of a group in step 1, and it can be deduced that at least3N/10The number of thanpivotSmall, at most7N/10The number of thanpivotBig. That is, greater than the region (or less than the region) maximum contains7N/10Number, minimum3N/10Student: number, so if thetaiLarge numbers are not equal to regions, either recursivelybfprtThe process is smaller than or larger than a region, and in the worst case, the maximum size of the subprocess7N/10, i.e.,T(7N/10)

To sum up, there is a derivation formula for T(N) of BFPRT: T(N/5)+T(7N/10)+O(N). The time complexity of BFPRT is O(NlogN) (base 2) according to the Master formula introduced in the basic chapter.

Morris traverses the binary tree

About binary tree traversal sequence, in sequence, after the first sequence of the recursive and non-recursive version in the direct BAT algorithm (basic) 】 【 have said, but the time complexity of the six times calendar calculation method requires O (H) for tree height (H) of the extra space complexity, because in the process of the binary tree traversal only down to find the child node to be back in the parent node, So these algorithms use the stack to hold the parent nodes to be traced (the essence of recursion is that the system pushes the stack for us), and the stack must be able to hold at least H elements (for example, if we go back to the parent node when we traverse the leaf node, all of its parents must be on the stack). Morris traversal can achieve the time complexity of O(N) while the additional space complexity is only O(1).

Traverse the rules

First, before introducing Morris traversal, let’s leave behind the rules of pre-ordering, middle-ordering, and post-ordering. For example, pre-ordering traverses the first node of a tree, then the left subtree, and then the right subtree. This is also true for traversal of subtrees during traversal.

With these traversal rules behind us, let’s look at the criteria for morris traversal definitions:

  1. Define a traversal pointercur, the pointer first points to the header
  2. judgecurWhether the left subtree of
    • ifcurThe left child is empty, indicatingcurThe left subtree does not exist, thencurMoves to the right tocur.right
    • ifcurThe left child is not empty, indicatingcurThe left subtree of, find the rightmost node of the left subtree, denoted asmostRight
      • If,mostRightIf the child to the right is empty, make it pointcur(mostRight.right=cur) and move to the leftcur(cur=cur.left)
      • ifmostRightThe right child is not empty, then letcurMoves to the right (cur=cur.right), and will bemostRightThe right child is left blank
  3. After step 2, ifcurIf it’s not empty, go aheadcurGo to Step 2. Otherwise, the traversal is complete.

The following figure illustrates the entire process of morris traversal:

Pre-ordered and middle-ordered sequences

After traversal, it is easy to obtain the pre-ordered and middle-ordered sequence of the binary tree by slightly processing the sequence of nodes that cur advances:

Sample code:

public static class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data; }}public static void preOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while(cur ! =null) {
        if (cur.left == null) {
            System.out.print(cur.data+"");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }if (mostRight.right == null) {
                System.out.print(cur.data+"");
                mostRight.right = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void mediumOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while(cur ! =null) {
        if (cur.left == null) {
            System.out.print(cur.data+"");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                System.out.print(cur.data+"");
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    preOrderByMorris(root);
    mediumOrderByMorris(root);

}
Copy the code

It is worth noting here that the Morris traversal comes twice to a node where the left child is not empty, and only once to any other node. Therefore, when using Morris traversal to print the preordered sequence, if the node arriving at has no left child, it can be printed directly (this node only passes once); otherwise, it can be printed only if the right child of the rightmost node of the left subtree of the node arriving at is empty (this is the first time to arrive at this node). This ignores the second node in the sequence of nodes cur passes through; When morris is used to traverse the printing sequence, if the node comes to no left child, print it directly (this node only passes once, left-middle-right, and prints directly if there is no left child); otherwise, print it only when the right-most node of the left subtree of the node comes to is not empty (this is the second time to come to this node). This ignores the first repetition in the sequence of nodes cur passes through.

Sequence after sequence

Morris traversal is not so easy to obtain the posterior sequence of the binary tree, because for non-leaf nodes of the tree species, morris traversal will pass through it at most twice, and our posterior traversal will print the node on the third visit. Therefore, to obtain a post-sequence, it is not possible to simply change the timing of printing nodes in morris traversal.

In fact, during morris traversal, if the nodes on the right boundary of the left subtree of the node are printed from bottom to top when the node passes through the second time, and then the right boundary of the whole tree is printed from bottom to top, the final sequence of this number will be:

It does nothing more than print at the second node passed through in the Morris traversal. To print the right boundary of a tree from bottom to top, the nodes on the right boundary can be regarded as a linked list with the right pointer as the successor pointer, reverse it, print it, and finally restore the original structure. Sample code looks like this (where lines 18 and 19 are not interchangeable) :

public static void posOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while(cur ! =null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                printRightEdge(cur.left);
                cur = cur.right;
            }
        }
    }
    printRightEdge(root);
}

private static void printRightEdge(Node root) {
    if (root == null) {
        return;
    }
    //reverse the right edge
    Node cur = root;
    Node pre = null;
    while(cur ! =null) {
        Node next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
    //print 
    cur = pre;
    while(cur ! =null) {
        System.out.print(cur.data + "");
        cur = cur.right;
    }
    //recover
    cur = pre;
    pre = null;
    while(cur ! =null) { Node next = cur.right; cur.right = pre; pre = cur; cur = next; }}public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    posOrderByMorris(root);
}
Copy the code

Time complexity analysis

In Morris traversal, only the non-empty node of the left child passes through twice while the other nodes only pass through once, that is to say, the traversal times are less than 2N. Therefore, the time complexity of obtaining pre-ordered and middle-ordered sequences using Morris traversal is naturally O(1). But the time complexity of printRightEdge is also calculated, but you can see that in the whole traversal process, all printRightEdge add up to only traversal and print N nodes:

So the time is still O(N).

Morris traverses nodes not in first, middle, or last order, but in accordance with its own set of criteria to determine which nodes to traverse next.

Morris traversal is unique in that it takes full advantage of invalid references to leaf nodes (the reference points to empty, but the reference variable still occupies memory) to achieve O(1) time complexity.

Sum to aim’s maximum array length

For example, in the array [7,3,2,1,1,7,-6,-1,7], the oldest array whose sum is 7 is of length 4. Subarray: an array of any consecutive numbers in an array.

General premise: If we find all subarrays ending with each of the numbers in the array and subarrays that are aim, the answer must be there.

Rule: For array [I,… k,k+1… j], if aim is 800 and we know that the sum from I to j is 2000, then the sum from I to j is backward, and if the sum reaches 1200 at k, then k+1~j is the largest array with 800.

Steps: Take [7,3,2,1,1,7,-6,-3,7], AIM =7 as an example,

  • First of all to(0,-1)In theHashMapIn, representing 0, the summation appears before traversal.- > (0, 1)
  • The sum of the positions is then stored in each iterationHashMap, such asarr[0]=7, the sum formed at position 0 is the sum formed at the previous position0Plus what’s in this position7, therefore,(7, 0)In theHashMapWhere indicates that the accumulated sum is formed at position 0 for the first time7And then subtract the sum at that positionaim, i.e.,7-7 = 0, find the position where the accumulative sum is 0 for the first time, i.e- 1, so the oldest array whose subarray ends with subscript 0 and is aim is0 ~ 0, i.e.,7One element, maximum lengthmaxLength=1.- > (7, 0)
  • Then came toarr[1]=3, the accumulated sum formed at position 1 is7 + 3 = 10.HashMapThere is nokeyfor10The record is therefore placed(10,1)It means that the first sum formed at position 1 is 10, and then the sum at that position is subtractedaimnamely10-7 = 3And to theHashMapDo you have anykeyfor3Is the earliest position to form a summation of 3), found no, so there is no summation in the subarray ending with subscript 1aim.- > (1, 1)
  • Then came toarr[2]=2, the accumulated sum formed at position 2 is10 + 2 = 12.HashMapThere is nokeyfor12The record is therefore placed(12, 2).sum-aim=12-7=5And to theHashMapDo you have anykeyfor5So there is no summation in the subarray ending with subscript 2aim.- > (12, 2)
  • Came toarr[3]=1And in the(13, 3).sum-aim=5, the subarray ending with subscript 3 has no summation as AIM.- > (13, 3)
  • Came toarr[4]=1And in the(14, 4).sum-aim=7And found thatHashMapThere arekey=7The record of(7, 0)That is, the sum at position 0 is 7, so1 ~ 4Is the cumulative sum of subarrays ending at subindex 47Update the oldest array ofmaxLength=4.- > (14, 4)
  • Came toarr[5]=7And in the(21, 5).sum-aim=14.HashMapThere are(14, 4), so5 ~ 5Is the largest array of this round, butmaxLength=4>1, so no update.- > (21, 5)
  • Came toarr[6]=-6And in the15, 6, there is no matching subarray.- > (15, 6)
  • Came toarr[7]=-1, the sum is15 + (1) = 14, butHashMapThere arekey=14The record is therefore not placed(14, 7)(HashMapIs the first occurrence of the summation, and 14 is the earliest occurrence of the summation at the index 4.sum-aim=7.HashMapThere are(7, 0), so the oldest array of this round is1 ~ 7, so updatemaxLength=7.
  • Came toarr[8]=7, the cumulative sum is 21, there is a record with key 21, so (21, 7) is not added.sum-aim=14, the largest array of this round isFive to eight, length 4, not updatedmaxLength.

Sample code:

public static int maxLength(int[] arr,int aim) {
    //key->accumulate sum value->index
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    hashMap.put(0, -1);
    int curSum = 0;
    int maxLength = 0;
    for (int i = 0; i < arr.length; i++) {
        curSum += arr[i];
        if(! hashMap.containsKey(curSum)) { hashMap.put(curSum, i); }int gap = curSum - aim;
        if (hashMap.containsKey(gap)) {
            intindex = hashMap.get(gap); maxLength = Math.max(maxLength, i - index); }}return maxLength;
}

public static void main(String[] args) {
    int arr[] = {7.3.2.1.1.7, -6, -1.7};
    int aim = 7;
    System.out.println(maxLength(arr, aim));/ / 7
}
Copy the code

expand

Find the length of the smallest array with the same number of odd and even numbers

Setting an odd number to 1 and an even number to -1 translates to the length of the largest array summing to 0

Find the smallest array with the same number of 1 and 2 elements.

Setting 2 to -1 translates to the length of the largest array summing 0

The advanced

Find the maximum number of subarrays whose xOR sum is 0 in any partition scheme

Example: to give you an array,2,3,0,2,3,1,0 [1], you should be divided into [1, 2, 3], [0],,3,1 [2], [0], the answer is 4.

The main premise: If we find the maximum number of subarrays ending with each number in the array that can be divided arbitrarily, the answer must be there.

Law: XOR operation conforms to commutative and associative laws. ^ ^ 0 N = N, N, N = 0.

Possibility analysis: for an array [I,… j, m… n, K], assuming that multiple subarrays are formed after optimal partitioning in line with the question,k, as the end element of the entire array, must also be the end element of the last subarray. The last subarray can only have two cases: xOR and is not 0, and xOR and is 0.

  • If it is the former, then the xOR sum of the last subarray will not be 0 even if the element k is removed, otherwise the optimal partition will divide the last subarray into two subarrays, where K is a separate subarray. Let’s say the last subarray isindexOf(m)~indexOf(k), its xOR sum is not 0, thendp[indexOf(k)]=dp[indexOf(k)-1], represents an array0~indexOf(k)And its subarrays0~(indexOf(k)-1)The solution to alpha is the same.->case 1
  • If the latter, there can be no smaller xOR sum-0 subarray ending in k in the last subarray. Let’s say the last subarray isindexOf(m)~indexOf(k), its xOR sum is 0, thendp[indexOf(k)]=dp[indexOf(m)-1]+1, represents an array0~indexOf(k)Solution of = subarray0~(indexOf(m)-1)The solution of + 1.->case 2

Sample code:

public static int maxSubArrs(int[] arr) {
    if (arr == null) {
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap();
    map.put(0, -1);
    int curXorSum = 0;
    int res = 0;
    int[] dp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        curXorSum ^= arr[i];
        // Case 1, if there is no xor before, then dp at this position is equal to dp at the previous position
        if(! map.containsKey(curXorSum)) { dp[i] = i >0 ? dp[i - 1] : 0;
        } else {
            //case 2, the sum of the subarray from the previous xOR to the current position is 0
            int index = map.get(curXorSum);
            dp[i] = index > 0 ? dp[index] + 1 : 1;
        }
        // Record the most recent xor and, since we want to partition the most xor and 0 subarrays
        map.put(curXorSum, i);
    }
    // Dp in the last position is the solution to the whole problem
    return dp[dp.length -1];
}

public static void main(String[] args) {
    int arr[] = {1.2.3.0.2.3.1.0.4.1.3.2};
    System.out.println(maxSubArrs(arr));
}
Copy the code

The problem of collecting binary tree information of high routine

Find the maximum number of nodes in a binary tree

Maximum search binary tree refers to the subtree of the binary tree, which is the search binary tree with the largest number of nodes.

The general premise of this kind of questions is that if we can find the maximum number of nodes in a two-pronged tree that starts with any node in the tree, then the answer must be there.

For the subtree with any node as the head node, the solution of the maximum search two-fork tree can be divided into three cases (possibilities are listed) :

  • The maximum search two-fork tree for the whole tree exists in the left subtree. This requires that the maximal search two-fork tree exists in the left subtree but not in the right subtree.
  • The maximum search two-fork tree for the whole tree exists in the right subtree. This requires that the maximal search two-fork tree exists in the right subtree and the left subtree does not exist.
  • The largest searching binary tree for the entire binary tree is itself. This requires that the left subtree is a search binary fork tree with a smaller maximum node than the head node, and the right subtree is a search binary fork tree with a larger minimum node than the head node.

To distinguish between the three, we need to collect the following information:

  • Whether there is a maximum search binary tree in the subtree
  • The head of a subtree
  • The maximum node of the subtree
  • The minimum node of a subtree

So we can start our altitude routine:

  1. The information to be collected from the subtree is encapsulated into oneReturnDataRepresents the information to be returned to the parent after processing this subtree.
  2. Suppose I collect the information of the subtree using the subprocess, and then process all the information that the current tree should provide to the superior based on the information of the subtree and the conditions listed in the analysis of the problem, and return it to the superior (integration information).
  3. determinebase case, the subprocess stops when the subtree is empty.

Based on the analysis of the height routine above, we can write highly similar code to solve this kind of problem:

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data; }}public static class ReturnData {
    int size;
    Node head;
    int max;
    int min;
    public ReturnData(int size, Node head, int max, int min) {
        this.size = size;
        this.head = head;
        this.max = max;
        this.min = min; }}public static ReturnData process(Node root) {
    if (root == null) {
        return new ReturnData(0.null, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);
    
    //case 1
    int leftSize = leftInfo.size;
    //case 2
    int rightSize = rightInfo.size;
    int selfSize = 0;
    if (leftInfo.head == root.left && rightInfo.head == root.right
        && leftInfo.max < root.data && rightInfo.min > root.data) {
        //case 3
        selfSize = leftInfo.size + rightInfo.size + 1;
    }
    int maxSize = Math.max(Math.max(leftSize, rightSize), selfSize);
    Node maxHead = leftSize > rightSize ? leftInfo.head : 
    				selfSize > rightSize ? root : rightInfo.head;
    
    return new ReturnData(maxSize, maxHead, 
                          Math.max(Math.max(leftInfo.max, rightInfo.max), root.data), 
                          Math.min(Math.min(leftInfo.min, rightInfo.min), root.data));
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).size);/ / 4
}
Copy the code

Find the furthest distance of a binary tree

If in the binary tree, xiao Ming from node A, can go up to its parent node, and can go down to the child node, so xiao Ming from node to node B at least after A number of nodes (including A and B) is called the distance from A to B, any two nodes of the distance, the largest is called A maximum distance of the tree.

Highly routine:

The main premise: If we can find the maximum distance of all the subtrees in a subtree that starts at any node of the tree, then the answer is there.

For any subtree of this tree, the solution of its maximum distance can be divided into the following three cases:

  • The maximum distance of the tree is the maximum distance of the left subtree.
  • The maximum distance of the tree is the maximum distance of the right subtree.
  • The maximum distance of the tree is from the deepest node in the left subtree through the head of the tree to the deepest node in the right subtree.

Information to collect from subtrees:

  • Maximum distance of subtree
  • Depth of subtree

Sample code:

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data; }}public static class ReturnData{
    int maxDistance;
    int height;
    public ReturnData(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height; }}public static ReturnData process(Node root){
    if (root == null) {
        return new ReturnData(0.0);
    }
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);

    //case 1
    int leftMaxDistance = leftInfo.maxDistance;
    //case 2
    int rightMaxDistance = rightInfo.maxDistance;
    //case 3
    int includeHeadDistance = leftInfo.height + 1 + rightInfo.height;

    int max = Math.max(Math.max(leftMaxDistance, rightMaxDistance), includeHeadDistance);
    return new ReturnData(max, Math.max(leftInfo.height, rightInfo.height) + 1);
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.right.right = new Node(6);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).maxDistance);
}
Copy the code

Highly routinized: List the possibilities -> integrate the information gathered by the subprocess into the information to be returned by the process -> return

Maximum activity at PROM

The relationship between superiors and subordinates in a company is a multi-fork tree. This company is going to hold a party, and you, as the organizer, have already understood the psychology of everyone: if an employee’s immediate superior is present, the employee will definitely not come. Each employee has an activity score (the higher the number, the more active the party), so you can send an invitation to an employee to decide who will come and how to make the party the livelier. Returns the maximum active value.

For example:

If you invite A, then its direct subordinate BCD will not come, you can invite any number of EFGHJKL, if all invited, then the maximum activity of the dance is A(2)+E(9)+F(11)+G(2)+H(4)+J(7)+K(13)+L(5); However, if you choose not to invite A, you can invite any of B’s direct subordinates from BCD. For example, if B is invited but CD is not invited, B’s direct subordinate E will not come back, but CD’s direct subordinate E can be invited selectively.

The main premise: PROM Max is easy to know if you know the effect of each employee coming to PROM or not coming to PROM on PROM activity. For example, whether or not to invite A depends on: B comes or doesn’t come, chooses the one with the maximum gain for the dance activity value +C comes or doesn’t come, chooses the one with the maximum gain for the dance activity value +D comes or doesn’t come, chooses the one with the maximum gain for the dance activity value; The same applies to any employee’s decision whether to invite him or not.

Make a list of possibilities: come or not.

Information to be collected by the subprocedure: returns the greater value of the child employee’s gain on the dance activity value and the greater value of the gain on the dance failure value.

Sample code:

public static class Node{
    int happy;
    List<Node> subs;
    public Node(int happy) {
        this.happy = happy;
        this.subs = newArrayList<>(); }}public static class ReturnData {
    int maxHappy;
    public ReturnData(int maxHappy) {
        this.maxHappy = maxHappy; }}public static ReturnData process(Node root) {
    if (root.subs.size() == 0) {
        return new ReturnData(root.happy);
    }
    //case 1:go
    int go_Happy = root.happy;
    //case 2:don't go
    int unGo_Happy = 0;
    for (Node sub : root.subs) {
        unGo_Happy += process(sub).maxHappy;
    }
    return new ReturnData(Math.max(go_Happy, unGo_Happy));
}

public static int maxPartyHappy(Node root) {
    if (root == null) {
        return 0;
    }
    return process(root).maxHappy;
}

public static void main(String[] args) {
    Node A = new Node(2);
    Node B = new Node(8);
    Node C = new Node(5);
    Node D = new Node(24);
    B.subs.add(new Node(9));
    C.subs.addAll(Arrays.asList(new Node(11),new Node(2),new Node(4),new Node(7)));
    D.subs.addAll(Arrays.asList(new Node(13), new Node(5)));
    A.subs.addAll(Arrays.asList(B, C, D));
    System.out.println(maxPartyHappy(A));/ / 57
}
Copy the code

Evaluate a mathematical expression

Given a string STR, STR represents a formula that may contain integers, addition, subtraction, multiplication, and division symbols, and left and right parentheses.

For example, STR =”48*((70-65)-43)+8*1″, return -1816. STR =”3+1*4″, return 7. STR =”3+(1*4)”, return 7.

Description:

  1. You can assume that a given string must be the correct formula, that is, you don’t need to do a formula validity check on STR.
  2. If it’s a negative number, you put it in parentheses, for example"4 * (3)". But if a negative number is the beginning of a formula or the beginning of a parenthesis section, you can have no parentheses, for example"- 3 * 4" and "(3 * 4)"It’s all legal.
  3. You don’t have to worry about overflow in the calculation process

Optimal solution analysis: The difficulty of this problem is how to handle the parentheses in the expression, with the help of a stack. But if you rely on only one stack, the amount of code can be complicated. If we are going to type contains parentheses around the expression of calculation out alone as a process (process), so the process can be reused, if we will be around all the expression contains parentheses subexpression as a numeric value, then the original problem into a calculation does not contain the expression of the brackets.

Take the expression 3+2*5-(7+2)*3 as an example to analyze the solution steps:

Sample code:

public static int getValue(String exp){
    return process(exp.toCharArray(), 0) [0];
}

/ * * *@param exp   expression
     * @param index the start index of expression
     * @return int[], include two elements:the result and the endIndex
     */
public static int[] process(char[] exp, int index) {

    LinkedList que = new LinkedList();
    // The next number to be placed at the end of the queue
    int num = 0;
    // The result returned by the black box process
    int sub[];

    while(index < exp.length && exp[index] ! =') ') {

        if (exp[index] >= '0' && exp[index] <= '9') {
            num = num * 10 + exp[index] - '0';
            index++;
        } else if(exp[index] ! ='(') {
            // +, -, *, /
            addNum(num, que);
            num = 0;
            que.addLast(String.valueOf(exp[index]));
            index++;
        } else {
            / / '('
            sub = process(exp, index + 1);
            num = sub[0];
            index = sub[1] + 1;
        }
    }

    addNum(num, que);

    return new int[]{getSum(que), index};
}

private static int getSum(LinkedList<String> que) {
    int res = 0;
    boolean add = true;
    while(! que.isEmpty()) {int num = Integer.valueOf(que.pollFirst());
        res += add ? num : -num;
        if(! que.isEmpty()) { add = que.pollFirst().equals("+")?true : false; }}return res;
}

private static void addNum(int num, LinkedList<String> que) {
    if(! que.isEmpty()) { String element = que.pollLast();if (element.equals("+") || element.equals("-")) {
            que.addLast(element);
        } else{
            // * or /
            Integer preNum = Integer.valueOf(que.pollLast());
            num = element.equals("*")? (preNum * num) : (preNum / num); } } que.addLast(String.valueOf(num)); }public static void main(String[] args) {
    String exp = "48 * (43) (70-65) - * 1 + 8";
    System.out.println(getValue(exp));
    System.out.println(-48*38+8);
}
Copy the code

Find the largest subarray of the exception or sum

You’re given an array, and you’re told to figure out what the largest xor sum of all the subarrays is.

Violent solution

Iterate over each number in the array and find the xOR sum of all subarrays ending with that number.

public static class NumTrie{
    TrieNode root;

    public NumTrie(a) {
        root = new TrieNode();
    }

    class TrieNode{
        TrieNode[] nexts;
        public TrieNode(a){
            nexts = new TrieNode[2]; }}public void addNum(int num) {
        TrieNode cur = root;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (cur.nexts[path] == null) {
                cur.nexts[path] = newTrieNode(); } cur = cur.nexts[path]; }}/**
         * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i)
         * @param num -> xor(0,i)
         * @return* /
    public int maxXor(int num) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            // If it is a sign bit, try to be the same as it (so xor is positive), if it is a numeric bit try to be the opposite
            int bestPath = i == 31 ? path : (path ^ 1);
            // If the greedy path does not exist, you have to take another pathbestPath = cur.nexts[bestPath] ! =null ? bestPath : (bestPath ^ 1);
            // Record the xOR result on this bit
            res |= (bestPath ^ path) << i;

            cur = cur.nexts[bestPath];
        }
        returnres; }}public static int maxXorSubArray(int arr[]) {
    int maxXorSum = Integer.MIN_VALUE;
    NumTrie numTrie = new NumTrie();
    // The xOR sum is 0 when there are no numbers. This should also be added to the prefix number, otherwise the first time to find bestPath in the prefix tree will give a null pointer
    numTrie.addNum(0);
    int xorZeroToI = 0;
    for (int i = 0; i < arr.length; i++) {
        xorZeroToI ^= arr[i];
        maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
        numTrie.addNum(xorZeroToI);
    }
    return maxXorSum;
}


public static void main(String[] args) {
    int[] arr = {1.2.3.4.1.2, -7};
    System.out.println(maxXorSubArray(arr));
}
Copy the code

Time order N^3.

Optimized violence solution

Looking at the violent solution, take {1, 2,3,4, 1, 2, 0} as an example, when I calculate the xOR sum of all subarrays ending in 4, I will evaluate the subarray {4} first, then {3,4}, then {2,3,4}, that is, all the way to the end, The result of the previous calculation does not speed up the subsequent calculation process. So I thought, when I calculate {3,4}, I will temporarily save the 3^4 result and reuse it in the next {2,3,4} calculation, and then save the 2^3^4 result and reuse it in the next {1,2,3,4} calculation. The violent solution is then optimized to look like this:

public static int solution2(int[] arr) {
    int res = 0;
    int temp=0;
    for (int i = 0; i < arr.length; i++) {
        // Maximum xOR sum ending in I
        int maxXorSum = 0;
        for (int j = i; j >= 0; j--) {
            temp ^= arr[j];
            maxXorSum = Math.max(maxXorSum, temp);
        }
        // Maximum xOR sum of the whole
        res = Math.max(res, maxXorSum);
    }
    return res;
}

public static void main(String[] args) {
    int[] arr = {1.2.3.4.1.2.0};
    System.out.println(solution2(arr));/ / 7
}
Copy the code

The time is reduced to O(N^2).

The optimal solution

However, using prefix tree structure can achieve O(N) time complexity.

Limit the solution of the maximum xOR sum of all subarrays ending in I to O(1).

Problem-solving tips:

  1. For the subarray 0~ I (I is a legal subscript) and the subscript k between 0~ I (k is greater than or equal to 0, less than or equal to I), there are the following relations among the xOR between K ~ I and xor(k, I), xor between 0~ I and xor(0, I), xor between 0~k-1 and xor(0,k-1) : Xor (k, I)=xor(0, I) ^ xor(o,k-1) (A^B=C -> B=C^A), so finding the maximum value of xor(k, I) can be converted to finding the maximum value of xor(0, I) ^ xor(o,k-1).

  2. The traversal array places the 32-bit binary xOR and of subarrays beginning with the first element and ending with the current traversal element into a prefix tree structure (each bit is a character, and the character is either 0 or 1). After the traversal, all xor’s from 0 to I are stored in the prefix tree. For example, traversing {1, 2, 3, 4, 1, 2, 0} produces the following prefix tree:

  3. Let’s say that in the process of iterating through the prefix tree, the number 4 is iterated, and 0, 100 is put into it. Since 1,2, and 3 have been iterated before, xor(0,0), xOR (0,1), and xOR (0,2) are also in the prefix tree. If we want the maximum value of xor(k,3) (k is between the subscripts 0 and 3 and includes 0 and 3), we can translate this into finding xor(0,3) ^ xor(0,k-1), and we know that xOR (0,3)=0, 100, so solving xor(0,k-1) becomes the key.

    Solution of xOR (0,k-1) : at this time, the cursor cur moves from the root node of the prefix tree to the leaf node, and the binary bits passing along cur are connected together to be xOR (0,k-1). It is required that when selecting which binary bit to pass through, the xor result with xOR (0,3) should be larger as much as possible:

    This process is greedy (if it is a sign bit, then make the xor result as 0 as possible, if it is a numeric bit, then make the xor result as 1 as possible), the prefix tree only put xOR (0,0), xOR (0,1), xOR (0,2), xOR (0,3), and xOR (0,k-1) can only be evaluated from it. The process of going from the root node to the leaf node is a search for the xor corresponding to the path that maximizes xor ^ xor(0,3).

    Sample code:

    public static class NumTrie{
    TrieNode root;

    public NumTrie(a) {
        root = new TrieNode();
    }

    class TrieNode{
        TrieNode[] nexts;
        public TrieNode(a){
            nexts = new TrieNode[2]; }}public void addNum(int num) {
        TrieNode cur = root;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (cur.nexts[path] == null) {
                cur.nexts[path] = newTrieNode(); } cur = cur.nexts[path]; }}/**
         * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i)
         * @param num -> xor(0,i)
         * @return* /
    public int maxXor(int num) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            // If it is a sign bit, try to be the same as it (so xor is positive), if it is a numeric bit try to be the opposite
            int bestPath = i == 31 ? path : (path ^ 1);
            // If the greedy path does not exist, you have to take another pathbestPath = cur.nexts[bestPath] ! =null ? bestPath : (bestPath ^ 1);
            // Record the xOR result on this bit
            res |= (bestPath ^ path) << i;

            cur = cur.nexts[bestPath];
        }
        returnres; }}public static int maxXorSubArray(int arr[]) {
    int maxXorSum = 0;
    NumTrie numTrie = new NumTrie();
    // a prefix with a sum equal to 0 must be added to the prefix, otherwise the first attempt to find bestPath in the prefix tree will return a null pointer
    numTrie.addNum(0);
    int xorZeroToI = 0;
    for (int i = 0; i < arr.length; i++) {
        xorZeroToI ^= arr[i];
        maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
        numTrie.addNum(xorZeroToI);
    }
    return maxXorSum;
}


public static void main(String[] args) {
    int[] arr = {1.2.3.4.1.2, -7};
    System.out.println(maxXorSubArray(arr));/ / 7
}
Copy the code

The largest array summing as AIM (all greater than 0)

We did the same problem in the basics, except that the values of the elements in the array are positive, whereas the values in the basics can be positive or negative or zero.

The idea in the basics is to use a hash table to record the subarray and its earliest location. This problem can be completed within the extra space complexity O(1) and time complexity O(N) due to the particularity of data (all positive numbers).

Using a window, L represents the left edge of the window, R represents the right edge of the window, and sum represents the sum of the elements in the window (initially 0). At first, L and R both stop at -1, and each time L is expanded one step to the right or R is expanded one step to the right, depending on the situation:

  • ifsum<aimSo R expands to the right
  • ifsum=aim, then record the number of elements in the window, L expands to the right
  • ifsum>aimSo L expands to the right

Until R expands to arr.length, then the sum of elements in the window must be less than AIM, and the whole process can be ended. The answer is the maximum number of elements in the window given sum= AIM.

Sample code:

/** * All array elements are positive and sum to the length of aim's oldest array *@param arr
     * @return* /
public static int aimMaxSubArray(int arr[],int aim) {
    int L=-1;
    int R= -1;
    int sum = 0;
    int len=0;
    while(R ! = arr.length) {if (sum < aim) {
            R++;
            if (R < arr.length) {
                sum += arr[R];
            } else {
                break; }}else if (sum == aim) {
            len = Math.max(len, R - L);
            sum -= arr[++L];
        } else{ sum -= arr[++L]; }}return len;
}

public static void main(String[] args) {
    int arr[] = {1.2.3.5.1.1.1.1.1.1.9};
    System.out.println(aimMaxSubArray(arr,6));
}
Copy the code

Consider: Why does this process get the right answer? That is, why does the window slide right in the process and not miss the oldest array for AIM? We can prove it:

Suppose that the elliptic region is the largest array of sum to AIM. If L comes to the left edge of the elliptic region, L2, then the position of R can be in two ways: in the elliptic region, such as R1, and outside the elliptic region, such as R2. If it is the former, since window L2~R1 is definitely less than AIM (elements are all positive), L is always on L2 when R moves right from R1 to the right boundary of the elliptic region, so it is obvious that the correct answer will not be missed. If it is the latter, the sum of window L2~R2 obviously exceeds aim, so this situation is impossible to exist. When L is to the left of L2, for example L1, R is more unlikely to cross the ellipse to R2, because the window always keeps sum<= AIM.

The smallest array whose sum is less than or equal to AIM

If you use violence enumeration, enumerate the subarrays that begin with each element, then the answer must be there (O(N^3)). But here is a time complexity O(N) solution.

Firstly, the array is traversed from the end to the end, and two auxiliary arrays min_sum and MIN_SUM_index are generated as auxiliary information when solving. Min_sum indicates the minimum of all subarrays starting with an element, and min_sum_index corresponds to the end index of the subarray that stores the minimum sum.

For example, for [100,200,7,-6].

  1. So let’s first iterate over PI in position 3- 6In order to- 6The leading subarray is only[6], somin_sum[3] = -6, min_sum_index[3] = 3([6]The tail of the element- 6The subscript in the original array is theta3).
  2. And then I go all the way to position two7In order to7The smallest sum subarray at the beginning is[7-6], somin_sum[2] = 7-6 = 1, min_sum_index[2]=3. ([7-6]The tail of the element- 6The subscript in the original array is theta3).
  3. And then I go all the way to position one200, there aremin_sum[1] = 200, min_sum_index[1] = 1.
  4. And then I go all the way to zero100, there aremin_sum[0] = 100, min_sum_index[0] = 0.

After iterating through the array and generating two auxiliary arrays, we can begin the formal solution process:

Using a window, L represents the left edge of the window, R represents the right edge of the window, and sum represents the sum of the elements within the window.

  • L goes from beginning to end to each element in the array, and every time L comes to one of the elements, it tries to expand R to the right, and when R doesn’t expand, the window sizeR-LIs the length of the oldest array starting with the element, and less than or equal to AIM.
  • L starts at the first element, R starts at the first element,sum=0.
  • The logic for expanding R once to the right is: ifsum + min_sum[L] <= aimPhi, then R expands to phimin_sum_index[L] + 1Location and updatesum.
  • When R is not expanded, recordR-LL go to the next element and updatesum.
  • If L comes to an element,sum > aim, indicating the length of the oldest array starting with the element, and less than or equal to AIM, compared to the current window sizeR-LSmaller, then the subarray starting with that element is not considered in the correct answer (because the largest window formed by the previous element is larger than the largest window formed by the current element, and the former has already been recorded), L goes directly to the next element and updatessum.

Sample code:

public static int lessOrEqualAim(int arr[], int aim) {
    int min_sum[] = new int[arr.length];
    int min_sum_index[] = new int[arr.length];
    min_sum[arr.length-1] = arr[arr.length - 1];
    min_sum_index[arr.length-1] = arr.length - 1;
    for (int i = arr.length - 2; i >= 0; i--) {
        if (min_sum[i + 1] < 0) {
            min_sum[i] = arr[i] + min_sum[i + 1];
            min_sum_index[i] = min_sum_index[i + 1];
        } else{ min_sum[i] = arr[i]; min_sum_index[i] = i; }}int R = 0;
    int sum = 0;
    int maxLen = 0;
    for (int L = 0; L < arr.length; L++) {
        while (R < arr.length && sum + min_sum[R] <= aim) {
            sum += min_sum[R];
            R = min_sum_index[R] + 1;
        }
        maxLen = Math.max(maxLen, R - L);
        sum -= R == L ? 0 : arr[L];
        R = Math.max(R, L + 1);
    }
    return maxLen;
}

public static void main(String[] args) {
    int arr[] = {1.2.3.2, -1, -1.1.1, -1, -1.9};
    System.out.println(lessOrEqualAim(arr,3));/ / 8
}
Copy the code

Line 19-27 is the difficulty of implementation. First of all, line 19 shows that L comes to every element in the array from beginning to end. Then, while 20-23 tries to expand R until it stops expanding. Finally, before entering the next for loop and moving L one step to the right, sum is updated in two ways:

  1. 29thewhileCarried out,RIt’s blown out, sosumI can just subtract the current entry in L.
  2. 29thewhileIt wasn’t implemented at all,RNot even one step out and sumLIn the same position, that is, there are no elements in the window at the moment (the window contains elements from L to R only if R>L),sum=0L and R should go to the next element at the same time,sumIt’s still 0, sosumDon’t have to subtractarr[L]Subtraction is required only if the L shift to the right causes an element to go out of the windowarr[L]).

The last 26 lines are also just to make sure that if L doesn’t expand out all the way to the right, then if L moves right up to R and R doesn’t expand out, then R should move right at the same time as L.

The key to achieving O(N) time complexity with this approach is to discard invalid cases. For example, if sum > AIM is found after L moves one step right to update sum, it is obvious that the oldest array starting with L, and whose sum is less than or equal to AIM must be less than the current r-L, while R-(L-1) is recorded in the previous step, and the subarray that meets the condition starting with L can be ignored (because it must be less than R-(L-1)). You don’t have to go back to the current L to expand R.

So L and R both move to the right without going back, so the time complexity is just going through the array.

Joseph’s problem for circular singly linked lists

Josephus, the famous Jewish historian, is said to have told the following story: After the Roman occupation of Joe tower pat, 39 jews and Josephus and his friend hiding in a hole, 39 decided jews would rather die don’t was caught by the enemy, then made a suicide, 41 people arranged in a circle, start from 1 individual number off, a count to three people committed suicide, and then the next person to submit them to 1, Those who count to three commit suicide, and so on, until the last person is left, free to choose their own fate. This is known as Joseph’s problem. Now describe the structure with a one-way circular linked list and show the entire suicide process.

Input: the head node of a circular unidirectional list and the value m of the count.

Return: the last surviving node, and this node itself forms a circular one-way list, other nodes are deleted.

Advanced: If the number of linked list nodes is N and the time complexity is O(N), how to achieve the requirements of the original problem?

Violent method: start counting from the beginning node, count from 1 to m, delete nodes when count to M, and then start counting from the next node…… So (n-1) nodes need to be deleted and m numbers need to be counted before each deletion, so the time complexity is O(NxM).

Here’s an O(N) method.

Let’s start with a function:

If starting from the head node, number each node 1, 2, 3… For example, a circular list with three nodes kills each time the count reaches seven:

Node number Count off
1 1
2 2
3 3
1 4
2 5
3 6
1 kill

So before killing, there is the following corresponding relationship between the node number and the number of nodes (x axis represents where the number of nodes is reported at the moment, y axis corresponds to the number of nodes reported, and N is the number of nodes) :

Suppose that after each killing, the node is renumbered and counted again from the next node. For example, if the circular linked list has 9 nodes and counts to 7, the node will be killed. Then the old number of the node before the killing and the new number of the node after the killing are related as follows:

The old number The new number
1 3
2 4
3 5
4 6
5 7
6 8
7 Killed, renumbered from the next node
8 1
9 2

If the number of nodes in the linked list is N and counts to m, then the corresponding relationship between the old and new numbers of nodes is as follows (s is the number of nodes with counts to M) :

This graph can also be obtained by shifting the basic function y = (x-1) % n + 1 s units to the left:

So y is equal to x minus 1 plus s times % n plus 1.

Now we have the following two formulas:

  1. Node number = (-1) % n + 1
  2. Old number = (new number -1 + S) % n +1, includingsIs the number of the node whose number is m

From formula 1, s = (m – 1) % n + 1, substitute in formula 2 to get

  1. Old number = (new number -1 + (M-1) % n + 1) % n + 1 = (new number + M-1) % n + 1, includingmandnDepends on the input parameter.

Now that we have equation 3, we can figure out the old number of a node given the new number of a node after the other node was killed. In other words, if you kill n-1 node, and only one node is left after you kill it, renumbered the chosen node must be number 1, then the number of the n-1 killed node before it is killed can be calculated by equation 3, With this result, we can get the number of the chosen node before the n-2nd node is killed… We can then find the node from the input linked list, point the subsequent pointer directly to ourselves and then return.

Sample code:

static class Node {
    char data;
    Node next;

    public Node(char data) {
        this.data = data; }}public static Node aliveNode(Node head, int m) {
    if (head == null) {
        return null;
    }
    int tmp = 1;
    Node cur = head.next;
    while(cur ! = head) { tmp++; cur = cur.next; }// There are two nodes left before the n-1 kill, after which the new number of the optional node is 1
    // Call getAlive recursively to deduce the number of the selected nodes when all the nodes are alive
    int nodeNumber = getAlive(1, m, 2, tmp);

    cur = head;
    tmp = 1;
    while(tmp ! = nodeNumber) { cur = cur.next; tmp++; } cur.next = cur;return cur;
}

/** * old number = (new number + m - 1) % n + 1 **@paramNewNumber indicates the newNumber *@param m
     * @paramN Number of surviving nodes corresponding to the old number *@paramLen total number of nodes *@return* /
public static int getAlive(int newNumber, int m, int n, int len) {
    if (n == len) {
        return (newNumber + m - 1) % n + 1;
    }
    // Calculate the old number corresponding to the new number and use the old number as the new number for the next calculation
    return getAlive((newNumber + m - 1) % n + 1, m, n + 1, len);
}

public static void main(String[] args) {
    Node head = new Node('a');
    head.next = new Node('b');
    head.next.next = new Node('c');
    head.next.next.next = new Node('d');
    head.next.next.next.next = new Node('e');
    head.next.next.next.next.next = head;

    System.out.println(aliveNode(head, 3).data);//d
}
Copy the code

Classic structure

Window maximum update structure

Maximum update structure

When put to the structure of the data to check the structure of the existing data, starting from the timestamps of the largest check, if in the process of inspection found that the data is less than the add data will pop up and check its next, until the data is in less than is checking data or data in a structure are popping up, The data to be put into the structure is then time-stamped. Each time data is fetched from the structure, it returns the data with the smallest timestamp in the structure, which is also the largest of all data that has entered the structure so far.

This structure can be implemented using a double-ended queue, with one end used only to store data (other data may pop up during the check process) and the other end used to retrieve the maximum value that has occurred so far.

The following is an example:

package top.zhenganwen.structure;

import java.util.LinkedList;

public class MaxValueWindow {

  private LinkedList<Integer> queue;
  public MaxValueWindow(a) {
    this.queue = new LinkedList();
  }

  // Update window maximum
  public void add(int i){
    while(! queue.isEmpty() && queue.getLast() <= i) { queue.pollLast(); } queue.add(i); }// Get the maximum window value
  public int getMax(a) {
    if(! queue.isEmpty()) {return queue.peek();
    }
    return Integer.MIN_VALUE;
  }

  // Expire the maximum window value
  public void expireMaxValue(a) {
    if (!queue.isEmpty()) {
      queue.poll();
    }
  }

  public static void main(String[] args) {
    MaxValueWindow window = new MaxValueWindow();
    window.add(6);
    window.add(4);
    window.add(9);
    window.add(8);
    System.out.println(window.getMax());/ / 9
    window.expireMaxValue();
    System.out.println(window.getMax());/ / 8}}Copy the code

sample

Windows mobile

Given an array of integers of length N and a window of size W, use an array of length N-w +1 to record the maximum value in the window as it moves from left to right.

For array [1,2,3,4,5,6,7] and window size 3, when the window moves from left to right:

  • [1,2,3],4,5,6,7When the window starts with a subscript of 0, the number boxed is1, 2, 3The maximum is 3
  • 1, [4] 2, 5, 6The maximum is 4
  • 1, 2, three, four, five, six or sevenThe maximum is 5
  • …

So the array is [3,4,5,6,7].

The window maximum update structure has the property that the number previously placed must be larger than the number later placed if it still exists in the structure. The process of moving the window is the process of subtracting a number from the window and adding a number. Take [1,2,3],4 to 1,[2,3,4] this process analysis: first,[1,2,3],4 state window should only have a value of 3 (because 1 was added first, before adding 2 pop up 1, before adding 3 pop up 2); The process of changing to 1,[2,3,4] is the process of subtracting 1 and adding 4 to the window. Since there is no 1 in the window, add 4 directly (3 in the pop-up window, add 4).

Code examples:

public static void add(int arr[], int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  while(! queue.isEmpty() && arr[queue.getLast()] < arr[index]) { queue.pollLast(); } queue.add(index); }public static void expireIndex(int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  if (!queue.isEmpty() && queue.peek() == index) {
    queue.pollFirst();
  }
}

public static int[] maxValues(int[] arr, int w) {
  int[] res = new int[arr.length - w + 1];
  LinkedList<Integer> queue = new LinkedList();
  for (int i = 0; i < w; i++) {
    add(arr, i, queue);
  }
  for (int i = 0; i < res.length; i++) {
    res[i] = queue.peek();
    if (i + w <= arr.length - 1) { expireIndex(i, queue); add(arr, i + w, queue); }}for (int i = 0; i < res.length; i++) {
    res[i] = arr[res[i]];
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {3.2.1.5.6.2.7.8.10.6};
  System.out.println(Arrays.toString(maxValues(arr,3)));//[3, 5, 6, 6, 7, 8, 10, 10]
}
Copy the code

Note here that the add and EXPIRE methods of the window maximum update structure have been improved for this problem (the structure stores the subscripts corresponding to the values). For example,[2,1],-1->2,[1,2,-1] should be translated as [2,1]. When the maximum value of window in -1 state is 2, the number 2 with subscript 2 should be translated as the number with subscript 0 expires from the window. Data 2 should not be out of date from the window (this would mistakenly delete the maximum subscript 2 in the window).

Find the number of subarrays that meet the criteria

Given an array of integers, determine the number of subarrays in which the difference between the maximum and minimum values does not exceed num. (A subarray is an array of elements with consecutive subscripts.)

Violent solution: Iterate over each element, iterate over all subarrays starting with the current element, iterate over the subarrays again to find the maximum and minimum values to determine whether they meet the criteria. The time complexity of this method is obviously O(N ^3), but o(N) level solutions can be achieved if the maximum update structure is used.

If we use two Pointers to an array, L and R, and L is to the left of R. When the subarray L~R meets the standard, it can be deduced that all subarrays starting with L whose length does not exceed r-L +1 meet the standard. When the subarray L~R does not meet the standard, L~R does not meet the standard no matter how many positions L expands to the left or R expands to the right.

The corresponding algorithm of O(N) is: L and R are starting from 0, R to the right first, R for each position moves to the right will use the maximum update structure and the minimum update records the L ~ R structure between the maximum and the minimum of the subscript, when R move to the right if another position L ~ R is not up to standard when to stop, then begin with the current L does not exceed the length of R – L + 1 subarray are up to standard; If L~R is not up to the standard if L~R is up to the standard stop (every right shift R also updates the maximum and minimum value update structure)…… ; Until L reaches the end of the array. The sum of the number of r-L +1 each time R stops is the solution of O(N), because L and R only move to the right, and every time R stops, the number of qualified substrings starting with L is directly calculated by R-L+1, so the time complexity is that the array is traversed once, namely O(N).

Sample code:

public static int getComplianceChildArr(int arr[], int num) {
  // Maximum and minimum update structures
  LinkedList<Integer> maxq = new LinkedList();
  LinkedList<Integer> minq = new LinkedList<>();
  int L = 0;
  int R = 0;
  maxq.add(0);
  minq.add(0);
  int res = 0;
  while (L < arr.length) {
    while (R < arr.length - 1) {
      while(! maxq.isEmpty() && arr[maxq.getLast()] <= arr[R +1]) {
        maxq.pollLast();
      }
      maxq.add(R + 1);
      while(! minq.isEmpty() && arr[minq.getLast()] >= arr[R +1]) {
        minq.pollLast();
      }
      minq.add(R + 1);
      if (arr[maxq.peekFirst()] - arr[minq.peekFirst()] > num) {
        break;
      }
      R++;
    }
    res += (R - L + 1);
    if (maxq.peekFirst() == L) {
      maxq.pollFirst();
    }
    if (minq.peekFirst() == L) {
      minq.pollFirst();
    }
    L++;
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {1.2.3.5};
  System.out.println(getComplianceChildArr(arr, 3));/ / 9
}
Copy the code