【算法训练笔记】栈的OJ题

这篇具有很好参考价值的文章主要介绍了【算法训练笔记】栈的OJ题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

       🔥🔥 欢迎来到小林的博客!!
      🛰️博客主页:✈️林 子
      🛰️博客专栏:✈️ 小林的算法训练笔记
      🛰️社区 :✈️ 进步学堂
      🛰️欢迎关注:👍点赞🙌收藏✍️留言

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

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

题目描述:

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

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

提示:

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

解题思路:

我们只需要把字符入栈,每次入栈前和栈顶元素进行比较,如果字符相同则把栈顶POP掉,并且此次元素也不Push,这样即完成一次删除操作。反之则把元素push入栈。 因为返回值是一个字符串,所以我们可以拿字符串来模拟栈,尾删对应的是出栈,尾插对应的是入栈。

动图详解:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

代码:

class Solution {
public:
    string removeDuplicates(string s) {
        string st;//用字符串模拟栈
        for(auto& ch : s)
        {
            if(st.size() > 0 && st.back() == ch)
            {
                st.pop_back();
            }else
            {
                st.push_back(ch);
            }
        }
        return st;
    }
};

运行结果:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

844. 比较含退格的字符串

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

题目描述:

给定 st 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true# 代表退格字符。

**注意:**如果对空文本输入退格字符,文本继续为空。

示例 1:

输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。

示例 2:

输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。

示例 3:

输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。

提示:

  • 1 <= s.length, t.length <= 200
  • st 只含有小写字母以及字符 '#'

解题思路:

和上一题是一样的,只不过这次我们是遇到#则删除前一个。而上一题是当前字符和栈顶字符相等则删除栈顶字符,这个则是遇到#删除栈顶字符。然后两个字符串都做一次上面那道题的操作,然后比较一小是否相等即可,不过这里也有一个小细节,那就是#号可以出现在第一个字符,这里需要特殊判断一下。因为步骤和上面几乎一模一样,所以动图就不画了,搞懂了上一题这一题自然也能秒懂。

代码:

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string st1; //存储s
        string st2; //存储t
        for(auto& ch : s)
        {
            if(st1.size() > 0 && ch == '#') st1.pop_back();
            else if(ch != '#') st1.push_back(ch);
        }
        //和上面操作一模一样
        for(auto& ch : t)
        {
            if(st2.size() > 0 && ch == '#') st2.pop_back();
            else if(ch != '#')st2.push_back(ch); //#符号不能入栈
        }
        return st1 == st2; //相等返回true
    }
};

运行结果:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

227. 基本计算器 II

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

题目描述:

给你一个字符串表达式 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 整数

解题思路

因为这运算只有 +,-,*,/四则运算。所以我们只需要用一个栈来存储数据,再用一个char op变量来存储符号。当走到数字的时候遇到 X 或者 / 号。那么就从栈中pop出2个数据。进行运算后再重新放回队列,如果记录的是-号。那么我们往队列push的值需要 乘上一个-1。到最后再把栈里的值全部相加起来即可。这里需要注意一个小细节,就是我们的op需要初始化成’+'号。因为只有op为’+‘ ,我们才会把数据push进栈中。

比如下面有一个例子,3+2*2-5 ,我们来动图模拟一下。

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

还有一点要注意的是,leetcode给的数据中是有可能会包含空格,所以遇到空格我们要跳过。

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

代码:

class Solution {
public:
    int calculate(string s) {
        char op = '+';
        stack<int> st;
        int n = s.size(), i = 0;
        while(i < n)
        {
            if(s[i] == ' ') i++;  //跳过空格
            else if(s[i] >= '0' && s[i] <= '9')
            {
                //遇到数据了,数据可能是多位数,所以我们要全部截取
                int val = 0; 
                while(s[i] >= '0' && s[i] <= '9') val = val * 10 + (s[i++] - 48); 

                //如果op是+号,我们要入栈,如果是-号,我们需要 * -1 再入栈,如果是 * 和 / 先出栈,再val和出栈的数进行运算
                if(op == '+')
                    st.push(val);
                else if(op == '-')
                    st.push(val* -1);
                else 
                {
                    //是 * 和 / ,我们把栈顶元素拿出来运算,运算完再push到栈中
                    int top = st.top();
                    st.pop();
                    switch(op)
                    {
                        case '*' : st.push(top * val);  break;
                        case '/' : st.push(top/val); break;
                    }
                }
            }else 
            {
                //遇到符号了,直接替换符号
                op = s[i++]; 
            }
        }

        //把栈中的元素全部取出来相加
        int sum = 0 ;
        while(!st.empty())
        {
            sum += st.top();
            st.pop();
        }
        return sum;
    }
};

运行结果:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

394. 字符串解码

题目链接:字符串解码

题目描述:

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[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:遇到数字

遇到数字,那么数字可能也是多个字符串组成,所以我们需要把数字提取出来,放入 nums栈中。

情况2:遇到 [

遇到[说明要开始提取字符了,那么从当前下标的下一个位置开始提取字符串。提取完字符串后入到 strs栈中。

情况3:遇到 ]

遇到 [ 说明我们要开始解密了,我们分别提取strs栈和nums栈中的栈顶。获得一个数字k和一个字符串str。我们循环k次,每次循环都加上一个str。最后需要把strs接到栈顶的尾部,因为我们不确定前面是否还有字符。

情况4:遇到字符

遇到字符说明数字只有1,所以我们只需要把字符提取出来,接入到strs栈顶的尾部即可。

需要注意一些小细节,那就是当strs栈为空的时候,我们是无法把字符串接入到栈顶的。所以我们一开始需要push一个空串进strs栈。这样后面的字符串往空串后面拼接,还是原来的样子。

动图演示:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

动图中没有显示空串,其实最底下是有个空串的。否则后面的cacacacacaca接入到栈顶元素尾部是会报错的。

代码:

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs; 
        strs.push(""); //先让空串入栈
        int i = 0 , n = s.size();
        while(i < n)
        {
            //第一种情况,如果遇到数字
            if(s[i] >= '0' && s[i] <= '9')
            {
                int val = 0;
                //拼接所有数字
                while(s[i] >= '0' && s[i] <= '9') val = val * 10 + (s[i++] - 48); 
                //拼接完数字入栈
                nums.push(val);
            }
            else if(s[i] == '[') //第二章情况,遇到 [ 
            {
                //从i的下一个位置开始提取字符
                string val; 
                i++; 
                while(s[i] >= 'a' && s[i] <= 'z')val += s[i++]; 
                //提取的字符入栈
                strs.push(val);
            }else if(s[i] == ']') // 第三种情况,遇到 ]
            {
                //分别从nums和strs中提取栈顶元素
                int k = nums.top();
                nums.pop();
                string tmp = strs.top();
                strs.pop();

                //将 k 次 tmp字符串接入到strs栈顶的尾部
                while(k--)
                {
                    strs.top() += tmp;
                }
                i++; //跳到下一个位置
            }else{
                //第四种情况,遇到字符
                //直接提取字符,接入到栈顶尾部
                string val; 
                while(i < n && s[i] >= 'a' && s[i] <= 'z')val += s[i++]; 
                //接入到栈顶尾部
                strs.top() += val;
            }
        }
        return strs.top(); //返回栈顶元素
    }
};

运行结果:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

946. 验证栈序列

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

题目描述:

给定 pushedpopped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 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
  • poppedpushed 的一个排列

解题思路:

我们可以用一个指针指向popped数组,然后疯狂让pushed数组的值入栈。然后监测栈顶元素是否等于当前指向的popped元素。如果等于则说明出栈,一直出栈到栈顶元素不等于popped为止。最后如果栈的元素不为空,说明出栈顺序是错误的。反之则是正确的。

动图演示:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记

如果循环结束,栈为空,则说明poped的出栈顺序是正确的。反之则说明是错误的。

代码:

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st; 
        for(int i = 0 , j = 0 ; i < pushed.size() ; i++)
        {
            st.push(pushed[i]);
            while(!st.empty() && st.top() == popped[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

运行结果:

【算法训练笔记】栈的OJ题,算法训练笔记,算法,笔记文章来源地址https://www.toymoban.com/news/detail-701028.html

到了这里,关于【算法训练笔记】栈的OJ题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【小笔记】从算法训练现象分析可能的参数设置问题-loss分析篇

    【学而不思则罔,思而不学则殆】 9.30 首先给出一个理想的训练loss收敛图片:loss平滑的下降,并逐渐收敛到0. 平滑说明学习率设置较合适,收敛到0说明模型在参数空间中收敛到一个很理想的区域。 训练现象: 本质原因: 算法收敛到参数空间中某个较高的“平坦区域”,而

    2024年02月07日
    浏览(33)
  • 数据结构刷题训练:用栈实现队列(力扣OJ)

    目录 前言 1. 题目:用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念,它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(39)
  • 【数据结构与算法】栈的讲解

    栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把 允许插入和删除的一段称为栈顶(top) , 另一端称为栈底 , 不含任何数据元素的栈称为空栈 。 栈又称为后进先出的线性表 。 进一步理解栈,栈首先他是一个 线性表 ,所以栈元素具有前驱后继关系。 栈的插入操

    2023年04月08日
    浏览(39)
  • 【算法与数据结构】栈的实现详解

    栈的概念: 栈 :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:

    2024年03月11日
    浏览(55)
  • 【算法】行星碰撞&机器人碰撞(栈的使用)

    本文记录了两个使用栈来处理碰撞问题的算法题目。 https://leetcode.cn/problems/asteroid-collision/ 对于这种题目,各个元素分别会向左或向右移动,可以使用栈模拟碰撞的过程。 由于从左往右进行遍历,因此遍历当前元素时,如果它是向右移动的,就只可能会碰撞到它右边还没有被

    2024年02月16日
    浏览(47)
  • 训练自己的ai模型(四)学习笔记与项目实操(什么也不懂,但有数据,怎么搞?无监督学习算法)

    很开心有人还在催更,有点小震惊吧。 (原来真有人在csdn发学习记录啊) (原来真有人在csdn看学习记录啊) ai模型方向的知识,我也在学习中,可能疑惑不比大家少。 直接开始! 不管你的是什么数据,只要你有数据,你就可以试一试,跑一跑。 使用 无监督学习算法 。

    2024年02月07日
    浏览(69)
  • 算法通关村第四关-黄金挑战栈的经典问题

    描述 :  给定一个只包括  \\\'(\\\' , \\\')\\\' , \\\'{\\\' , \\\'}\\\' , \\\'[\\\' , \\\']\\\'  的字符串  s  ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 题目 : LeetCode 20.有效的括号 : 

    2024年02月07日
    浏览(44)
  • 数据结构与算法-(7)---栈的应用-(4)后缀表达式求值

    🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如需转载还请通知⚠️ 📝个人主页:Aileen_0v0🧸—CSDN博客 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​ 📣系列专栏:Aileen_0v0🧸

    2024年02月07日
    浏览(53)
  • 《深入理解Java虚拟机》读书笔记:基于栈的字节码解释执行引擎

      虚拟机是如何调用方法的内容已经讲解完毕,从本节开始,我们来探讨虚拟机是如何执行方法中的字节码指令的。上文中提到过,许多Java虚拟机的执行引擎在执行Java代码的时候都有 解释执行(通过解释器执行) 和 编译执行(通过即时编译器产生本地代码执行) 两种选

    2024年02月11日
    浏览(53)
  • 【算法】BF、KMP算法及OJ题

      大家好,好久不见,这里是平凡的人,众所周知,现在是暑假时期,趁现在时间比较充裕,博主将通过这篇博客具体介绍数据结构与算法中的BF、KMP算法, 记录自己的学习过程加上自己的理解,希望能够帮到更多的人了解学习BF、KMP算法。同时,如果存在错误的地方,还请

    2024年02月01日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包