首页 > 试题广场 >

吐泡泡

[编程题]吐泡泡
  • 热度指数:441 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小鱼儿会吐出两种泡泡:大泡泡 \texttt{,小泡泡 \texttt{;两种泡泡的变化规则如下:
\hspace{23pt}\bullet\,任意两个相邻的小泡泡会融合成一个大泡泡;
\hspace{23pt}\bullet\,任意两个相邻的大泡泡会相互爆炸,变成空白(即消失)。
\hspace{15pt}上述合并与爆炸过程自左至右依次进行,直至无法再进行任何操作。

\hspace{15pt}例如,对于初始泡泡序列 \texttt{,经过一段时间后会变成 \texttt{


输入描述:
\hspace{15pt}第一行输入一个整数 T\left(1\leqq T\leqq 10\right) 代表数据组数。
\hspace{15pt}接下来 T 行,每行一个仅由 'O' 和 'o' 构成的字符串 s,字符串长度不超过 10^5


输出描述:
\hspace{15pt}每组输出仅包含一行,输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。
示例1

输入

1
ooOOoooO

输出

oO

说明


示例2

输入

1
OOOOOOOOOOOOOOOooooooooooooooooooOOoOoOoOOOoOoOoOOoOooOoOOoOoOoOoOoOoOoOoOoOooOoOoOOoooOOOOoOOoooOOoOOOOOooOoOOOoOOoooOoOOOooOooooOoOooOoOooOoOooOoOOOOOOOOOOOOOOoOoOoOooOOoOooOoOOoOoOOOOooooOOOOOooooooOOOOOOoooooOoOooOoOoOoooOoOOOOoOoOoOOOOOOOOOOoOooOoOooOOoOOoOooOooOOoooOOOoOoOooOOooOoOOOoOOoOOOoOooOoOOOooOOoooOOoOOoOooOOOOoOooOoOoOoOooOoOoO

输出

oOoOoOoOoOoO

说明



备注:

class Stack:
    def __init__(self) -> None:
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.is_empty():
            self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

    def peek(self):  # 修正拼写
        if not self.is_empty():
            return self.items[-1]
        return None

def tu_bubbles(bubbles):
    # 初始化栈
    stack = Stack()
    # 遍历泡泡序列
    for bubble in bubbles:
        if bubble == "o":
            if stack.peek() == "o":
                stack.pop()
                if stack.peek() == "O":
                    stack.pop()
                else:
                    stack.push("O")
            else:
                stack.push("o")
        elif bubble == "O":
            if stack.peek() == "O":
                stack.pop()
            else:
                stack.push("O")
    # 输出最终结果
    return "".join(stack.items)

# 读取输入
import sys
n = int(input())
for line in sys.stdin:
    s = line.strip()
    print(tu_bubbles(s))

发表于 2025-06-10 15:13:19 回复(0)

问题信息

上传者:牛客303862号
难度:
1条回答 1380浏览

热门推荐

通过挑战的用户

查看代码
吐泡泡