Nuggets team number online, help you Offer impromptu! Click for details

preface

I came across the problem by accident. Originally wanted to brush one of the five commonly used algorithms – greedy algorithm, with the tag search greedy algorithm, after the point into the discovery is not. But encounter is fate, and the solution of the problem is very like quicksort, so today by the way review quicksort, but also can review the five commonly used algorithms of another – divide-and-conquer algorithm. I think I’ll do a little bit of thinking about greedy algorithms tomorrow.

Topic describes

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

Note: In this case, we define an empty string as a valid palindrome string.

Example 1:

Input: "A man, A plan, A canal: Panama" Output: trueCopy the code

Example 2:

Input: "race a car" Output: falseCopy the code

Source: LeetCode link: leetcode-cn.com/problems/va… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

In this case, it is unavoidable to compare two elements before and after. We can define two cursors one from the beginning of the string and one from the end of the string. The cursor moves to the next character when left meets right. Indicates that all elements before this point are the same. If an unmatched character is encountered before the encounter, the match fails.

You can write pseudocode along these lines:

BEGIN:
    while: left! = right thendo:
        if(left character invalid) then left++; CONTINUE; ENDif;
        if(right character invalid) then right++; CONTINUE; ENDif;
        if(the left character! =right character) BREAK; ENDwhile;
    return left== right;
END
Copy the code

But there is a problem with this. Can left really meet right every time? If the number of valid characters in the input string is odd, it can be encountered. But if the number of valid characters is even, such as AA, left and right match successfully. At this point, left and right move one position each, and they pass each other perfectly. The fact that they pass by each other also means that all strings are matched before they collide, so the true critical condition should be left < right. To tidy up the final code:

class Solution {
    public boolean isPalindrome(String s) {
        String inStr = s.toLowerCase();
        int left = 0, right = inStr.length() - 1;

        while (left < right) {
            if(! Character.isLetterOrDigit(inStr.charAt(left))) { ++left;continue;
            }
            if(! Character.isLetterOrDigit(inStr.charAt(right))) { --right;continue;
            }
            if(inStr.charAt(left) ! = inStr.charAt(right))break;
            ++left;
            --right;
        }
        returnleft >= right; }}Copy the code

This cursor operation is very reminiscent of quicksort. The idea of sorting algorithm is to find a number as a reference number in the sequence to be sorted. So what we need to do is move the elements that are smaller than the base number to the left of the sequence, and move the elements that are larger than the base number to the right of the sequence. Everything on the left must be less than the base number and less than the right. Repeat this for the left and right partitions until they are completely ordered.

Here are 47, 29, 71, 99, 78, 19, 24, 47. The first element is selected as the base value. Define two cursors I and j, move the I cursor forward in turn, find the one smaller than the base number and swap. Then move the cursor J from the left to the right to find the first value greater than the reference value and swap it with the reference value; And then we keep looking until we get to the point where I meets j, where the last reference value is, which is the position of K, which means that the value to the left of K is smaller than the value on k, and the value to the right of K is larger than the value on K.

Therefore, for the above sequence 47, 29, 71, 99, 78, 19, 24 and 47, the ordering of the first exchange in the first trip is as follows, and the operation of the first trip is shown in the figure.

After the swap, J moves to the position of subscript 6 and continues to scan I, as shown in the figure.

At this point, the sequence changed into 24, 29, 47, 99, 78, 19, 71, 47. Next we continue with I and j, as shown in Figure 3, and continue with the comparison of I — and j++.

After these two I and J moves, comparisons and swaps, we finally get the sequence of 24, 29, 19, 47, 78, 99, 71, 47. Then we continue with the operation of I –. We find that when I is 4, it is larger than 47, and we meet j when I is 3. At this point, we do not need to continue to move and compare, we have found k, and the value of k is 3. We can make sure that in the current sequence, all values to the left of k are less than 47, and all values to the right of k are greater than 47 (47 is also to the right of base 47 because we want to keep the relative position constant).

47 is where it should be, so the first sort is done. Next is to take K as the benchmark, divided into two parts, and then perform the above sorting operation on the left and right parts respectively, finally the data will be divided into four parts; Each part is then manipulated until there is only one value for each part.

The sample source: data structure and algorithm tutorial links: data.biancheng.net/view/117.ht…

Fast line of code

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array) {
        this.array = array;
    }
    public void sort(a) {
        quickSort(array, 0, array.length - 1);
    }
    public void print(a) {
        for (int i = 0; i < array.length; i++) { System.out.println(array[i]); }}/** * recursive sort *@param src
     * @param begin
     * @param end
     */
    private void quickSort(int[] src, int begin, int end) {
        if (begin < end) {
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) {
                while (i < j && src[j] > key) {
                    j--;
                }
                if (i < j) {
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] < key) {
                    i++;
                }
                if (i < j) {
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end); }}}Copy the code

conclusion

The essence of sorting algorithm is the idea of divide and conquer, the problem is divided into a small part to solve separately, and then combine the results. This problem forces the quickrow in with a small cursor operation. Although the topic is simple, but can review the divide-and-conquer algorithm, but also consolidate the quick sort, also calculate today has gained it.

This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details.