编程知识 cdmana.com

An algorithm problem of array de duplication can't make Dong Ge whole

After reading this article , You can go and get the following questions :

316. Remove duplicate letters

1081. The smallest sequence of different characters

-----------

About the de duplication algorithm , There should be no difficulty , Just put it in the hash set ?

At best, I'll give you some restrictions , How do you duplicate an ordered array in place , This is our old article How to efficiently give an ordered array / The chain watch is weightless .

The problem that this article talks about should be the most difficult in the algorithm of de duplication correlation , Make sense of the problem , We don't have to worry about array duplication anymore .

It's a force lock 316 topic 「 Remove duplicate letters 」, The title is as follows :

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

This question and No 1081 topic 「 The smallest sequence of different characters 」 The solution is exactly the same , You can paste the solution code of this problem directly 1081 The problem is also eliminated .

The requirements of the topic are summed up in three aspects :

Demand one 、 We need to remove the weight .

Requirement 2 、 Remove the order of characters in a string Don't disturb s The relative order in which characters appear in .

Requirement 3 、 In all de duplicated strings that meet the previous requirement , Dictionary order is the smallest As the end result .

Among the above three requirements , Request three may be a little difficult to understand , for instance .

For example, input string s = "babc", There are two strings that are de duplicated and conform to the relative position , Namely "bac" and "abc", But our algorithm has to go back to "abc", Because it has a smaller lexicographic order .

Logically speaking , If we want orderly results , So you have to sort the original string, right , But after sorting, there is no guarantee of conformity s The Chinese characters appear in order , It seems contradictory .

In fact, we will learn from the previous article Monotonous stack solution framework Talked about 「 Monotonic stack 」 The idea of , It doesn't matter if you haven't seen it , You'll see later .

Let's ignore claim three for the time being , use 「 Stack 」 To fulfill requirements one and two , Why stack , You'll find out later :

String removeDuplicateLetters(String s) {
    //  Store the results of de duplication 
    Stack<Character> stk = new Stack<>();
    //  The initial value of Boolean array is  false, Record whether there is a character in the stack 
    //  The input characters are  ASCII  character , So the size  256  Will be enough 
    boolean[] inStack = new boolean[256];

    for (char c : s.toCharArray()) {
        //  If the characters  c  In stack , Just skip 
        if (inStack[c]) continue;
        //  If it does not exist , Insert into the top of the stack and mark as exist 
        stk.push(c);
        inStack[c] = true;
    }

    StringBuilder sb = new StringBuilder();
    while (!stk.empty()) {
        sb.append(stk.pop());
    }
    //  The insertion order of elements in the stack is reverse , need  reverse  once 
    return sb.reverse().toString();
}

The logic of this code is very simple , It's a Boolean array inStack Record elements in the stack , To achieve the goal of de duplication , At this time, the elements in the stack are not repeated .

If input s = "bcabc", This algorithm will return "bca", Requirements 1 and 2 have been met , But the answer to the question is "abc" Right .

Let's think about it , If you want to meet requirement three , Keep dictionary order , What changes need to be made ?

To the stack stk Insert character in 'a' This moment of , Our algorithm needs to know , character 'a' The dictionary order and the preceding two characters 'b' and 'c' comparison , Who is big or who is small? ?

If the current character 'a' Smaller than the previous character dictionary order , It may be necessary to put the preceding characters pop Out of the stack , Give Way 'a' At the top , Right

that , Let's change a version of the code first :

String removeDuplicateLetters(String s) {
    Stack<Character> stk = new Stack<>();
    boolean[] inStack = new boolean[256];

    for (char c : s.toCharArray()) {
        if (inStack[c]) continue;

        //  Before insertion , Compare the size with the previous elements 
        //  If the dictionary order is smaller than the previous one ,pop  The elements in front 
        while (!stk.isEmpty() && stk.peek() > c) {
            //  Pop up top element , And mark the element as not on the stack 
            inStack[stk.pop()] = false;
        }

        stk.push(c);
        inStack[c] = true;
    }

    StringBuilder sb = new StringBuilder();
    while (!stk.empty()) {
        sb.append(stk.pop());
    }
    return sb.reverse().toString();
}

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

This code is easy to understand , It's the insertion of a while loop , continuity pop A character at the top of the stack that is smaller than the current character , Until the top element of the stack is smaller than the dictionary order of the current element . It's just not a little bit 「 Monotonic stack 」 I'm not sure ?

such , For input s = "bcabc", We can get the right result "abc" 了 .

however , If I change the input , hypothesis s = "bcac", According to the algorithm logic just now , The result is "ac", And the right answer should be "bac", Analyze what's going on ?

It's easy to see , because s Only one of them 'b', Even if the character 'a' The dictionary order of a character is more than that of a character 'b' smaller , character 'b' And it shouldn't be pop get out .

What's the problem ?

Our algorithm is stk.peek() > c when pop Elements , In fact, this time should be divided into two situations

Situation 1 、 If stk.peek() This character will be followed by , Then you can put it pop get out , Anyway, there's more behind , Later push Go to the stack , Just in line with the requirements of the dictionary order .

Situation two 、 If stk.peek() This character doesn't follow , As mentioned above, there will be no duplicate elements in the stack , Then you can't put it pop get out , Or you'll lose the character forever .

go back to s = "bcac" Example , Insert characters 'a' When , Find the preceding character 'c' The dictionary order of 'a' Big , And in 'a' And then there are the characters 'c', So this one at the top of the stack 'c' Will be pop fall .

while The loop continues to judge , Find the preceding character 'b' The dictionary order is still better than 'a' Big , But in 'a' After that, there are no more characters 'b' 了 , So you shouldn't put 'b' pop get out .

So the key is , How to let the algorithm know the character 'a' Then there were a few 'b' There are several 'c' Well

It's not difficult. , Just change another version of the code :

String removeDuplicateLetters(String s) {
    Stack<Character> stk = new Stack<>();

    //  Maintain a counter to record the number of characters in a string 
    //  Because the input is  ASCII  character , size  256  Will be enough 
    int[] count = new int[256];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i)]++;
    }

    boolean[] inStack = new boolean[256];
    for (char c : s.toCharArray()) {
        //  Every time you traverse a character , Subtract the corresponding count by one 
        count[c]--;

        if (inStack[c]) continue;

        while (!stk.isEmpty() && stk.peek() > c) {
            //  If there is no top of stack element after , Then stop  pop
            if (count[stk.peek()] == 0) {
                break;
            }
            //  If there is any more , Then you can  pop
            inStack[stk.pop()] = false;
        }
        stk.push(c);
        inStack[c] = true;
    }

    StringBuilder sb = new StringBuilder();
    while (!stk.empty()) {
        sb.append(stk.pop());
    }
    return sb.reverse().toString();
}

We used a counter count, When smaller characters in the dictionary try to 「 Squeeze out 」 At the top of the stack , stay count Check whether the top element of the stack is unique , Only when there is a stack top element behind it can it be squeezed out , Or you can't squeeze out .

thus , The algorithm is over , Time and space complexity is O(N).

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

Do you remember the three requirements we mentioned at the beginning ? How do we meet these three requirements

Demand one 、 adopt inStack This Boolean array does stack stk There are no repeating elements in .

Requirement 2 、 We iterate through the strings in sequence s, adopt 「 Stack 」 In this order push/pop Operation record result string , It ensures the order in which characters appear and s In the same order .

You can also think of why you should use 「 Stack 」 This data structure , Because the first in, last out structure allows us to immediately manipulate the character we just inserted , If you use 「 queue 」 You can't do it .

Requirement 3 、 We use the idea of a monotonous stack , With the counter count constantly pop Drop characters that do not conform to the minimum lexicographic order , The dictionary order of the final result is minimum .

Of course , Because of the structural characteristics of the stack , Finally, we need to take the elements out of the stack and then reverse it again .

Tell the truth , This should be the highest level of array de duplication , It's not easy to think of it before . Have you learned ?

_____________

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ! Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢

Scroll to Top