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

03.01、三合一

03.01、[简单] 三合一

1、题目描述

三合一。描述如何只用一个数组来实现三个栈。

你应该实现push(stackNum, value)pop(stackNum)isEmpty(stackNum)peek(stackNum)方法。stackNum表示栈下标,value表示压入的值。

构造函数会传入一个stackSize参数,代表每个栈的大小。

2、方法思路

  1. 数组表示栈:我们可以使用一个数组 arr 来表示三个栈。数组被划分为三个部分,每部分存储一个栈的元素。栈 1 的索引范围是 [0, stackSize-1],栈 2 的范围是 [stackSize, 2*stackSize-1],栈 3 的范围是 [2*stackSize, 3*stackSize-1]
  2. 辅助指针数组:用一个长度为 3 的数组 tops,存储每个栈的栈顶索引(即当前元素的存储位置),通过栈的编号 stackNum 来访问对应的栈。
  3. 操作限制
    • 在进行 push 操作时,需要检查栈是否已经满了。
    • poppeek 操作在栈为空时应返回 -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、时间复杂度

  • pushpoppeekisEmpty 操作的时间复杂度均为 O(1),因为每次操作只需更新栈指针或访问数组中的一个元素。

这个解决方案使用了固定大小的数组来实现三个栈的分隔,逻辑简单且效率高。在面试中这是一个常见的问题,考察你对栈和数组的理解,以及如何在限制条件下实现数据结构。

相关文章:

03.01、三合一

03.01、[简单] 三合一 1、题目描述 三合一。描述如何只用一个数组来实现三个栈。 你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标&#xff0c;value表示压入的值。 构造函数会传入一个stackSize参数&#xf…...

github上clone代码过程

从 GitHub 上拉取代码的过程非常简单&#xff0c;一般通过 git clone 命令来完成。以下是详细步骤&#xff1a; 下载git工具 要下载并安装 Git&#xff0c;你可以根据你的操作系统来选择相应的步骤。以下是如何在不同操作系统上安装 Git 的详细说明&#xff1a; 1. 在 Windo…...

ChatGLM3模型搭建教程

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

多层建筑能源参数化模型和城市冠层模型的区别

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

27. Redis并发问题

1. 前言 对于一个在线运行的系统,如果需要修改数据库已有数据,需要先读取旧数据,再写入新数据。因为读数据和写数据不是原子操作,所以在高并发的场景下,关注的数据可能会修改失败,需要使用锁控制。 2. 分布式场景 2.1 分布式锁场景 面试官提问: 为什么要使用分布式锁?…...

JVM四种垃圾回收算法以及G1垃圾回收器(面试)

JVM 垃圾回收算法 标记清除算法&#xff1a;标记清除算法将垃圾回收分为两个阶段&#xff1a;标记阶段和清除阶段。 在标记阶段通过根节点&#xff0c;标记所有从根节点开始的对象。然后&#xff0c;在清除阶段&#xff0c;清除所有未被标记的对象 适用场合&#xff1a; 存活对…...

Python 数学建模——Vikor 多标准决策方法

文章目录 前言原理步骤代码实例 前言 Vikor 归根到底其实属于一种综合评价方法。说到综合评价方法&#xff0c;TOPSIS&#xff08;结合熵权法使用&#xff09;、灰色关联度分析、秩和比法等方法你应该耳熟能详。Vikor 未必比这些方法更出色&#xff0c;但是可以拓展我们的视野。…...

计算机网络八股总结

这里写目录标题 网络模型划分&#xff08;五层和七层&#xff09;及每一层的功能五层网络模型七层网络模型&#xff08;OSI模型&#xff09; 三次握手和四次挥手具体过程及原因三次握手四次挥手 TCP/IP协议组成UDP协议与TCP/IP协议的区别Http协议相关知识网络地址&#xff0c;子…...

AMD CMD UMD CommonJs ESM 的历史和区别

这几个东西都是用于定义模块规范的。有些资料会提及到这些概念&#xff0c;不理清楚非常容易困惑。 ESM&#xff08;ES Module&#xff09; 这个实际上我们是最熟悉的&#xff0c;就是ES6的模块功能。出的最晚&#xff0c;因为是官方出品&#xff0c;所以大势所趋&#xff0c…...

人工智能数据基础之微积分入门-学习篇

目录 导数概念常见导数和激活导数python代码绘制激活函数微分概念和法则、积分概念微积分切线切面代码生成案例链式求导法则反向传播算法(重要) 一、概念 二、常见导数及激活导数 常见激活函数及其导数公式&#xff1a; 在神经网络中&#xff0c;激活函数用于引入非线性因素&…...

【PSINS】ZUPT代码解析(PSINS_SINS_ZUPT)|MATLAB

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

多态(上)【C++】

文章目录 多态的概念多态的实现多态产生的条件什么是虚函数&#xff1f;虚函数的重写和协变重写协变 析构函数的重写为什么有必要要让析构函数构成重写&#xff1f; 多态的概念 C中的多态是面向对象编程&#xff08;OOP&#xff09;的一个核心特性&#xff0c;指的是同一个接口…...

如何驱动一枚30年前的音源芯片,YMF288驱动手记 Part2

一些问题 在上一篇里面虽然策划了想要驱动YMF288所需要做的事情以及目标。但是&#xff0c;在板子打出来后&#xff0c;我在进一步的研究中&#xff0c;发现我犯了个错误&#xff0c;那就是YMF288并不是使用现在很多轻量化的嵌入式&#xff0c;比如ESP32常用的I2S协议的&#x…...

yarn webpack脚手架 react+ts搭建项目

安装 Yarn 首先&#xff0c;确保你已经安装了 Node.js 和 Yarn。如果还没有安装 Yarn&#xff0c;可以通过以下命令安装&#xff1a; npm install -g yarn创建项目 使用 create-react-app 脚手架创建一个带有 TypeScript 的项目&#xff0c;node更新到最新版&#xff0c;并指定…...

防蓝光护眼灯有用吗?五款防蓝光效果好的护眼台灯推荐

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

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 是一种结合开发&#xff08;Development&#xff09;与运维&#xff08;Operations&#xff09;的方法论&#xff0c;旨在通过工具和文化变革&#xff0c;促进软件开发和运维之间的协作&#xff0c;提升软件交付的效率、质量和稳定性。…...

单体架构系统是不是已经彻底死亡?

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

mathorcup发邮件:参赛必看邮件撰写技巧?

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

ESP01烧入AT出厂固件

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

23-Oracle 23 ai 区块链表(Blockchain Table)

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

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的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 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...