吐泡泡算法题

这个题我是第二次才ac 第一遍没想到用栈来”瞻前” 因为是从左到右合嘛 第一遍的只过了百分之四十测试用例
第一次代码:(通过率40%)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

//通过率40%

#include <bits/stdc++.h>
using namespace std;

string s;

int main()
{
while(cin>>s)
{
	//因为有多组数据
	list<char> paopao;
	//把这个字符串存到链表容器里面
	int Length=s.length();
	for(int i=0;i<Length;i++)
	{
	    paopao.push_back(s[i]);
	}
	
	//开始遍历list容器
	//ooOOoooO
	list<char>::iterator p1;
	p1=paopao.begin();
	while(p1!=paopao.end())
	{
		if(*p1=='o')
		{
			//因为是从左到右合并 所以要先看前驱再看后继
			//o不需要看前驱 因为前面是O则没必要 前面不会存在o因为是从左到右遍历，若有小o一定会先结合成O
			
			//看后继
			p1++;
			if(p1==paopao.end()) continue;
			if(*p1=='o')
			{
				//两个o变O
				*p1='O';
				list<char>::iterator p2;
				p2=p1;
				p1--;
				paopao.erase(p1);
				p1=p2;
				continue;
			}
			else if(*p1=='O')
			{
				continue;
			}
		}
		if(*p1=='O')
		{
			//看前驱
			if(p1!=paopao.begin())
			{
				p1--;
				if(*p1=='O')
				{
					list<char>::iterator p2;
					p2=p1;
					p1++;
					paopao.erase(p2);
					p2=p1;
					p1++;
					paopao.erase(p2);
					continue;
				}
				else if(*p1=='o')
				{
					p1++;
					//看了前驱后的看后继
					//如果被删除了 那么也不会运行此段代码
					p1++;
					if(p1==paopao.end()) continue;
					//和后继节点的O抵消
					if(*p1=='O')
					{
						list<char>::iterator p2;
						p2=p1;
						p1--;
						paopao.erase(p1);
						p1=p2;
						p1++;
						paopao.erase(p2);
						continue;
					}
					//后继节点是o
					else if(*p1=='o')
					{
						//把指针指向这个小o然后继续遍历
						continue;
					}
				}
			}
			//看不了前驱后的看后继
			//即p1==paopao.begin()
			else{
				//直接看后继
				p1++;
				if(p1==paopao.end()) continue;
				
				if(*p1=='O')
				{
					list<char>::iterator p2;
					p2=p1;
					p1--;
					paopao.erase(p1);
					p1=p2;
					p1++;
					paopao.erase(p2);
					continue;
				}
				else if(*p1=='o')
				{
					continue;
				}
			}
		}
	}
	for(list<char>::iterator i=paopao.begin();i!=paopao.end();i++)
	{
		cout<<*i;
	}
}

cout<<endl;

return 0;
}

其实可以把栈给利用起来
就是每遍历下一个泡泡 就遍历栈顶的元素 如果是小o就直接变成大O
因为是从左到右合并 所以左边的会自动与右边的合并 这个时候别着急把大O进栈 而是先看栈顶元素
那么此时情况分两种:
1,小o 直接把O进栈
2,大O 两个大O直接爆 直接出栈栈顶元素 目前遍历到的大O也作废了嘛 for循环遍历下一个泡泡
这样做可以满分通过:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
//本题和括号序列匹配本质一致 主要依赖栈的数据结构实现
stack<char> st,tmp;
//ooOOoooO
//栈  ch
//o
//o   o
//O
//O   O
//O
//O   o
//Oo
//Oo  o
//O   O
//    O
//o
//o   O
//oO
int main()
{
    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= false;
            while(top==ch)
            {
                //两个小o变成一个大O 然后入栈
                if(ch=='o')
                {
                    st.pop();
                    ch='O';
                }
                //两个大O
                else
                {
                    //发生爆炸
                    st.pop();
                    flag=true;//表示当前遍历位置ch已经失效 无需在下一次循环之前入栈
                    break;//break掉while循环 ch已无价值 继续进行for循环下一个字符的遍历
                }
                if(st.empty()) break;
                //更新top的值 以继续while循环
                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;
}

[视频内嵌代码]