代码编织梦想

一、逆波兰表达式求值

解法:栈

逆波兰表达式求值的过程总是先列出运算符前面两个数字,然后将这两个数字进行相应运算,得到一个新的数字,这个数又与后面的数进行相应运算,直到结束。

所以,可以先新建一个栈,当遇到数字时,直接压入栈中,遇到运算符时,先取出栈顶的两个数字,进行相应运算,再压回栈中。最后栈中剩下的那个元素即是表达式的值。
在这里插入图片描述

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack<int> s;
        int num,num1,num2,tmp;
        for(auto i:tokens){
            if(i=="+"|| i=="-"|| i=="*"|| i=="/")
            {
                num1=s.top();
                s.pop();
                num2=s.top();
                s.pop();
                if(i=="+")
                    tmp=num2+num1;
                else if(i=="-")
                    tmp=num2-num1;
                else if(i=="*")
                    tmp=num2*num1;
                else if(i=="/")
                    tmp=num2/num1;  
                s.push(tmp);
            }

            else
            {
                num = atoi(i.c_str());
                s.push(num);
            }
        }   
        return s.top();
    }
};

时间复杂度:需要遍历整个字符串数组,所以时间复杂度是O(n)。
空间复杂度:最坏情况下,总共有(n+1)/2个数压入栈中,所以至多需要额外大小为(n+1)/2的栈,所以空间复杂度为O(n)。

二、点击消除

解法:栈

  • 创建一个空栈;输入元素;
  • 遍历s,如果栈内元素为0,则直接添加;否则,如果栈内最后一个元素与i相等,则弹出该元素;否则直接添加;
  • 如果栈长度为0,打印0;否则,逐个打印
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main()
{
    string str;
    cin>>str;
    stack<char>s;
    for(auto i:str)
    {
        if(s.empty())
            s.push(i);
        else
        {
            if(i==s.top())
                s.pop();
            else
                s.push(i);
        }
    }
    if(s.empty())
        cout<<0<<endl;
    else
    {
        str.clear();
        while(!s.empty())
        {
            str+=s.top();
            s.pop();
        }
        reverse(str.begin(),str.end());
        cout<<str<<endl;
    }
    return 0;
}

时间复杂度:O(n),遍历字符串
空间复杂度:O(n),栈最大为n

三、最长的括号子串

解法:

因为括号需要一一匹配,而且先来的左括号,只能匹配后面的右括号,因此可以考虑使用栈的先进后出功能,使括号匹配。

  • 可以使用栈来记录左括号下标。
  • 遍历字符串,左括号入栈,每次遇到右括号则弹出左括号的下标。
  • 然后长度则更新为当前下标与栈顶下标的距离。
  • 遇到不符合的括号,可能会使栈为空,因此需要使用start记录上一次结束的位置,这样用当前下标减去start即可获取长度,即得到子串。
  • 循环中最后维护子串长度最大值。
class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        stack<int> st;
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s[i] == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空,不合法,设置为结束位置
                if(st.empty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号,说明右括号不够,减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = max(res, i - st.top());
                    //栈中没有括号,说明左右括号行号,减去上一次结束的位置就是长度
                    else 
                        res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qwer1234mnbv_/article/details/126071037

python算法刷题——栈和队列(一)-爱代码爱编程

算法菜鸡的刷题记录,写的代码可能比较多冗余,可以到leetcode解题区看更多大佬们优雅的解题~ 一、栈和队列 栈(stack): 后进先出。 栈的一些标准操作: s.pop() # 出栈 s.push() # 入栈 s.top() # 获取栈顶元素(不出栈) s.size() # 获取栈的大小(元素个数) s.empty() # 判断栈是否为空

LeetCode刷题——栈和队列2-爱代码爱编程

LeetCode刷题——栈和队列2 逆波兰表达式求值滑动窗口最大值前 K 个高频元素 逆波兰表达式求值 题目链接题意:根据逆波兰表示法(后缀表达式),求表达式的值。思路:一般a+b表达式是中缀表达式的形式,ab+就是后缀表达式的的形式。遍历字符串,用栈存数字,遇到运算符的时候,对栈顶部的两个元素进行相应的操作,弹出这两个数字,将他们的结果存入

LeetCode刷题——栈(python语言)-爱代码爱编程

LeetCode刷题——栈(python语言) 一、栈 1.1 定义 栈(Stack):也称堆栈。一种线性表数据结构,是一种只允许在表的一端进行插入和删除操作的线性表。 我们把栈中允许插入和删除的一端称为[栈顶(top)];另一端则称为[栈底(bottom)]。当表中没有任何数据元素时,称之为[空栈]。 栈的特点: 线性表后进先出 栈的存储方式有顺

<数据结构>刷题笔记——栈和队列篇(动图详解)-爱代码爱编程

文章目录 1. 有效的括号【链接】【思路】【参考代码】2. 用队列实现栈【链接】【思路】【参考代码】3. 用栈实现队列【链接】【思路】【参考代码】4. 设计循环队列【链接】【思路】【参考代码】 目前在不断更新<数据结构>的知识总结,已经更新完了<C语言>,未来我会系统地更新<C++语言><Linu

树上启发式合并小结_汤键.的博客-爱代码爱编程

算法适用:dsu on tree主要是解决不修改的子树问题首先看题先想一下暴力算法,对于每一次询问都遍历整棵子树,然后统计答案,最后再清空cnt数组删除信息过程耗了太多的时间,最坏情况是时间复杂度为 O(n2)现在考虑优化算法先说以下大概过程大概过程1.处理轻子树及其子树的答案,删除贡献2.处理重子树及其子树的贡献,并不删除贡献3.暴力统计所有轻子树及其子

java 集合_一只小鸟儿的博客-爱代码爱编程

3.1. 接口继承关系和实现 集合类存放于 Java.util 包中,主要有 3 种:set(集)、list(列表包含 Queue)和 map(映射)。 1. Collection:Collection 是集合 List、Set、Queue 的最基本的接口。 2. Iterator:迭代器,可以通过迭代器遍历集合中的数据

王道3.1 顺序栈以及链式栈_晨沉宸辰的博客-爱代码爱编程

顺序栈以及链式栈 一、的基本概念二、栈的储存三、顺序栈的基本操作四、链式栈的基本操作 一、的基本概念 1.栈只允许在一段进行删除或插入操作的线性表 2.三个术语 ①栈顶top :线性表允许进行插入删除的那

数据结构刷题——栈(上)_std i hurt o love的博客-爱代码爱编程

一、【模板】栈 C语言版 #include<stdio.h> #include<stdlib.h> #include<string.h> #define INITSIZE 10 ty

算法和数据结构解析-9 : 排序相关问题讲解_鮀城小帅的博客-爱代码爱编程

1. 排序算法复习 常见的排序算法可以分为两大类:比较类排序,和非比较类排序。 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。主要思路是通过将数值以哈希

程序优化之数据结构(list的数据结构的选择)_永远的helloworld的博客-爱代码爱编程

1.Arrarlist 和 Linkedlist 区别 (1)ArrayList 是实现了基于动态数组的数据结构,LinkedList 基于链表的数据结构。 (2)对于随机访问 get 和 set,ArrayList 觉得优于 LinkedList,因为 LinkedList 要移动指针。 (3)对于新增和删除操作 add 和 remove,Line

数据结构--插入排序_暗魂b的博客-爱代码爱编程

插入排序 直接插入排序 1、算法思想 每次将一个数插入到已经有序的序列中。 2、算法步骤(递增) ①将第一个元素视为初始有序序列,它已经有序,从第二个元素开始遍历 ②将需要插入元素赋值给r[0]作为哨兵,比较需要插入元

6.xml处理_秦剑的博客-爱代码爱编程

一、读 1.直接%XML.TextReader解析 方法或属性说明Read方法获取下一个路径AttributeCount属性获取当前结点的xml属性个数LacalName属性当前属性名称Value属性当前属性值 示例:

数据结构刷题——图论_std i hurt o love的博客-爱代码爱编程

一、【模板】拓扑排序 解法: 本题可分为两部分: 1.根据输入使用邻接表建图,并将每个顶点的入度记录下来; 2.采用类似于BFS(广搜)的思想,依次遍历入度为0的顶点,并根据邻接表进行相应顶点入度的调整,最终判断是否可以

数据结构刷题——二叉树_std i hurt o love的博客-爱代码爱编程

一、实现二叉树先序,中序和后序遍历 解法一:递归 「二叉树的先序遍历」的思路是:先访问根结点,再访问左子树,最后访问右子树; 「二叉树的中序遍历」的思路是:先访问左子树,再访问根结点,最后访问右子树; 「二叉树的后序

数据结构与算法复习:第七弹_理想国の糕的博客-爱代码爱编程

文章目录 1. 知识点总结2. 分题题解2.1 PAT 1156 Sexy Primes2.2 PAT 1157 Anniversary2.3 PAT 1158 Telefraud Detection2.4 PAT

数据结构刷题——dfs_std i hurt o love的博客-爱代码爱编程

一、kotori和素因子 kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是,kotori有强迫症,她不允许两个不同的正整数取出相同的素因子。 她想知道,最终所有取出的数的和的最小值是多少? 注:若

jdk线程池threadpoolexecutor源码总结_weixin_43478710的博客-爱代码爱编程

1、线程池定义的几个状态 private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0)); //29 private st

leecode刷题——栈和队列——括号匹配(栈的应用)_栈与队列括号匹配-爱代码爱编程

计算机程序中有非常多的栈的应用,其中最典型的就是括号匹配,以此来更深入的了解一下栈的原理 例题:20.有效的括号 代码: class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(