03.01、三合一
03.01、[简单] 三合一
1、题目描述
三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)
、pop(stackNum)
、isEmpty(stackNum)
、peek(stackNum)
方法。stackNum
表示栈下标,value
表示压入的值。
构造函数会传入一个stackSize
参数,代表每个栈的大小。
2、方法思路
- 数组表示栈:我们可以使用一个数组
arr
来表示三个栈。数组被划分为三个部分,每部分存储一个栈的元素。栈 1 的索引范围是[0, stackSize-1]
,栈 2 的范围是[stackSize, 2*stackSize-1]
,栈 3 的范围是[2*stackSize, 3*stackSize-1]
。 - 辅助指针数组:用一个长度为 3 的数组
tops
,存储每个栈的栈顶索引(即当前元素的存储位置),通过栈的编号stackNum
来访问对应的栈。 - 操作限制:
- 在进行
push
操作时,需要检查栈是否已经满了。 pop
和peek
操作在栈为空时应返回 -1。
- 在进行
3、代码实现
class TripleInOne {
private:vector<int> arr; // 用来存储三个栈的数据vector<int> tops; // 栈指针, 指向三个栈的下一个可用位置int stackSize; // 每个栈的最大容量public:// 初始化: 设置栈的大小, 初始化数组和栈顶指针TripleInOne(int stackSize) {this->stackSize = stackSize; // 保存栈的大小arr.resize(3 * stackSize); // 数组容量是三个栈的总容量// 初始化三个栈的指针// 栈 1 从 0 开始, 栈 2 从 stackSize 开始, 栈 3 从 2*stackSize 开始tops = {0, stackSize, 2 * stackSize};}// 向指定的栈中压入一个元素void push(int stackNum, int value) {// 检查当前栈是否已满if (tops[stackNum] < (stackNum + 1) * stackSize) {arr[tops[stackNum]++] = value; // 插入值并更新栈顶索引}}// 从指定的栈中弹出栈顶元素int pop(int stackNum) {if (isEmpty(stackNum)) { // 栈为空时返回-1return -1;}return arr[--tops[stackNum]]; // 弹出栈顶元素并更新栈顶索引}// 查看指定栈的栈顶元素int peek(int stackNum) {// 检查栈是否为空if (isEmpty(stackNum)) { // 栈为空时返回-1return -1;}return arr[tops[stackNum] - 1]; // 返回栈顶元素}// 判断指定栈是否为空bool isEmpty(int stackNum) {// 如果栈指针等于栈的起始位置,说明栈为空return tops[stackNum] == stackSize * stackNum;}
};
4、代码解析
- 构造函数
TripleInOne(int stackSize)
:- 初始化
arr
数组大小为3 * stackSize
,以容纳三个栈的数据。 - 初始化
tops
数组,分别为三个栈的初始位置:栈 1 为 0,栈 2 为stackSize
,栈 3 为2 * stackSize
。
- 初始化
push(int stackNum, int value)
:- 先检查当前栈是否已满(通过检查指针是否超出该栈的边界),若未满,则将值压入并更新指针。
pop(int stackNum)
:- 检查栈是否为空,若为空则返回 -1;否则更新指针并返回栈顶元素。
peek(int stackNum)
:- 检查栈是否为空,若为空则返回 -1;否则返回栈顶元素。
isEmpty(int stackNum)
:- 通过比较指针位置是否等于栈的初始位置来判断栈是否为空。
5、时间复杂度
push
、pop
、peek
和isEmpty
操作的时间复杂度均为 O(1),因为每次操作只需更新栈指针或访问数组中的一个元素。
这个解决方案使用了固定大小的数组来实现三个栈的分隔,逻辑简单且效率高。在面试中这是一个常见的问题,考察你对栈和数组的理解,以及如何在限制条件下实现数据结构。
相关文章:
03.01、三合一
03.01、[简单] 三合一 1、题目描述 三合一。描述如何只用一个数组来实现三个栈。 你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标,value表示压入的值。 构造函数会传入一个stackSize参数…...
github上clone代码过程
从 GitHub 上拉取代码的过程非常简单,一般通过 git clone 命令来完成。以下是详细步骤: 下载git工具 要下载并安装 Git,你可以根据你的操作系统来选择相应的步骤。以下是如何在不同操作系统上安装 Git 的详细说明: 1. 在 Windo…...

ChatGLM3模型搭建教程
一、介绍 ChatGLM3 是智谱 AI 和清华大学 KEG 实验室联合发布的对话预训练模型。ChatGLM3-6B 是 ChatGLM3 系列中的开源模型,在保留了前两代模型对话流畅、部署门槛低等众多优秀特性的基础上,ChatGLM3-6B 引入了如下特性: 更强大的基础模型…...

多层建筑能源参数化模型和城市冠层模型的区别
多层建筑能源参数化(Multi-layer Building Energy Parameterization, BEP)模型和城市冠层模型(Urban Canopy Model, UCM)都是用于模拟城市环境中能量交换和微气候的数值模型,但它们的侧重点和应用场景有所不同。以下是…...

27. Redis并发问题
1. 前言 对于一个在线运行的系统,如果需要修改数据库已有数据,需要先读取旧数据,再写入新数据。因为读数据和写数据不是原子操作,所以在高并发的场景下,关注的数据可能会修改失败,需要使用锁控制。 2. 分布式场景 2.1 分布式锁场景 面试官提问: 为什么要使用分布式锁?…...
JVM四种垃圾回收算法以及G1垃圾回收器(面试)
JVM 垃圾回收算法 标记清除算法:标记清除算法将垃圾回收分为两个阶段:标记阶段和清除阶段。 在标记阶段通过根节点,标记所有从根节点开始的对象。然后,在清除阶段,清除所有未被标记的对象 适用场合: 存活对…...

Python 数学建模——Vikor 多标准决策方法
文章目录 前言原理步骤代码实例 前言 Vikor 归根到底其实属于一种综合评价方法。说到综合评价方法,TOPSIS(结合熵权法使用)、灰色关联度分析、秩和比法等方法你应该耳熟能详。Vikor 未必比这些方法更出色,但是可以拓展我们的视野。…...

计算机网络八股总结
这里写目录标题 网络模型划分(五层和七层)及每一层的功能五层网络模型七层网络模型(OSI模型) 三次握手和四次挥手具体过程及原因三次握手四次挥手 TCP/IP协议组成UDP协议与TCP/IP协议的区别Http协议相关知识网络地址,子…...

AMD CMD UMD CommonJs ESM 的历史和区别
这几个东西都是用于定义模块规范的。有些资料会提及到这些概念,不理清楚非常容易困惑。 ESM(ES Module) 这个实际上我们是最熟悉的,就是ES6的模块功能。出的最晚,因为是官方出品,所以大势所趋,…...

人工智能数据基础之微积分入门-学习篇
目录 导数概念常见导数和激活导数python代码绘制激活函数微分概念和法则、积分概念微积分切线切面代码生成案例链式求导法则反向传播算法(重要) 一、概念 二、常见导数及激活导数 常见激活函数及其导数公式: 在神经网络中,激活函数用于引入非线性因素&…...

【PSINS】ZUPT代码解析(PSINS_SINS_ZUPT)|MATLAB
这篇文章写关于PSINS_SINS_ZUPT的相关解析。【值得注意的是】:例程里面给的这个m文件的代码,并没有使用ZUPT的相关技术,只是一个速度观测的EKF 简述程序作用 主要作用是进行基于零速更新(ZUPT)的惯性导航系统(INS)仿真和滤波 什么是ZUPT ZUPT是Zero Velocity Update(…...

多态(上)【C++】
文章目录 多态的概念多态的实现多态产生的条件什么是虚函数?虚函数的重写和协变重写协变 析构函数的重写为什么有必要要让析构函数构成重写? 多态的概念 C中的多态是面向对象编程(OOP)的一个核心特性,指的是同一个接口…...

如何驱动一枚30年前的音源芯片,YMF288驱动手记 Part2
一些问题 在上一篇里面虽然策划了想要驱动YMF288所需要做的事情以及目标。但是,在板子打出来后,我在进一步的研究中,发现我犯了个错误,那就是YMF288并不是使用现在很多轻量化的嵌入式,比如ESP32常用的I2S协议的&#x…...
yarn webpack脚手架 react+ts搭建项目
安装 Yarn 首先,确保你已经安装了 Node.js 和 Yarn。如果还没有安装 Yarn,可以通过以下命令安装: npm install -g yarn创建项目 使用 create-react-app 脚手架创建一个带有 TypeScript 的项目,node更新到最新版,并指定…...

防蓝光护眼灯有用吗?五款防蓝光效果好的护眼台灯推荐
现在孩子的很多兴趣班和课后辅导班都是在线上举行,通常对着手机电脑长时间。电子产品有大量蓝光和辐射,会伤害到孩子的眼睛。但为了学习,也是没办法。护眼台灯的出现可以让孩子们的眼睛得到保护,防止蓝光对眼睛的伤害。防蓝光护眼…...

Mac使用Elasticsearch
下载 Past Releases of Elastic Stack Software | Elastic 解压tar -xzvf elasticsearch-8.15.1-darwin-x86_64.tar.gz 修改配置文件config/elasticsearch.yml xpack.security.enabled: false xpack.security.http.ssl: enabled: false 切换目录 cd elasticsearch-8.15.1/…...
DevOps -CI/CD 与自动化部署
DevOps - CI/CD 与自动化部署详解 DevOps 是一种结合开发(Development)与运维(Operations)的方法论,旨在通过工具和文化变革,促进软件开发和运维之间的协作,提升软件交付的效率、质量和稳定性。…...

单体架构系统是不是已经彻底死亡?
单体架构系统并未“彻底死亡”,尽管在复杂和大规模的应用场景中,它可能不再是首选的架构模式。单体架构系统,也称为巨石系统(Monolithic),在软件发展过程中是最广泛的架构风格之一,出现时间最早…...

mathorcup发邮件:参赛必看邮件撰写技巧?
mathorcup发邮件的注意事项?如何使用mathorcup发信? 无论是提交参赛作品、咨询比赛规则,还是与组委会沟通,一封清晰、专业的邮件都能为你赢得更多机会。AokSend将为你详细介绍mathorcup发邮件的撰写技巧,帮助你在比赛…...

ESP01烧入AT出厂固件
ESP01是一种常见的WIFI模块,其核心是esp8266,常用于给主控拓展WIFI功能,因其体积较小、集成度高、造价便宜,常受到消费者喜爱,ESP01常用的开发方式有两种,一种是利用基于Arduino框架作为独立设备开发&#…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...