【基础算法总结】栈

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

栈并不是很难的数据结构,我们就可以使用数组模拟出来。但是某些问题难就难在看到这道题的时候能不能想到用栈来解决。如果能想到你会发现这些题本质就是借用栈模拟一下就可以了。

1.删除字符串中的所有相邻重复项

题目链接:1047. 删除字符串中的所有相邻重复项

题目描述:

在这里插入图片描述

算法原理:

我们可以把这个字符串看成一个往下坠的字符串,如同消消乐一般。相同的就消掉的。

在这里插入图片描述

这个过程很明显就是栈的应用。

解法:利用栈做一下模拟即可

用栈模拟一下发现最后栈中的元素就是最终答案。
栈空或者栈顶元素和要入栈的元素不一样直接入栈,反过来就出栈,继续下一个。
但是这道题是要我们返回string,这样做还需要把栈中的元素取出来放到string里。

在这里插入图片描述
所以我们可以用string模拟一下栈。

在这里插入图片描述

直接用数组就可以模拟这个栈结构,好处就是:模拟完毕之和,数组里面存的就是最终结果。

class Solution {
public:
    string removeDuplicates(string s) {

        string ret;// 搞一个数组,模拟栈结构即可
        for(int i = 0; i < s.size(); ++i)
            if(!ret.empty() && ret.back() == s[i])  //出栈
                ret.pop_back();
            else
                ret += s[i]; // 入栈

        return ret;
    }
};

2.比较含退格的字符串

题目链接:844. 比较含退格的字符串

题目分析:

在这里插入图片描述

遇到 ‘#’ ,就相当于删除前面的元素。

算法原理:

这道题和上面几乎就是一模一样。

解法:利用栈模拟即可

不是 ‘#’ 就进栈,遇到 ‘#’ ,删除前面的元素,如果栈为空就不能删除。两个字符串经过处理最后比较一下即可。

在这里插入图片描述

class Solution {
public:
    bool backspaceCompare(string s, string t) {

        return changStr(s) == changStr(t);
    }

    string changStr(string& s)
    {
        string ret;
        for(auto& ch : s)
        {
            if(ch != '#') ret += ch;
            else
            {
                if(!ret.empty()) ret.pop_back();
            }
        }
        return ret;
    }
};

3.基本计算器 II

题目链接:227. 基本计算器 II

题目分析:

在这里插入图片描述

s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成,中间由一些空格隔开。也就说里面是没有括号的,没有括号处理起来还是比较容易的。

算法原理:

这道题虽然是一个基本计数器,但是本质是一种类型的题目,表达式求值,解法是统一的。

解法:利用栈来模拟计算过程

有两种通用的解法:
解法一:中缀表达式转成后缀表达式,然后定义一个操作数栈,扫描后缀表达式,遇到操作数就进栈,遇到运算符就出栈顶两个元素,然后将计算结果在压栈,当后缀表达式结束,栈顶就是我们的运算结果。

中缀表达式转成后缀表达式:

初始化一个栈,用于保存暂时还不能确定顺序的运算符。
从左到右处理各个元素,直到末尾,可能遇到三种情况:

  1. 遇到操作数,直接加入后缀表达式
  2. 遇到界限符,遇到 “(” 直接入栈,遇到 “)” 则依次弹出栈内运算符并加入后缀表达式,直到弹出 “(” 为止,注意 “(” 不加入到后缀表达式
  3. 遇到运算符,依次弹出栈中优先级高于或者等于当前运算符的所有运算符,并加入到后缀表达式,若碰到 “(” 或者栈空则停止,之后再把当前运算符入栈
  4. 按上述处理完所有字符后,将剩余运算符依次弹出,并加入到后缀表达式

解法二:中缀表达式直接计算,利用两个栈,其中一个栈用来维护操作数,另一个栈用来维护操作符。

  1. 初始化两个栈,操作数栈和运算符栈
  2. 扫描到操作数,压入操作实栈
  3. 扫描到运算符或者界限符,则按照 “中缀转后缀” 相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素,并执行相应运算,运算结果再压回操作数栈,最后栈顶元素就是最终运算结果)

不过这道题比较简单,只要 + - * - 四个运算符,并且里面只有正数没有负数,而且还没有括号。所以这道题我们可以用更简单的方法来解决的。我们仅需要一个栈和一个变量就可以了。

接下来模拟一下。
int类型的栈用来保存操作数,op用来标记当前数前面的运算符是什么。

在这里插入图片描述
刚开始的时候,把op初始化成一个‘+’,这样的话第一个数和后面的数处理逻辑是一样的。
在这里插入图片描述
接下来遍历这个字符串,当碰到数字的时候,把数字给提取出来,因为这整体是一个字符串。碰到单个数还好说,但是碰到123这种需要把123整体提出来。数字提取出来,然后去看看这个数字前面运算符,当是 ‘+’,‘-’ 的时候,这个数字可能还操作不了,因为后面运算符不知道,一旦后面运算符是 ‘*’ ,‘/’ 这个数字应该先和后面的数先进行运算。所以遇到一个数这个数字前面是 ‘+’,‘-’ 运算符,就把数字丢到栈中。如果是 ‘+’ 数字直接丢到栈中,如果是 ‘-’ 就取这个数字的负数,放入栈中。这样弄的因为是最后可以把栈里未运算的元素取出来都看成 ‘+’ 运算,直接加就可以了。如果这数字前面是 ’ * ’ ,‘/’。就将这个数字直接和栈顶元素进行相应的运算,因为 ’ * ’ ,‘/’ 优先级是最高的在这道题而且这道题并没有括号!

当碰到运算符的时候 直接更新 op。为什么直接更新原因很简单,因为栈里面存的元素如果没有运算的是它前面要么是 ‘+’,要是 ‘-’。而 ’ * ’ ,‘/’ 我们也已经运算过了加入到栈里面了。最后把栈中元素取出来做加法就行了。

在这里插入图片描述
其实这就是一个分情况讨论的过程:

1.遇到操作符:更新操作符 op

2.遇到数字

  1. 先把数字提取出来, tmp
  2. 分情况讨论,根据 op 符号
    op == ‘+’,tmp直接入栈;
    op == ‘-’,-tmp入栈;
    op == ‘*’,直接乘到栈顶元素上;
    op == ‘/’,直接除到栈顶元素上;
class Solution {
public:

    int calculate(string s) {

        vector<int> st;// ⽤数组来模拟栈结构
        char op = '+';
        int i = 0, n = s.size();
        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');
                
                if(op == '+') st.push_back(tmp);
                else if(op == '-') st.push_back(-tmp);
                else if(op == '*') st.back() *= tmp;
                else st.back() /= tmp;
            }
            else
                op = s[i++];
        }
        //取出栈中元素 进行 '+' 运算
        int ret = 0;
        for(auto e : st) ret += e;
        return ret;
    }   
};

4.字符串解码

题目链接:394. 字符串解码

题目分析:

在这里插入图片描述

给一个经过编码的字符串,返回它解码后的字符串。数字后面括号里跟的是要重复几次的字符串。
在这里插入图片描述

算法原理:

如果表达式求值里面有加括号,是由内向外计算。有括号先算括号里面的。这道题解码方式也是由内到外的,因此我们可以使用栈。

在这里插入图片描述

解法:用栈来模拟

比如说拿到这个1的时候,不知道后面跟的是什么东西,不能贸然就去解码,需要先把后面东西解码之后,在重复。因此这个1需要先保存起来。

在这里插入图片描述

当碰到 [ 括号的时候,因为要把后面东西进行解码,因此直接跳过 [ 括号。

在这里插入图片描述

碰到字符串a之后,往后走,也要把这个字符串a保存起来,因为a后面要接一堆字符串的,但是需要解码之后才知道后面接的是什么,因此先把字符串a保存起来。
在这里插入图片描述

当碰到 ] 括号的时候,前面肯定是有一个 ] 是和我匹配的,所以就可以解码了,拿到前面的最近保存过的字符串bc 和 数字 2 进行解码。

在这里插入图片描述
我们是从前往后扫描的 进行保存的,然后碰到 ] 把最近的字符串和数字拿到。这不正好符号栈 后进先出的吗。

当我们分析用栈来解决,接下来就是模拟的过程了。

因为字符串既有数字还有字符串,因此需要一个 “数字栈” 、 " 字符串栈"。

当碰到一个数,先把数提取出来,因为并不知道要让我重复谁,所以先放到 数字栈 中
在这里插入图片描述
当遇到 [ , [ 后面一堆东西是需要重复的,但是此时不知道需要重复谁,因此将 [ 后面一小堆字符串提出来先放到 字符串栈 中。
在这里插入图片描述

碰到数字和 [ ,同理都是这样的操作

在这里插入图片描述

碰到 ] 括号,就可以大胆的解析了,解析的时候仅需把两个栈的栈顶元素提出来,然后解析。接下来重点来了,是把解析后的字符串直接丢到字符串栈里面吗?并不是!因为这一堆东西前面可能还连着字符串,所以是把解析后的字符串放到 字符串栈的栈顶元素后面。

在这里插入图片描述

此时右碰到 ] 括号,把两个栈的栈顶元素提出来,然后解析。把解析后的字符串放到 字符串栈的栈顶元素后面。但是此时 字符串栈 是空的,会发生越界的情况。因此 字符串栈,初始化给一个 空字符串。 这样在放回去的时候就不会发生越界了。

在这里插入图片描述
当碰到单独的字符串之后,把字符串提取出来,因为它前面并没有 [ ,因此可以直接该字符串放到栈顶元素后面,因为这个字符串并不需要重复,直接放在前面解析好的字符串后面就可以了。所以把这个字符串放在栈顶元素后面。
在这里插入图片描述
后面的就和前面一样的操作,最终 字符串栈 栈顶元素就是解析后的字符串

在这里插入图片描述

总结一下:

细节:字符串栈中,初始化先放入一个空串。

分情况讨论:

  1. 遇到数字,提取出这个数字,放入 “数字栈” 中
  2. 遇到 ’ [ ',把后面字符串提取出来,放到到 “字符串栈” 中
  3. 遇到 ’ ] ',解析,然后放到 “字符串栈” 栈顶的字符串后面
  4. 遇到单独的字符,提取出来这个字符串,直接放在"字符串栈" 栈顶的字符串后面
class Solution {
public:
    string decodeString(string s) {
        vector<string> strst(1,string());
        vector<int> numst;

        int i = 0, n = s.size();
        while(i < n)
        {
            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');
                numst.push_back(tmp);
            }
            else if(s[i] == '[')
            {
                ++i; // 把括号后⾯的字符串提取出来
                string str;
                while(i < n && isalpha(s[i]))
                    str += s[i++];
                strst.push_back(str);
            }
            else if(s[i] == ']')
            {

                string str = strst.back();
                strst.pop_back();
                int k = numst.back();
                numst.pop_back();

                while(k--)
                    strst.back() += str;

                ++i;//跳过这个右括号
            }
            else
            {
                string str;
                while(i < n && isalpha(s[i]))
                    str += s[i++];
                strst.back() += str;
            }
        }

        return strst.back();
    }
};

5.验证栈序列

题目链接: 946. 验证栈序列

题目描述:

在这里插入图片描述

给一个入栈顺序和出栈顺序,看是否匹配。

算法原理:

解法:借助栈模拟即可

让进栈元素一直进栈,进栈之后让栈顶元素和出栈元素比较是否相等,相等且栈不为空就一直出栈,不相等继续进栈。当进栈元素都进栈之后,如果栈不为空 或者 出栈元素还没有完,就不匹配,否则匹配。

在这里插入图片描述

  1. 让元素一直进栈
  2. 进栈的同时,判断是否出栈即可
  3. 当所有元素进栈完毕之后,判断 i 是否已经遍历完毕 或者 判断栈是否为空即可。
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        for(auto &e : pushed)
        {
            st.push(e);
            while(!st.empty() && popped[i] == st.top())
            {
                st.pop();
                ++i;
            }
        }

        if(!st.empty()) return false;
        return true;
    }
};

相关推荐

  1. 算法集训】基础数据结构:四、

    2024-07-21 19:50:02       70 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 19:50:02       132 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 19:50:02       146 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 19:50:02       122 阅读
  4. Python语言-面向对象

    2024-07-21 19:50:02       133 阅读

热门阅读

  1. [强化学习马里奥 MarioRL]-- 环境ENV 3

    2024-07-21 19:50:02       26 阅读
  2. ubuntu 上安装中文输入法

    2024-07-21 19:50:02       26 阅读
  3. 记一次通过udev自动加在i2c接口触摸驱动过程

    2024-07-21 19:50:02       25 阅读
  4. 优选算法之滑动窗口(下)

    2024-07-21 19:50:02       28 阅读
  5. Linux常用命令(备忘自查)

    2024-07-21 19:50:02       26 阅读
  6. 计算机视觉发展历程

    2024-07-21 19:50:02       28 阅读