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框架作为独立设备开发&#…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...

LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

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、一个结构体实现多…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...