Description:
小鱼儿吐泡泡,嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡:大泡泡"O",小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。(是的你没看错,小气泡和大气泡不会产生任何变化的,原因我也不知道。)
例如:ooOOoooO经过一段时间以后会变成oO。
Input:
数据有多组,处理到文件结束。
每组输入包含一行仅有’O’与’o’组成的字符串。
Output:
每组输出仅包含一行,输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。
Sample Input:
ooOOoooO
Sample Output:
oO
题目链接
我在做这道题的时候第一想法就是先用string字符串读取数据装入vector然后一遍遍地从左至右遍历vector,遇到两个"o"就把第一个"o"改为"O"然后删掉第二个"o",接着从头开始遍历,如果遇到两个"O"就把两个"O"都删掉,接着从头开始遍历,直到无法再更改为止。
AC代码:
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main() {
// 加速输入输出
ios::sync_with_stdio(0);
cin.tie(0);
// string字符串获取一行泡泡
string str;
// 建立一个字符格式容器用来处理获取泡泡
vector<char> vec;
while (getline(cin,str)) { // 获取一行泡泡
// len代表此次获得泡泡总数量
int len = str.length();
// 将每个泡泡按照从左至有的顺序压入vec容器中
for (int i = 0;i < len;++i) {
vec.push_back(str[i]);
}
// 不断循环合并泡泡直到无法再合并
while (1) {
emm:;
// 如果已生成泡泡序列已经没有泡泡,则打破循环
if (vec.size() == 0) {
break;
}
// flag变量用来判断此次循环是否有泡泡合并
int flag = 0;
// 从左至有循环寻找可以合并的泡泡
for (int i = 0;i < vec.size() - 1;++i) {
if (vec[i] == vec[i + 1]) { // 如果有两个相邻泡泡想用便可以合并
if (vec[i] == 'o') { // 如果是两个o则合并为一个O
vec[i] = 'O'; // 将两个o中的第一个o改为O
vec.erase(vec.begin() + i + 1); // 删除两个o中的第二个O
goto emm; // 返回再次从头开始循环
flag++; // 将flag标记
}
else if (vec[i] == 'O') { // 如果是两个O则全部删除
vec.erase(vec.begin() + i); // 删除两个泡泡
vec.erase(vec.begin() + i);
goto emm; // 返回再次从头开始循环
flag++; // 将flag标记
}
}
// 如果已生成泡泡序列已经没有泡泡,则打破循环
if (vec.size() == 0) {
break;
}
}
// 如果已生成泡泡序列已经没有泡泡,或者没有此次循环没有进行任何合并则打破循环
if (flag == 0 || vec.size() == 0) {
break;
}
}
// 按照题目要求输出结果
if (vec.size() == 0) {
cout << endl;
continue;
}
for (int i = 0;i < vec.size();++i) {
cout << vec[i];
}
cout << endl;
// 清空容器
vec.clear();
}
return 0;
}
但是后来我看好多人都没有用vector而是用的栈写的这道题,思路是用string字符串读取数据,然后在字符串中从左至右开始遍历,先把第一个元素压入栈顶,然后从第二个元素开始判断如果当前栈不为空且遍历元素和栈顶元素相同且为"o"则取出栈顶元素,并向栈内压入一个"O",如果当前栈不为空且遍历元素和栈顶元素相同且为"O"则取出栈顶元素,否则将当前遍历元素压入栈顶,注意遍历结束之后还要用另一个栈将之前用的栈反向存储一下,最后按照顺序输出。
AC代码:
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
int main() {
// 加速输入输出
ios::sync_with_stdio(0);
cin.tie(0);
// string字符串获取一行泡泡
string s;
while (getline(cin,s)) { // 获取一行泡泡
stack<char> q; // 建立栈处理泡泡
int len = s.length(); // len代表此次获得泡泡总数量
for (int i = 0;i < len;++i) { // 将字符串从左至右遍历循环
if (s[i] == 'o' && !q.empty() && q.top() == 'o') { // 如果此字符为'o'&栈不为空&栈顶为'o'
q.pop(); // 取出栈顶元素
if (!q.empty() && q.top() == 'O') { // 如果栈不为空&栈顶为'O'
q.pop();
// 在取出栈顶元素
}
else {
q.push('O'); // 否则将'O'压入栈顶
}
}
else if (s[i] == 'O' && !q.empty() && q.top() == 'O') { // 如果此字符为'O'&栈不为空&栈顶为'O'
q.pop(); // 取出栈顶元素
}
else {
q.push(s[i]); // 否则压入栈顶
}
}
s = ""; // 将s字符串初始化
stack<char> l; // 建立另一个栈反向
while (!q.empty()) { // 将q栈的栈顶元素赋值给l栈,并依次取出栈顶元素
l.push(q.top());
q.pop();
}
while (!l.empty()) { // 依次输出、取出l栈顶元素
cout << l.top();
l.pop();
}
cout << endl;
}
return 0;
}