栈经典题目(C++)


前言

一、删除字符串中的所有相邻重复项

1.题目解析

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:
输入:“abbaca”
输出:“ca”
解释:
例如,在 “abbaca” 中,我们可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”。

提示:
1 <= S.length <= 20000
S 仅由小写英文字母组成。

2.算法原理

我们本道题目可以通过模拟栈来完成操作。

以abbaca为例子。
如果栈顶元素和这个元素相同,我们就pop.否则我们就插入元素。
最终栈里面从顶到底剩下ac,我们还需要依次取出来,放到string中,再对这个string进行继续操作。

我们可以用数组模拟实现一个栈
在数组尾部插入删除,实现栈的进栈出栈。最后数组存留的内容,就是最后结果

3.代码编写

class Solution {
public:
    string removeDuplicates(string s) 
    {
        string ret="";
        for(auto&e:s)
        {    //首先判断是否有元素
            if(ret.size()&&ret.back()==e)
            {
                ret.pop_back();
            }
            else
            {
                ret+=e;
            }
        }
        return ret;

    }
};

二、 基本计算器 II

1.题目解析

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。

示例 1:
输入:s = “3+2*2”
输出:7

示例 2:
输入:s = " 3/2 "
输出:1

示例 3:
输入:s = " 3+5 / 2 "
输出:5

提示:
1 <= s.length <= 3 * 105
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成,中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

2.算法原理

我们遇到这种计算之类的问题,都需要用栈来解决。

我们以(4-3+6*4/2-123+34)为例子,画图理解一下。
大思路:把带有乘除的看作一项,计算出来,根据运算符进行入栈,最后进行相加

根据规则,先算乘除,再算加减。
我们用op表示遍历前面最近的运算符。
op初始化为 ‘+’

🌟 遍历到整数,如果op是+,把这个数直接入栈。
在这里插入图片描述

🌟 遇到符号对op进行更新
在这里插入图片描述

🌟 遇到操作数,如果op为减号,负的tmp入栈(方便我们就行统一进行加计算)
在这里插入图片描述

🌟 遇到操作符更新op

在这里插入图片描述

🌟 操作数入栈

在这里插入图片描述

🌟 op更新
在这里插入图片描述

🌟 遇到操作数,如果op为乘,让栈顶元素乘这个数。

在这里插入图片描述

🌟 遇到操作符更新op

在这里插入图片描述

🌟 遇到操作数,如果op为除,就让栈顶元素除以这个值。

在这里插入图片描述🌟后面也是同样的道理

总结:
遇到操作符,更改op。
遇到操作数,先把这个值tmp提取出来,按照运算符进行操作。
💖 如果是加号,tmp直接入栈
💖 如果是减号,-tmp入栈
💖 如果是乘号,栈顶元素*tmp
💖 如果是除号,栈顶元素除tmp

我们本道题目直接就可以用一个栈解决,因为我们知道运算规则。本道题也可以用双栈解决。

3.代码编写

class Solution {
public:
    int calculate(string s) 
    {
        stack<int>st;
        char op='+';
        int n=s.size();
        int i=0;
        while(i<n)
        {
            //空格
            if(s[i]==' ')
            {
                i++;
            }
            //数字
            else if(s[i]>='0'&&s[i]<='9')
            {
                //先提取
                int tmp=0;
                while(i<n&&s[i]>='0'&&s[i]<='9')
                {
                    //可能会越界,加个括号
                    tmp=tmp*10+(s[i]-'0');
                    i++;
                }
                //判断运算符
                if(op=='+')
                {
                    st.push(tmp);
                }
                else if(op=='-')
                {
                    st.push(-tmp);
                }
                else if(op=='*')
                {
                    st.top()*=tmp;
                }
                else  if(op=='/')
                {
                    st.top()/=tmp;
                }
                else 
                {
                    assert(false);
                }
            }
            //运算符
            else
            {
                op=s[i];
                i++;
            }
        }
        int sum=0;
        while(st.size())
        {
            sum+=st.top();
            st.pop();
        }
        return sum;
    }
};

三、字符串解码

1.题目解析

给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例 1:
输入:s = “3[a]2[bc]”
输出:“aaabcbc”

示例 2:
输入:s = “3[a2[c]]”
输出:“accaccacc”

示例 3:
输入:s = “2[abc]3[cd]ef”
输出:“abcabccdcdcdef”

示例 4:
输入:s = “abc3[cd]xyz”
输出:“abccdcdcdxyz”

提示:
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]

我们解码时从内到外进行解码。

2.算法原理

本道题与之前做过的括号匹配十分类似,我们可以考虑用栈解决。

我们以(1【a2【bc】】de3【f】)为例子,模拟一下操作。

本道题木需要用两个栈进行解决,一个存放字符,一个存放个数

🌟 遇到数字,把它取出来,放到int栈中。

在这里插入图片描述

🌟 遇到左括号,把左括号后面的字母取出来放到string栈中

在这里插入图片描述

🌟 遇到数字,把它取出来,放到int栈中。

在这里插入图片描述

🌟 遇到左括号,把左括号后面的字母取出来放到string栈中

在这里插入图片描述

🌟 遇到右括号,取string栈和int栈顶元素,进行解码,放到栈顶元素的后面

在这里插入图片描述

🌟 遇到右括号,取string栈和int栈顶元素,进行解码,放到string栈顶元素的后面

在这里插入图片描述

🌟 如果我们直接遇到字母,把字母取出来,放到string栈顶元素的后面

在这里插入图片描述

🌟 遇到数字,把它取出来,放到int栈中。

在这里插入图片描述

🌟 遇到左括号,把左括号后面的字母取出来放到string栈中

在这里插入图片描述

🌟 遇到右括号,取string栈和int栈顶元素,进行解码,放到string栈顶元素的后面

在这里插入图片描述

总结:
遇到数字,把它取出来,放入int栈
遇到左括号,把左括号后买你字母取出来,放到string栈
遇到右括号,取两个栈栈顶,进行解码。放入栈顶元素的后面。
遇到字母,取出来,直接放入栈顶元素后面
遍历完毕之后,string栈栈顶元素就是我们所求结果。

优化:我们可以一开始直接在string栈中放入空串,就可以避免string栈为空,取栈顶进行判断

3.代码编写

class Solution {
public:
    string decodeString(string s) 
    {
        stack<int>ist;
        stack<string>sst;
        int n=s.size();
        int i=0;
        //加这个可以避免string为空,进行判断
        sst.push("");
        while(i<n)
        {
            cout<<s[i]<<endl;
            //数字,取出来,入int栈
            if(s[i]>='0'&&s[i]<='9')
            {
                int tmp=0;
                while(i<n&&s[i]>='0'&&s[i]<='9')
                {
                   tmp=tmp*10+(s[i]-'0');
                   i++;
                }
                ist.push(tmp);
            }
            //左括号,取左括号后买你的字母入栈
            else if(s[i]=='[')
            {
                string tmp;
                i++;
                while(i<n&&s[i]>='a'&&s[i]<='z')
                {
                  tmp+=s[i];
                   i++;
                }
                sst.push(tmp);
            }
            //右括号,取两个栈栈顶,进行解码
            else if(s[i]==']')
            {
                i++;
                string s1=sst.top();
                for(int j=1;j<ist.top();j++)
                {
                    s1+=sst.top();
                }
                sst.pop();
                ist.pop();
                sst.top()+=s1;    
            }
            //字母
            else
            {
                string tmp;
                while(i<n&&s[i]>='a'&&s[i]<='z')
                {
                   tmp+=s[i];
                   i++;
                }
                sst.top()+=tmp;
 
            }
        }
        return sst.top();
    }
};

四、验证栈序列

1.题目解析

给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

示例 1:
输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:
输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

提示:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

2.算法原理

通过栈来解决,一直让元素进栈,进站同时判断是否需要出栈。所有元素模拟完毕之后,如果栈中还有元素,那
么就是⼀个⾮法的序列。

3.代码编写

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        //一直让元素进栈,进栈同时判断是否需要出栈。
        stack<int>st;
        int i=0;//遍历popped
        for(auto&e:pushed)
        {
            //进栈
            st.push(e);
            //出栈
            while(st.size()&&st.top()==popped[i])
            {
                i++;
                st.pop();
            }
        }
        //如果栈为空,说明合法
        if(st.empty())
        {
            return true;
        }
        else
        {
            return false;
        }

    }
};

总结

以上就是今天要讲的内容。希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

相关推荐

  1. C++经典面试题目(三)

    2024-06-09 12:50:02       16 阅读
  2. C++经典面试题目(四)

    2024-06-09 12:50:02       9 阅读
  3. C++经典面试题目(六)

    2024-06-09 12:50:02       11 阅读
  4. C++经典面试题目(七)

    2024-06-09 12:50:02       13 阅读
  5. C++经典面试题目(八)

    2024-06-09 12:50:02       15 阅读
  6. C++经典面试题目(九)

    2024-06-09 12:50:02       14 阅读

最近更新

  1. 数据分离(C++)

    2024-06-09 12:50:02       0 阅读
  2. Jira系统基本介绍

    2024-06-09 12:50:02       0 阅读
  3. 深入解析Spring Cloud:微服务架构的利器(下)

    2024-06-09 12:50:02       0 阅读
  4. Adam优化算法

    2024-06-09 12:50:02       0 阅读
  5. K-MEANS 算法的简单实现

    2024-06-09 12:50:02       0 阅读
  6. String结构体测试代码(一)

    2024-06-09 12:50:02       0 阅读

热门阅读

  1. React——组件通信方式

    2024-06-09 12:50:02       5 阅读
  2. 我对Chat-GPT4o的使用感受

    2024-06-09 12:50:02       4 阅读
  3. 【C#】延时关闭电脑、取消关闭电脑

    2024-06-09 12:50:02       5 阅读
  4. 方法调研:DDOS检测有哪些方法?

    2024-06-09 12:50:02       4 阅读
  5. Rust 编程——prost-build 使用

    2024-06-09 12:50:02       6 阅读
  6. 速盾:ddos防护与高防ip区别?

    2024-06-09 12:50:02       5 阅读
  7. 贪心算法详解

    2024-06-09 12:50:02       5 阅读
  8. 自然语言处理(NLP)—— rasa的测试

    2024-06-09 12:50:02       4 阅读
  9. 支持向量机(SVM): 从理论到实践的指南(1)

    2024-06-09 12:50:02       4 阅读
  10. Web前端Text:深入解析与实践应用

    2024-06-09 12:50:02       5 阅读
  11. 多关键字排序

    2024-06-09 12:50:02       5 阅读
  12. opencv

    opencv

    2024-06-09 12:50:02      5 阅读
  13. HTML5表单元素:重塑数据收集的艺术

    2024-06-09 12:50:02       3 阅读