题解 | #吐泡泡#

题目链接

吐泡泡

题目描述

小鱼儿会吐出两种泡泡：大泡泡 O ，小泡泡 o ；两种泡泡的变化规则如下：

任意两个相邻的小泡泡 oo 会融合成一个大泡泡 O。
任意两个相邻的大泡泡 OO 会相互爆炸，变成空白（即消失）。

上述合并与爆炸过程自左至右依次进行，直至无法再进行任何操作。

输入格式 第一行输入一个整数 T 代表数据组数。接下来 T 行，每行一个仅由 'O' 和 'o' 构成的字符串 s。

输出格式 每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

示例

输入:
```
1
ooOOoooO
```
输出:
```
oO
```

解题思路

直接模拟方法中的反复扫描非常耗时。我们可以借鉴"括号匹配"等问题的思想，使用栈（或类似的数据结构，如 std::string 或 StringBuilder 作为栈）来优化这个过程，将时间复杂度降至线性 $\mathcal{O}(L)$ 。

我们将最终生成的稳定字符串看作一个栈。我们从左到右遍历输入字符串的每一个字符，并尝试将其"压入"这个结果栈。在压入时，我们检查栈顶元素是否能与当前字符发生反应。

核心逻辑：

当一个新字符到来时，它只可能与结果字符串的最后一个字符发生反应。
oo -> O 的反应比较特殊：两个 o 合并成一个 O 后，这个新生成的 O 可能会与结果字符串中更早的字符（即新的最后一个字符）再次发生反应（例如 OO -> ""）。这构成了一个连锁反应。

算法步骤：

初始化一个空的结果容器（例如 std::string res），我们将它当作栈来使用。
遍历输入字符串 s 中的每一个字符 c。
对于每个字符 c，我们用一个循环来处理它和栈顶的连锁反应： a. 开始处理 c: b. 如果栈是空的，直接将 c压入栈，然后结束对 c 的处理（跳出连锁反应循环）。 c. 如果栈不为空，取出栈顶字符 top。 d. 判断反应： - 如果 top == 'o' 且 c == 'o'：两个小泡泡相遇。它们合并成一个大泡泡 O。我们弹出栈顶的 'o'，然后将待处理的字符 c 更新为 'O'，继续连锁反应循环，用这个新的 'O' 去和新的栈顶比较。 - 如果 top == 'O' 且 c == 'O'：两个大泡泡相遇。它们爆炸消失。我们弹出栈顶的 'O'，然后结束对 c 的处理（因为没有新泡泡产生，连锁反应中止）。 - 没有反应：如果 top 和 c 不构成上述两种组合，说明它们可以共存。将 c 压入栈，然后结束对 c 的处理。
遍历完所有输入字符后，结果栈中留下的字符串就是最终答案。

代码

cpp
java
python

#include <iostream>
#include <string>

using namespace std;

void solve() {
    string s;
    cin >> s;

    string res = "";
    for (char current_char : s) {
        char char_to_process = current_char;
        while (true) {
            if (res.empty()) {
                res.push_back(char_to_process);
                break;
            }

            char top = res.back();
            if (char_to_process == 'o' && top == 'o') {
                res.pop_back();
                char_to_process = 'O'; // Chain reaction
            } else if (char_to_process == 'O' && top == 'O') {
                res.pop_back();
                break; // Annihilation, end of reaction
            } else {
                res.push_back(char_to_process);
                break; // No reaction
            }
        }
    }
    cout << res << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        while (t-- > 0) {
            String s = sc.nextLine();
            StringBuilder res = new StringBuilder();
            
            for (int i = 0; i < s.length(); i++) {
                char char_to_process = s.charAt(i);
                
                while (true) {
                    if (res.length() == 0) {
                        res.append(char_to_process);
                        break;
                    }
                    
                    char top = res.charAt(res.length() - 1);
                    
                    if (char_to_process == 'o' && top == 'o') {
                        res.deleteCharAt(res.length() - 1);
                        char_to_process = 'O'; // Chain reaction
                    } else if (char_to_process == 'O' && top == 'O') {
                        res.deleteCharAt(res.length() - 1);
                        break; // Annihilation
                    } else {
                        res.append(char_to_process);
                        break; // No reaction
                    }
                }
            }
            System.out.println(res.toString());
        }
    }
}

def solve():
    s = input()
    stack = []
    for char in s:
        char_to_process = char
        while True:
            if not stack:
                stack.append(char_to_process)
                break
            
            top = stack[-1]
            if char_to_process == 'o' and top == 'o':
                stack.pop()
                char_to_process = 'O' # Chain reaction
            elif char_to_process == 'O' and top == 'O':
                stack.pop()
                break # Annihilation
            else:
                stack.append(char_to_process)
                break # No reaction
    
    print("".join(stack))

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法: 基于栈的线性扫描。
时间复杂度: $\mathcal{O}(L)$ ，其中 L 是输入字符串的长度。虽然代码中有嵌套循环，但每个输入字符最多被压入结果一次，每个在结果中的字符也最多被弹岀一次。因此，总操作数与字符串长度成正比。
空间复杂度: $\mathcal{O}(L)$ 。在最坏情况下（例如，字符串为 oOoOoO...），栈的大小将与输入字符串的长度相同。