这道题明明很简单的,我却被牛牛难得一见的多组输入卡到自闭,一度怀疑自己是不是sb
题目
题目描述:
小鱼儿吐泡泡,嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡:大泡泡"O",小泡泡"o"。
小鱼儿吐泡泡,嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡:大泡泡"O",小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
(是的你没看错,小气泡和大气泡不会产生任何变化的,原因我也不知道。)
例如:ooOOoooO经过一段时间以后会变成oO。
输入描述:
数据有多组,处理到文件结束。
每组输入包含一行仅有'O'与'o'组成的字符串。
每组输入包含一行仅有'O'与'o'组成的字符串。
输出描述:
每组输出仅包含一行,输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。
解析
知识点
这道题就是一道简单的栈操作。
算法解析
- 这道题,我们可以看到,是相邻的两个都是小泡泡就要变成大泡泡,都是大泡泡就要删除。
- 有过题目经验的我,一看就知道的关于栈的题目:因为题目如果从前往后操作,可以逐个进行判断。
- 栗子:先入栈o,然后入栈o,发现都是小泡泡,然后合成为大泡泡,并且这个大泡泡前面没有大泡泡,所以将O入栈。然后入栈O,就爆炸了,无入栈。
操作分析
- 从前往后遍历栈,我们就是碰到相同即操作,不同即进栈就行了(同上面例子)。
- 操作咋的操作?首先我们就判断一波是不是空栈,是空的就没啥可以比较的了呀,就入栈跳过呗:
if (st.empty()) { st.push(ch); continue; }
- 如果不是,我们就把当前的值取出来做个比较,如果都是小泡泡就合成大泡泡,如果都是大泡泡就炸掉:
while (ch == top) { if ('o' == ch) { st.pop(); ch = 'O'; } else { st.pop(); flag = 1; break; } if (st.empty()) break; top = st.top(); } if (!flag) st.push(ch); }
这里合并ch为'O'用于判断前面还有没有大泡泡可以炸掉。最后判断时除了如果不是炸掉的话就入栈呗(包括变成了大泡泡时前面为空和前面是小泡泡)。 - 最后栈倒过来一下再输出就好了。
打代码
- 首先输入,多组输入搞死我,我没看到,我说怎么只过了40%。
- 然后就对数组每一位进行个遍历了。从前往后。
- 接下来按照我讲的栈操作进行操作。
- 看完代码咯~
AC代码
#include <iostream> #include <stack> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 stack<char> st, tmp; //全局变量区 int main() { IOS; string s; while (cin >> s) { int len = s.length(); for (int i = 0; i < len; i++) { char ch = s[i]; if (st.empty()) { st.push(ch); continue; } char top = st.top(); bool flag = 0;//表示不是炸裂开的 while (ch == top) { if ('o' == ch) { st.pop(); ch = 'O'; } else { st.pop(); flag = 1; break; } if (st.empty()) break; top = st.top(); } if (!flag) st.push(ch); } while (!st.empty()) { tmp.push(st.top()); st.pop(); } while (!tmp.empty()) { cout << tmp.top(); tmp.pop(); } cout << endl; } return 0; } //函数区