猿创征文 |【算法入门必刷】数据结构-栈（五）

📦个人主页：一二三o-0-O的博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨‍💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer
📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，求职就业一战解决】
🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路

【算法入门必刷】数据结构-栈篇系列文章：
【算法入门必刷】数据结构-栈（一）
【算法入门必刷】数据结构-栈（二）
【算法入门必刷】数据结构-栈（三）
【算法入门必刷】数据结构-栈（四）
【算法入门必刷】数据结构-栈（五）
【算法入门必刷】数据结构-栈（六）

前言

开启刷题，请点击右边链接进行跳转点击这里

算法入门刷题训练

AB5：点击消除

题目分析

描述
牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？

根据题目描述，本题是典型的栈的应用。维护一个辅助栈，遍历字符串，在当前栈非空的前提下，判断即将遍历的字符是否与栈顶元素相等，如果相等则进行消除，继续遍历。不相等则直接入栈，最后栈中剩余的元素就是最终形态，返回即可。

理论准备

首先我们要掌握stack的一些基础操作：

-----将元素入栈-----
std::stack mystack;
// 依次将元素1-10入栈
for (int i=1;i<=10;i++) mystack.push(i);

-----判断stack是否为空-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 如果栈不为空，进入循环
while (!mystack.empty())
{
}

----获取stack中元素数量-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 获取数量
int size = mystack.size();

-----获取栈顶元素-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 获取栈顶元素
int topNum = mystack.top();

-----弹出栈顶元素-----
std::stack mystack;
int sum (0);
for (int i=1;i<=10;i++) mystack.push(i);
while (!mystack.empty())
{
sum += mystack.top();
// 弹出栈顶元素
mystack.pop();
}
std::cout << "total: " << sum << ‘\n’;

题解

具体的解决方案如下：

1. 声明辅助栈

// 输入字符串
string s;
cin >> s;
// 声明辅助栈
int n = s.size();
stack<char> st;
1
2
3
4
5
6

2. 遍历字符串，当栈顶元素与当前元素相等时则进行消除

// 遍历字符串
for(int i{};i<n;++i){
	// 如果当前栈为空 and 当前元素与栈顶元素相等
    if(!st.empty() && st.top() == s[i]){
    	// 进行消除
        st.pop();
    }else{// 否则将当前元素入栈
        st.push(s[i]);
    }
}
1
2
3
4
5
6
7
8
9
10

3. 最后返回消除完成后最后剩余的字符串

// 如果栈为空，则返回0
if(st.empty()){
    cout << 0 << endl;
}else{
	// 否则根据栈中的元素返回最后剩余的字符串
    string ans;
    while(!st.empty()){
        ans = st.top() + ans;
        st.pop();
    }

    cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 完整代码如下：

#include 
#include 
#include 
using namespace std;

int main() {
    string s;
    cin >> s;

    int n = s.size();
    stack<char> st;
    
    for(int i{};i<n;++i){
        if(!st.empty() && st.top() == s[i]){
            st.pop();
        }else{
            st.push(s[i]);
        }
    }
    
    if(st.empty()){
        cout << 0 << endl;
    }else{
        string ans;
        while(!st.empty()){
            ans = st.top() + ans;
            st.pop();
        }

        cout << ans << endl;
    }
    
    
    return 0;
}
// 64 位输出请用 printf("%lld")
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

当提交成功后，会展示如下界面，那么恭喜这道题目就通过了！

小结

祝愿所有的伙伴都能拿到自己心仪的Offer！📣伙伴们点击右边链接立刻开启刷题吧：牛客——刷题网