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

Java栈的压入、弹出序列(详解)

目录

1.题目描述

2.题解

方法1

方法2


1.题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例: 

输入:[1,2,3,4,5],[4,5,3,2,1]

返回:true

输入:[1,2,3,4,5],[4,3,5,1,2]

返回:false

2.题解

方法1

思路分析:

判断两个序列是否符合入栈、出栈的次序,我们可以使用一个栈来模拟。

入栈:栈顶元素不等于出栈序列当前元素

出栈:栈顶元素等于出栈序列当前元素

具体过程:

 具体实现:

1.创建一个栈,来模拟入栈、出栈次序

2.使用i、j来遍历pushV、popV数组,i < pushV.length,入栈

3.栈顶元素等于popV数组当前元素时,出栈

4.遍历完pushV数组后,判断栈是否为空,栈为空,弹出序列为正确的出栈顺序;反之,则为错误的出栈顺序

代码实现:

public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);//判断是否有元素出栈while(j < popV.length && !stack.empty()){int k = stack.peek();if(k == popV[j]){stack.pop();j++;}else{break;}}}return stack.empty();}
}

 

方法2

思路分析:

由于数组本身就可用于实现栈,我们可以将pushV数组当作栈,使用p来标记栈顶,

入栈:pushV[p](栈顶元素)不等于当前出栈数组中元素,p++(入栈)

出栈:pushV[p](栈顶元素)等于当前出栈数组中元素,p--(出栈)

具体过程:

具体实现:

1.使用p来标识栈顶元素

2.使用i、j来遍历pushV、popV数组,pushV[p](栈顶元素)不等于当前出栈数组中元素,

pushV[p] = pushV[i],p++

3.pushV[p](栈顶元素)等于当前出栈数组中元素,p--

4.遍历完pushV数组后,判断p的大小,若p为0,则表示所有元素都已出栈,出栈序列为正确的出栈顺序,返回true,否则,返回false

代码实现:

public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {int p = 0;//标识栈顶int j = 0;//出栈序列下标for(int n : pushV){pushV[p] = n;while( p>=0 && j < popV.length && pushV[p] == popV[j]){j++;p--;}p++;}return p==0;}
}

题目来自:

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

相关文章:

Java栈的压入、弹出序列(详解)

目录 1.题目描述 2.题解 方法1 方法2 1.题目描述 输入两个整数序列&#xff0c;第一个序列表示栈的压入顺序&#xff0c;请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序&#xff0c;序列4,5,3,2,1是该压栈序…...

RabbitMQ学习笔记(消息发布确认,死信队列,集群,交换机,持久化,生产者、消费者)

MQ&#xff08;message queue&#xff09;&#xff1a;本质上是个队列&#xff0c;遵循FIFO原则&#xff0c;队列中存放的是message&#xff0c;是一种跨进程的通信机制&#xff0c;用于上下游传递消息。MQ提供“逻辑解耦物理解耦”的消息通信服务。使用了MQ之后消息发送上游只…...

PyTorch - 模型训练损失 (Loss) NaN 问题的解决方案

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/133378367 在模型训练中&#xff0c;如果出现 NaN 的问题&#xff0c;严重影响 Loss 的反传过程&#xff0c;因此&#xff0c;需要加入一些微小值…...

8、Nacos服务注册服务端源码分析(七)

本文收录于专栏 Nacos 中 。 文章目录 前言确定前端路由CatalogController.listDetail()ServiceManager总结 前言 前文我们分析了Nacos中客户端注册时数据分发的设计链路&#xff0c;本文根据Nacos前端页面请求&#xff0c;看下前端页面中的服务列表的数据源于哪里。 确定前端…...

MySQL使用Xtrabackup在线做主从

1、主库上操作 1.1前提 172.16.11.2&#xff08;主库&#xff09; 172.16.11.4&#xff08;从库&#xff09; 在执行备份之前&#xff0c;确保数据库没有锁定&#xff0c;以避免备份期间的任何写操作。 确保主库上的 MySQL 服务器正在运行&#xff0c;以便备份数据的一致性。…...

scala基础入门

一、Scala安装 下载网址&#xff1a;Install | The Scala Programming Language ideal安装 &#xff08;1&#xff09;下载安装Scala plugins &#xff08;2&#xff09;统一JDK环境&#xff0c;统一为8 &#xff08;3&#xff09;加载Scala &#xff08;4&#xff09;创建工…...

【Java-LangChain:面向开发者的提示工程-5】推断

第五章 推断 推断任务可以看作是模型接收文本作为输入&#xff0c;并执行某种分析的过程。其中涉及提取标签、提取实体、理解文本情感等等。如果你想要从一段文本中提取正面或负面情感&#xff0c;在传统的机器学习工作流程中&#xff0c;需要收集标签数据集、训练模型、确定如…...

【C++】手撕vector(vector的模拟实现)

手撕vector目录&#xff1a; 一、基本实现思路方针 二、vector的构造函数剖析&#xff08;构造歧义拷贝构造&#xff09; 2.1构造函数使用的歧义问题 2.2 vector的拷贝构造和赋值重载&#xff08;赋值重载不是构造哦&#xff0c;为了方便写在一起&#xff09; 三、vector的…...

智能指针那些事

​《Effective Modern C》学习笔记之条款二十一&#xff1a;优先选用std::make_unique和std::make_shared,而非直接new - 知乎...

Fiddler抓取手机https包的步骤

做接口测试时&#xff0c;有时我们需要使用fiddler进行抓包分析&#xff0c;那么如何抓取https包。主要分为以下七步&#xff1a; 1.设置fiddler选项&#xff1a;Tools->Options,按如下图勾选 2.下载并安装Fiddler证书生成器 下载地址&#xff1a;http://www.telerik.com/…...

idea没有maven工具栏解决方法

背景&#xff1a;接手的一些旧项目&#xff0c;有pom文件&#xff0c;但是用idea打开的时候&#xff0c;没有认为是maven文件&#xff0c;所以没有maven工具栏&#xff0c;不能进行重新加载pom文件中的依赖。 解决方法&#xff1a;选中pom.xml文件&#xff0c;右键 选择添加为…...

levelDB引擎

一、背景 1.1、影响磁盘性能的因素&#xff1a; 主要受限于磁盘的寻道时间&#xff0c;优化磁盘数据访问的方法是尽量减少磁盘的IO次数。磁盘数据访问效率取决于磁盘IO次数&#xff0c;而磁盘IO次数又取决于数据在磁盘上的组织方式。磁盘数据存储大多采用B树类型数据结构&…...

IM同步服务

设计概述 后台同步方案的设计就是数据存储结构的设计&#xff0c;如何快速体现“信息变化”&#xff0c;如何快速计算出“变化信息”。后台数据存储结构是由同步协议中同步契约决定的。 设计方案 该方案的同步是按照业务粒度来划分&#xff0c;只需要同步sdk要求同步的数据。…...

MySQL 运维常用脚本

常用功能脚本 1.导出整个数据库 mysqldump -u 用户名 -p –default-character-setlatin1 数据库名 > 导出的文件名(数据库默认编码是latin1) mysqldump -u wcnc -p smgp_apps_wcnc > wcnc.sql 2.导出一个表 mysqldump -u 用户名 -p 数据库名 表名> 导出的文件…...

ABC322刷题记

ABC322刷题记 T1.A A - First ABC 2。 妥妥的简单题…… 用find函数做就行。&#xff08;如果不存在那个子串就返回-1&#xff0c;否则返回第一次出现位置&#xff09; 注意题目中编号是从1开始的。 时间复杂度&#xff1a;O(log(n))。find函数有一定代价&#xff0c;我记…...

visual studio的安装及scanf报错的解决

visual studio是一款很不错的c语言编译器 下载地址&#xff1a;官网 点击后跳转到以下界面 下滑后点击下载Vasual Sutdio&#xff0c;选择社区版即可 选择位置存放下载文件后&#xff0c;即可开始安装 安装时会稍微等一小会儿。然后会弹出这个窗口&#xff0c;我们选择安装位…...

React生命周期

React的生命周期主要是指React组件从创建到销毁的过程&#xff0c;包括三个阶段&#xff1a;挂载期&#xff08;实例化期&#xff09;、更新期&#xff08;存在期&#xff09;、卸载期&#xff08;销毁期&#xff09; 挂载期&#xff1a; constructor&#xff08;props&#…...

SpringBoot整合RocketMQ笔记

SpringBoot版本为2.3.12.Release RocketMQ对比kafka 学习链接 https://zhuanlan.zhihu.com/p/335216381 代码实战 https://www.cnblogs.com/RedOrange/p/17401238.html Centos安装rocketmq https://blog.csdn.net/chuige2013/article/details/123783612 RocketMQ详细配置与…...

【【萌新的RiscV学习之在写代码之前对于关键路径的分析-11】】

萌新的RiscV学习之在写代码之前对于关键路径的分析-11 首先我们最简单的control 模块 全分段 因为只有分段 &#xff0c; 分开使用之后 &#xff0c; 各个阶段的具体功能才会合理使用 就像是为了后续 “气泡” 赋值 为 0 还有单独比较前递这种 EX &#xff1a; ALUOP ALUSrc …...

A. Sequence with Digits

题目&#xff1a;样例&#xff1a; 输入 8 1 4 487 1 487 2 487 3 487 4 487 5 487 6 487 7输出 42 487 519 528 544 564 588 628 思路&#xff1a; 暴力模拟题&#xff0c;看这数据范围&#xff0c;有些人可能会被唬住&#xff0c;以为是高精度或者容易超时&#xff0c;实际上…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

稳定币的深度剖析与展望

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

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

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

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

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、写…...