当前位置: 首页 > news >正文

栈的三道oj【C++】

栈和队列的相关oj

  • 最小栈
    • 思路
    • 解决代码
  • 栈的压入弹出序列
    • 思路
    • 解决代码
  • 逆波兰表达式
    • 思路:
    • 解决代码

这里就挑了三道题用来熟悉栈

最小栈

力扣链接

在这里插入图片描述
咱们已经是高贵的C++使用者了,不用像C语言一样从头开始造轮子了

这里我们调用了stack后,就会发现这道题主要的问题就是getMin的功能。

思路

按照一般人的思路可能会想在成员变量中添加一个最小值的成员:min
每次进栈和出栈来比较是否与值相同,进行更新。

但是在实现的过程中就会发现这个思路并不可行
因为:
**
当最小值出栈后,那第二个最小值不知道填什么
这个问题的最主要原因是栈无法遍历**

所以这里就要用新的思路了:

双栈:
创建一个用来放最小值的栈
在这里插入图片描述

1.每次插入都进行比较,看看是否是比栈顶小,这样就可以保证栈顶一直是最小值

2.注意这里相同大小的最小值也要进行放入,防止有相同的重复最小值

3.出栈时:与最小栈的栈顶进行比较,看看是否等于,如果一样就出最小栈的栈顶
在这里插入图片描述

思路大致是这样,实现就直接放在下面了。

解决代码

class MinStack {
public:void push(int val) {_stack.push(val);if(_stack_min.empty()||val<=_stack_min.top()){_stack_min.push(val);}}void pop() {if(_stack.top()==_stack_min.top())_stack_min.pop();_stack.pop();}int top() {return _stack.top();}int getMin(){return _stack_min.top();}private:stack<int> _stack;stack<int> _stack_min;
};

栈的压入弹出序列

力扣链接

在这里插入图片描述

思路

这道题主要就是考:如何判断出栈的顺序的可行性的判断。

这里我们随便来串数字进行判断

在这里插入图片描述
那我们来看一下我们的判断方法:
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
经过上图我们知道了我们判断一个出栈顺序,是否符合入栈顺序的基本过程

总结来说就是模拟入栈和出栈

所以这边我们可以把过程给归纳一下了:
1.不停入栈,直到和出栈顺序的元素相同
2.然后将出栈元素出栈,之后继续不停入栈,再知道和出栈队列元素相同
3.判断入栈元素是否无了,跳出循环
4.判断栈是否为空,如果为空栈,这样的话证明结论是是可行的,反之则不行。

解决代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> _st;int push=0;int pop=0;while(push<pushV.size()){_st.push(pushV[push++]);while(!_st.empty()&&_st.top()==popV[pop]){_st.pop();pop++;}}return _st.empty();}
};

逆波兰表达式

力扣链接

这里首先来解释一下为什么会有这个表达式的出现:

对于计算机来说,用中缀的表达式十分不友好。
因为如果读取两个数和一个符号后,还不能马上进行计算

因为你无法确定后面有没有更高优先级的运算符。

思路:

这里其实我们看到思路也很简单其实,没有什么复杂的。

在这里插入图片描述

这里就拿这个队列来举例子。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

接下来就是重复就行了。。

思路还是很明确的。

解决代码


class Solution {
public:int evalRPN(vector<string>& tokens){for (auto& str : tokens){if (str != "*" && str != "-" && str != "+" && str != "/"){_st.push(stoi(str));}else{switch (str[0]){case '+':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right + left);break;}case '-':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right - left);break;}case '*':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right * left);break;}case '/':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right / left);break;}}}}return _st.top();}
private:stack<int> _st;};

相关文章:

栈的三道oj【C++】

栈和队列的相关oj 最小栈思路解决代码 栈的压入弹出序列思路解决代码 逆波兰表达式思路&#xff1a;解决代码 这里就挑了三道题用来熟悉栈 最小栈 力扣链接 咱们已经是高贵的C使用者了&#xff0c;不用像C语言一样从头开始造轮子了 这里我们调用了stack后&#xff0c;就会发…...

AI大模型低成本快速定制法宝:RAG和向量数据库

文章目录 1. 前言2. RAG和向量数据库3. 论坛日程4. 购票方式 1. 前言 当今人工智能领域&#xff0c;最受关注的毋庸置疑是大模型。然而&#xff0c;高昂的训练成本、漫长的训练时间等都成为了制约大多数企业入局大模型的关键瓶颈。 这种背景下&#xff0c;向量数据库凭借其独特…...

文旅媒体有哪些?如何邀请到现场报道?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 中国文旅产业在近年来得到了持续而快速的发展。从产业端看&#xff0c;中国文旅产业呈现出新的发展趋势&#xff0c;其中“文旅”向“文旅”转变成为显著特点。通过产业升级和空间构建&a…...

搭建知识付费系统的最佳实践是什么

在数字化时代&#xff0c;搭建一个高效且用户友好的知识付费系统是许多创业者和内容创作者追求的目标。本文将介绍一些搭建知识付费系统的最佳实践&#xff0c;同时提供一些基本的技术代码示例&#xff0c;以帮助你快速入门。 1. 选择合适的技术栈&#xff1a; 搭建知识付费…...

计算机视觉:使用opencv实现车牌识别

1 引言 汽车车牌识别&#xff08;License Plate Recognition&#xff09;是一个日常生活中的普遍应用&#xff0c;特别是在智能交通系统中&#xff0c;汽车牌照识别发挥了巨大的作用。汽车牌照的自动识别技术是把处理图像的方法与计算机的软件技术相连接在一起&#xff0c;以准…...

用封面预测书的价格【图像回归】

今天&#xff0c;我将介绍计算机视觉的深度学习应用&#xff0c;用封面简单地估算一本书的价格。 我没有看到很多关于图像回归的文章&#xff0c;所以我为你们写这篇文章。 距离我上一篇文章已经过去很长时间了&#xff0c;我不得不承认&#xff0c;作为一名数据科学家&#x…...

阿里云服务器e实例40G ESSD Entry系统盘、2核2G3M带宽99元

阿里云99元服务器新老用户同享2核2G经济型e实例、3M固定带宽和40G ESSD Entry系统盘&#xff0c;老用户也可以买&#xff0c;续费不涨价依旧是99元一年&#xff0c;阿里云百科aliyunbaike.com分享阿里云3M带宽服务器40G ESSD Entry云盘性能说明&#xff1a; 阿里云99元服务器配…...

Datawhale智能汽车AI挑战赛

1.赛题解析 赛题地址&#xff1a;https://tianchi.aliyun.com/competition/entrance/532155 任务&#xff1a; 输入&#xff1a;元宇宙仿真平台生成的前视摄像头虚拟视频数据&#xff08;8-10秒左右&#xff09;&#xff1b;输出&#xff1a;对视频中的信息进行综合理解&…...

pyclipper和ClipperLib操作多边型

目录 1. 等距离缩放多边形 1.1 python 1.2 c 1. 等距离缩放多边形 1.1 python 环境配置pip install opencv-python opencv-contrib-python pip install pyclipper pip install numpy import cv2 import numpy as np import pyclipperdef equidistant_zoom_contour(contour…...

Golang 协程、主线程

Go协程、Go主线程 1)Go主线程(有程序员直接称为线程/也可以理解成进程):一个Go线程上&#xff0c;可以起多个协程&#xff0c;你可以这样理解&#xff0c;协程是轻量级的线程。 2)Go协程的特点 有独立的栈空间 共享程序堆空间 调度由用户控制 协程是轻量级的线程 go线程-…...

【SA8295P 源码分析】125 - MAX96712 解串器 start_stream、stop_stream 寄存器配置 过程详细解析

【SA8295P 源码分析】125 - MAX96712 解串器 start_stream、stop_stream 寄存器配置 过程详细解析 一、sensor_detect_device():MAX96712 检测解串器芯片是否存在,获取chip_id、device_revision二、sensor_detect_device_channels() :MAX96712 解串器 寄存器初始化 及 detec…...

pandas教程:Apply:General split-apply-combine 通常的分割-应用-合并

文章目录 10.3 Apply&#xff1a;General split-apply-combine&#xff08;应用&#xff1a;通用的分割-应用-合并&#xff09;1 Suppressing the Group Keys&#xff08;抑制组键&#xff09;2 Quantile and Bucket Analysis&#xff08;分位数与桶分析&#xff09;3 Example:…...

第一讲之递归与递推下篇

第一讲之递归与递推下篇 带分数费解的开关飞行员兄弟翻硬币 带分数 用暴力将所有全排列的情况都算出来 > 有三个数&#xff0c;a,b,c 每种排列情况&#xff0c;可以用两层for循环&#xff0c;暴力分为三个部分&#xff0c;每个部分一个数 当然注意这里&#xff0c;第一层fo…...

第十六篇-Awesome ChatGPT Prompts-备份

Awesome ChatGPT Prompts——一个致力于提供挖掘ChatGPT能力的Prompt收集网站 https://prompts.chat/ 2023-11-16内容如下 ✂️Act as a Linux Terminal Contributed by: f Reference: https://www.engraved.blog/building-a-virtual-machine-inside/ I want you to act as a…...

Python Web框架Django

Python Web框架Django Django简介第一个Django应用Django核心概念Django django-adminDjango项目结构Django配置文件settingsDjango创建和配置应用Django数据库配置Django后台管理Django模型Django模型字段Django模型关联关系Django模型Meta 选项Django模型属性ManagerDjango模…...

1.Spring的简单使用

简介 本文是介绍spring源码的开始&#xff0c;先了解最基础的使用&#xff0c;最深入源码。 spring源码下载地址 https://github.com/spring-projects/spring-framework.git 依赖 依赖 spring-context dependencies {implementation(project(":spring-context")…...

02.智慧商城——vant组件库使用和vw适配

01. vant组件库及Vue周边的其他组件库 组件库&#xff1a;第三方封装好了很多很多的组件&#xff0c;整合到一起就是一个组件库。 https://vant-contrib.gitee.io/vant/v2/#/zh-CN/ 比如日历组件、键盘组件、打分组件、下拉筛选组件等 组件库并不是唯一的&#xff0c;常用的组…...

Android笔记(十三):结合JetPack Compose和CameraX实现视频的录制和存储

在“Android笔记&#xff08;八&#xff09;&#xff1a;基于CameraX库结合Compose和传统视图组件PreviewView实现照相机画面预览和照相功能”&#xff0c;文中介绍了拍照功能的实现&#xff0c;在本文中将介绍结合JetPack Compose和CameraX实现视频的录制。 新建一个项目 在项…...

【开题报告】基于SpringBoot的音乐鉴赏平台的设计与实现

1.研究背景与意义 音乐是人类文化的重要组成部分&#xff0c;具有广泛的影响力和吸引力。然而&#xff0c;随着数字化时代的到来&#xff0c;传统的音乐鉴赏方式面临一些挑战。因此&#xff0c;设计和开发一个基于Spring Boot的音乐鉴赏平台&#xff0c;能够满足用户对音乐欣赏…...

云原生 黑马Kubernetes教程(K8S教程)笔记——第一章 kubernetes介绍——Master集群控制节点、Node工作负载节点、Pod控制单元

参考文章&#xff1a;kubernetes介绍 文章目录 第一章 kubernetes介绍1.1 应用部署方式演变传统部署&#xff1a;互联网早期&#xff0c;会直接将应用程序部署在物理机上虚拟化部署&#xff1a;可以在一台物理机上运行多个虚拟机&#xff0c;每个虚拟机都是独立的一个环境&…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...