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

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...