题目描述

https://www.nowcoder.com/practice/42852fd7045c442192fa89404ab42e92

题解

暴力法

不推荐，但是能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while(n--) {
        string str;
        cin >> str;
        for (int i = 0; i + 2 < str.size(); i++) {
            if (str[i] == str[i + 1]) {
                if (str[i + 1] == str[i + 2])
                    str.erase(i--, 1);
                else
                    if (i + 3 < str.size() && str[i + 2] == str[i + 3]) 
                        str.erase((i--) + 2, 1);
            }
        }
        cout << str << endl;
    }
    return 0;
}

时间复杂度：O(n2)O(n^2)，因为erase()删除的复杂度是 O(n)。
空间复杂度：O(1)O(1)，除了输入数据，没有用到额外空间。

以下解法均参考：2020字节跳动：万万没想到之聪明的编辑[python][队列][正则][自动机]

队列 + 滑动窗口

以双端队列 deque 作一个滑动窗口，最大大小为 4，如果 deq.size() == 4 且不含要消除的类型，就弹出队首并将其加到结果字符串 res。

deque 相比与 vector 可以更方便的操作队首的元素，而相比于 queue 更是可以通过迭代器取到任意位置的元素，queue 因为先进先出的特性而不提供迭代器。

参考文章中的该解法对于输入 AAAA 的输出结果为 AAA，所以以下解法有改动，答案为 AA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n;
    cin >> n;
    while(n--) {
        string str, res = "";
        deque<char> deq;
        cin >> str;
        for (char ch : str) {
            deq.push_back(ch);
            if (deq.size() == 3 && deq[0] == deq[1] && deq[1] == deq[2]) {  // AAA -> AA
                deq.pop_back();
            }
            if (deq.size() == 4) {
                if (deq[0] == deq[1] && deq[2] == deq[3]        // AABB -> AAB
                 || deq[1] == deq[2] && deq[2] == deq[3]) {     // ABBB -> ABB
                    deq.pop_back();
                } else {
                    res += deq.front();
                    deq.pop_front();
                }
            }
        }
        for (char ch : deq) res += ch;
        cout << res << endl;
    }
    return 0;
}

时间复杂度：O(n)O(n)，对 deque 的增删操作都是 O(1)。
空间复杂度：O(n)O(n)，queue 的最大大小为 4，是 O(1)；另外结果字符串 res 为 O(n)。

有限状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        string str, res = "";
        int state = 0;
        char A = '\0', B = '\0';
        cin >> str;
        for (char i : str) {
            res.push_back(i);
            switch(state) {
                case 0:     // None
                    A = i; state = 1;           // A
                break;
                case 1:     // A
                    if (A == i) state = 2;      // AA
                    else A = i;                 // A
                break;
                case 2:     // AA
                    if (A == i) {               // AAA
                        res.pop_back();
                    } else if (B == '\0') {     // AAB
                        B = i; state = 3;
                    }
                break;
                case 3:     // AAB
                    if (B == i) res.pop_back(); // AABB
                    else {                      // AABC
                        state = 1; A = i; B = '\0';
                    }
                break;
            }
        }
        cout << res << endl;
    }
    return 0;
}

时间复杂度：O(n)O(n)，遍历一遍字符串。
空间复杂度：O(n)O(n)，结果字符串 res 为 O(n)。

正则表达式

看起来非常优雅，但是通过样例的运行时间比前面的方法要慢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <regex>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        string str;
        cin >> str;
        str = regex_replace(str, regex("(.)\\1+"), "$1$1");
        str = regex_replace(str, regex("(.)\\1(.)\\2"), "$1$1$2");
        cout << str << endl;
    }
    return 0;
}