当前位置：首页 > news >正文

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

news 来源：原创 2024/5/6 19:33:47

【算法入门必刷】数据结构-栈（五）

前言
算法入门刷题训练
- AB5：点击消除
- - 题目分析
  - 理论准备
  - 题解
小结

📦个人主页：一二三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’;

题解

具体的解决方案如下：

声明辅助栈

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

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

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

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

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

    cout << ans << endl;
}

完整代码如下：

#include <iostream>
#include <stack>
#include <string>
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")