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

Leetcode-每日一题【剑指 Offer 31. 栈的压入、弹出序列】

题目

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

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

提示:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed 是 popped 的排列。

解题思路

1.题目要求我们判断栈的弹出顺序是否是所给两个整数序列,对于这道题我们需要设置一个辅助栈来帮助我们。还需要一个变量k来指向我们的出栈元素,方便我们读取。

2.举个例子:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

我们先按入栈顺序入栈第一个元素1

  

然后判断stack当前的栈顶元素是否等于k指向的出栈顺序的元素,若不等于我们就继续入栈

 再次判断stack当前的栈顶元素是否等于k指向的出栈顺序的元素,不等于我们继续入栈

 stack当前的栈顶元素依旧不等于k指向的出栈顺序的元素,我们继续入栈

  此时我们可以看到 stack当前的栈顶元素等于k指向的出栈顺序的元素,我们就将Stack的栈顶元素出栈,并将 k 后移。

这时 stack当前的栈顶元素不等于k指向的出栈顺序的元素,我们继续按照入栈顺序继续入栈

再次将 stack当前的栈顶元素与k指向的出栈顺序的元素进行判断,发现两者相等,我们就将栈顶元素进行出栈,并且将k后移

出栈

 

出栈

 

出栈

 

此时我们发现stack栈空了,那就证明所给的出栈顺序是正确的。

3.本体的主要思想就是,我们需要查看栈顶元素是否与出栈顺序所对应的元素相等,若相等就出栈,若不等就继续按照入栈顺序入栈,如果所有的操作结束后栈为空,就证明所给顺序正确,否则就代表所给顺序有误。 

代码实现

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {//判断所给序列是否为空if(pushed == null || pushed.length == 0){return true;}//设置一个辅助栈Stack<Integer> stack = new Stack();int k = 0;for(int i = 0; i < pushed.length; i++){stack.push(pushed[i]);while(!stack.isEmpty() && stack.peek() == popped[k]){stack.pop();k++;} }return stack.isEmpty();}
}

测试结果

 

相关文章:

Leetcode-每日一题【剑指 Offer 31. 栈的压入、弹出序列】

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

软件需求-架构师之路(五)

软件需求 软件需求&#xff1a; 指用户 对系统在功能、行为、性能、设计约束等方面的期望。 分为 需求开发 和 需求管理 两大过程。 需求开发&#xff1a; 需求获取需求分析需求定义&#xff08;需求规格说明书&#xff09;需求验证&#xff1a;拉客户一起评审&#xff0c…...

Python自带的IDLE有什么用

在Python的官方解释器中&#xff0c;自带了一个名为IDLE(Interactive DeveLopment Environment)的集成开发环境。 一、简化代码调试过程 很多初学者在编写Python代码时&#xff0c;经常会遇到一些问题需要调试。而在IDLE中&#xff0c;我们可以通过设置断点、单步调试等方法&…...

设计模式之简单工厂模式

一、概述 定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂模式使一个类的实例化延迟到其子类。 简单工厂模式&#xff1a;又叫做静态工厂方法模式&#xff0c;是由一个工厂对象决定创建出哪一种产品类的实例。 二、适用性 1.当一个类不知道它所必须…...

从SaaS到RPA,没有真正“完美”的解决方案!

众所周知&#xff0c;SaaS行业越来越卷&#xff0c;利润也越来越“薄”&#xff0c;这是传统软件厂商的悲哀&#xff0c;也是未来数字化行业不得不面对的冷峻现状之一。 随着基于aPaaS、低代码的解决方案之流行&#xff0c;SaaS行业变得越来越没有技术门槛&#xff0c;IT人员的…...

miniconda克隆arcpy

arcpy环境克隆 前言尝试思考到此结束 前言 最近遇到了一些问题&#xff0c;需要用到arcpy来处理一些东西&#xff0c;但众所周知&#xff0c;arcgis的arcpy是python 2.0的&#xff0c;我不是很喜欢&#xff1b;所以我安装了arcgis pro 2.8&#xff0c;我发现这也是个坑&#x…...

一万字关于java数据结构堆的讲解,让你从入门到精通

目录 java类和接口总览 队列(Queue) 1. 概念 2. 队列的使用 以下是一些常用的队列操作&#xff1a; 1.入队操作 2.出队操作 3.判断队列是否为空 4.获取队列大小 5.其它 优先级队列(堆) 1. 优先级队列概念 Java中的PriorityQueue具有以下特点 2.常用的PriorityQue…...

Java集合底层源码剖析-ArrayList和LinkedList

文章目录 ArrayList基本原理优缺点核心方法的原理数组扩容以及元素拷贝LinkedList基本原理优缺点双向链表数据结构插入元素的原理获取元素的原理删除元素的原理Vector和Stack栈数据结构的源码剖析ArrayList 基本原理 ArrayList是Java中的一个非常常用的数据结构,它实现了Lis…...

【数据分享】2006-2021年我国城市级别的市政公用设施建设固定资产投资相关指标(30多项指标)

《中国城市建设统计年鉴》中细致地统计了我国城市市政公用设施建设与发展情况&#xff0c;在之前的文章中&#xff0c;我们分享过基于2006-2021年《中国城市建设统计年鉴》整理的2006—2021年我国城市级别的市政设施水平相关指标&#xff08;可查看之前的文章获悉详情&#xff…...

学点Selenium玩点新鲜~,让分布式测试有更多玩法

前 言 我们都知道 Selenium 是一款在 Web 应用测试领域使用的自动化测试工具&#xff0c;而 Selenium Grid 是 Selenium 中的一大组件&#xff0c;通过它能够实现分布式测试&#xff0c;能够帮助团队简单快速在不同的环境中测试他们的 Web 应用。 分布式执行测试其实并不是一…...

【SpringBoot学习笔记】04. Thymeleaf模板引擎

模板引擎 所有的html元素都可以被thymeleaf替换接管 th:元素名 templates下的只能通过Controller来跳转&#xff0c;templates前后端分离&#xff0c;需要模板引擎thymeleaf支持 模板引擎的作用就是我们来写一个页面模板&#xff0c;比如有些值呢&#xff0c;是动态的&#x…...

【uni-app】 .sync修饰符与$emit(update:xxx)实现数据双向绑定

最近在看uni-app文档&#xff0c;看到.sync修饰符的时候&#xff0c;觉得很有必要记录一下 其实uni-app是一个基于Vue.js和微信小程序开发框架的跨平台开发工具 所以经常会听到这样的说法&#xff0c;只要你会vue&#xff0c;uni-app就不难上手 在看文档的过程中&#xff0c;发…...

链表之第二回

欢迎来到我的&#xff1a;世界 该文章收入栏目&#xff1a;链表 希望作者的文章对你有所帮助&#xff0c;有不足的地方还请指正&#xff0c;大家一起学习交流 ! 目录 前言第一题&#xff1a;反转一个链表第二题&#xff1a;链表内指定区间反转第三题&#xff1a;判断一个链表…...

【sgDragSize】自定义拖拽修改DIV尺寸组件,适用于窗体大小调整

核心原理就是在四条边、四个顶点加上透明的div&#xff0c;给不同方向提供按下移动鼠标监听 &#xff0c;对应计算宽度高度、坐标变化 特性&#xff1a; 支持设置拖拽的最小宽度、最小高度、最大宽度、最大高度可以双击某一条边&#xff0c;最大化对应方向的尺寸&#xff1b;再…...

Gson与FastJson详解

Gson与FastJson详解 Java与JSON 做什么? 将Java中的对象 快速的转换为 JSON格式的字符串. 将JSON格式的字符串, 转换为Java的对象. Gson 将对象转换为JSON字符串 转换JSON字符串的步骤: 引入JAR包 在需要转换JSON字符串的位置编写如下代码即可: String json new Gson().to…...

LeetCode150道面试经典题-- 有效的字母异位词(简单)

1.题目 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 2.示例 s"adasd" t"daads" 返回true s"addad" t &q…...

前端与人工智能

前端开发与人工智能的结合在未来将会产生许多有趣和有前景的发展。以下是前端与人工智能结合可能带来的一些趋势和前景&#xff1a; 智能用户体验&#xff1a;人工智能可以用于改善用户体验&#xff0c;例如通过个性化推荐、情感分析等技术来提供更贴近用户需求的内容和功能。…...

神经网络基础-神经网络补充概念-14-逻辑回归中损失函数的解释

概念 逻辑回归损失函数是用来衡量逻辑回归模型预测与实际观测之间差异的函数。它的目标是找到一组模型参数&#xff0c;使得预测结果尽可能接近实际观测。 理解 在逻辑回归中&#xff0c;常用的损失函数是对数似然损失&#xff08;Log-Likelihood Loss&#xff09;&#xff…...

UG NX二次开发(C++)-PK函数创建一条圆弧曲线

文章目录 1、前言2、创建一个项目3、添加头文件4、在do_it中添加创建圆曲线的源代码5、调用dll6、再创建一个长方体验证1、前言 采用PK进行UG NX二次开发,现在看到的文章很多是直接创建实体,然后在UG NX的视图区显示出来,对于创建圆曲线的文章不多,本文讲一下PK函数创建圆…...

AndroidStudio中修改打包生成的apk名称

1.配置手机架构 splits {abi {enable truereset()include armeabi-v7a,arm64-v8auniversalApk false} } 2.多渠道 productFlavors {normal {applicationId "*****"manifestPlaceholders [appName: "string/app_name_normal"]}driver {applicationId &qu…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

StarRocks 全面向量化执行引擎深度解析

StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计&#xff0c;相比传统行式处理引擎&#xff08;如MySQL&#xff09;&#xff0c;性能可提升 5-10倍。以下是分层拆解&#xff1a; 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...

Jmeter(四) - 如何在jmeter中创建网络测试计划

1.简介 如何创建基本的 测试计划来测试网站。您将创建五个用户&#xff0c;这些用户将请求发送到JMeter网站上的两个页面。另外&#xff0c;您将告诉用户两次运行测试。 因此&#xff0c;请求总数为&#xff08;5个用户&#xff09;x&#xff08;2个请求&#xff09;x&#xff…...