day11 代码回想录-栈与队列part02-有效的括号&删除字符串中的所有相邻重复项&逆波兰表达式求值

这篇具有很好参考价值的文章主要介绍了day11 代码回想录-栈与队列part02-有效的括号&删除字符串中的所有相邻重复项&逆波兰表达式求值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大纲

● 20. 有效的括号
● 1047. 删除字符串中的所有相邻重复项
● 150. 逆波兰表达式求值

有效的括号

题目链接:20. 有效的括号
题目需要判断括号是否匹配
解题思路:
使用栈来实现,当为**{[(时入栈,当遇到)]}时,判断栈顶元素释放能匹配。需要单独处理只有右边**单个括号的情况。

bool isRightString(string s)
{
    stack<char> _stack;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '['
                || s[i] == '{'
                || s[i] == '(') {
            _stack.push(s[i]);
        }
        if (s[i] == ']'
                || s[i] == '}'
                || s[i] == ')')
        {
            if (!_stack.empty()) {
                char ch = _stack.top();
                if ( (s[i] == ']' && ch != '[')
                        || (s[i] == '}' && ch != '{')
                        || (s[i] == ')' && ch != '('))
                    return false;
                _stack.pop();
            } else {
            	return false;
            }
        }
    }
    return _stack.empty();
}

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

题目链接:1047. 删除字符串中的所有相邻重复项
分析过程:
本题也是使用栈来解决,不断消除相邻相同的元素。剩下栈中的元素需要逆序。

string removeDuplicates(string s) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }

逆波兰表达式求值

题目链接:150. 逆波兰表达式求值
分析过程:
逆波兰表达式其实就是后缀表达式求值,模拟计算机计算表达式的过程。思路是使用栈保存操作数,遇到操作符则取出栈中元素做计算,之后再把结果放回栈中。【特别要注意栈中元素放回顺序和实际顺序相反】
需要注意处理栈为空的情况和注意操作数顺序。文章来源地址https://www.toymoban.com/news/detail-676286.html

bool isNumber(string s) {
    if (s == "+" || s == "-" || s == "*" || s == "/") {
        return false;
    }
    return true;
}

int getExpressValue(vector<string>& tokens)
{
    stack<int> _stack;
    for (int i = 0; i < tokens.size(); ++i) {
        if (!isNumber(tokens[i])) {
            int val1 = _stack.top();
            _stack.pop();
            int val2 = _stack.top();
            _stack.pop();

            if (tokens[i] == "+") {
                _stack.push(val2 + val1);
            }
            else if (tokens[i] == "-") {
                _stack.push(val2 - val1);
            }
            else if (tokens[i] == "*") {
                _stack.push(val2 * val1);
            }
            else {
                _stack.push(val2 / val1);
            }
        } else {
            int _val1 = atoi(tokens[i].c_str());
            _stack.push(_val1);
        }
    }
    return _stack.empty() ? 0 : _stack.top();
}

到了这里,关于day11 代码回想录-栈与队列part02-有效的括号&删除字符串中的所有相邻重复项&逆波兰表达式求值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode:20. 有效的括号——栈和队列

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正

    2023年04月26日
    浏览(57)
  • 算法训练day4:栈与队列

    那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C++为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。 C++中stack 是容器么? 我们使用的stack是属于哪个版本的STL? 我们使用的STL中stack是如何实现的? stack 提供迭

    2024年02月01日
    浏览(36)
  • Day28- 贪心算法part02

    题目一:122. 买卖股票的最佳时机II 122. 买卖股票的最佳时机 II 给你一个整数数组  prices  ,其中  prices[i]  表示某支股票第  i  天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候  最多  只能持有  一股  股票。你也可以先购买,然后在  同一天  

    2024年01月15日
    浏览(48)
  • Day32 贪心算法part02

    太牛了我,随随便便双指针秒杀 md题解里面双指针都没用直接for循环秒杀 写成这样纯粹是没有看到第一次跳跃必须从第一个开始

    2024年02月20日
    浏览(40)
  • Leetcoder Day12| 二叉树 part02

    语言:Java/C++  给你一个二叉树,请你返回其按层序遍历得到的节点值。 (即逐层地,从左到右访问所有节点)。 在昨天的二叉树理论基础里有提到,层序遍历需要借助队列实现。 队列先进先出,符合一层一层遍历的逻辑 这里要注意的是,定义每一层元素列表的时候ListIn

    2024年01月20日
    浏览(37)
  • 算法打卡|Day4 链表part02

    今日任务 ● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II 目录 Day4 链表part02 Problem: 24. 两两交换链表中的节点 思路 解题方法 Code Code Problem: 19. 删除链表的倒数第 N 个结点 思路 解题方法 Code Problem: 面试题 02.07. 链表相交

    2024年02月08日
    浏览(43)
  • 代码随想录笔记--栈与队列篇

    目录 1--用栈实现队列 2--用队列实现栈 3--有效的括号 4--删除字符串中的所有相邻重复项 5--逆波兰表达式求值 6--滑动窗口的最大值 7--前k个高频元素 利用两个栈,一个是输入栈,另一个是输出栈 ; 主要思路:         弹出栈顶元素时,需要将队列前 size - 1 个元素先弹出再

    2024年02月10日
    浏览(48)
  • 数据结构例题代码及其讲解-栈与队列

    栈Stack 后进先出 ​ 栈的结构体定义及基本操作。 初始化 ​ 这里初始化时是将栈顶指针指向-1,有些则是指向0,因此后续入栈出栈的代码略微有点区别 判断栈是否为空 压栈操作 由于初始时栈顶指针指向-1,因此需要先变化栈顶指针,然后入栈操作; 且当MaxSize为50时候,数

    2024年02月10日
    浏览(42)
  • Day32 贪心算法 part02 122. 买卖股票的最佳时机 II 55. 跳跃游戏 45. 跳跃游戏 II

    思路:计算每天的利润,利润如果为正,加到结果中去

    2024年01月19日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包