当前位置: 首页 > 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;实际上…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...