TypeScript栈的压入与弹出序列校验

目录
  • 前言
  • 思路分析
    • 弹出序列满足条件
    • 弹出序列不满足条件
  • 实现代码

前言

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

思路分析

仔细分析题目后,我们很直观的想法就是构造一个辅助栈,把压入序列中的数字依次压入该辅助栈。按照弹出序列的顺序依次从该栈中弹出数字,如果辅助栈被清空则代表此序列是它的一个弹出序列,否则就不可能是一个弹出序列。

弹出序列满足条件

如下图所示,它的压入过程为:

取出弹出序列的第1个元素,维护一个已取索引,在压入序列中从已取索引位置开始寻找与之相等的元素,将它之前的数字和其本身依次入栈,每取1个元素就将索引自增1次

  • 此时,栈顶元素与弹出序列的第1个元素相等,将栈顶元素出栈。

取出弹出序列的第2个元素,在压入序列中从已取索引位置开始寻找与之相等的元素,将它之前的数字和其本身依次入栈。

  • 此时,栈顶元素与弹出序列的第2个元素相等,将栈顶元素出栈。

取出弹出序列的第3个元素,此时,压入序列的元素已经被取完。我们继续判断 辅助栈中的元素是否与弹出序列的元素相等

  • 栈顶元素为3,要弹出的元素也是3,二者相等,栈顶元素出栈

取出弹出序列的第4个元素

  • 栈顶元素为2,要弹出的元素也是2,二者相等,栈顶元素出栈

取出弹出序列的第5个元素

  • 栈顶元素为1,要弹出的元素也是1,二者相等,栈顶元素出栈

弹出序列已取完,辅助栈已清空。 该弹出序列属于压入序列的一个弹出顺序

弹出序列不满足条件

接下来,我们来分析下它不是压入序列的弹出顺序的情况,它的压入过程与满足条件时一样,唯独不同的是,弹出序列的第3个元素从辅助栈出栈后,压入序列已经被取完。此时,弹出序列的第4个元素是1,辅助栈的栈顶元素是2,二者不等,那么该序列肯定不是压入序列的弹出顺序。

实现代码

经过上面的分析,我们已经知道了如何解决这个问题。思路已明确,接下来,我们就可以愉快的进入编码环节了

(0)

相关推荐

  • TypeScript之调用栈的实现

    本文介绍了TypeScript之调用栈,分享给大家,具体如下: class CallStackTool{ private static index:number = 0; public static printCallStack (count:number , simple: boolean = true):void { let caller:Function = arguments.callee.caller; let i:number = 0; count = count || 10; Ca

  • TypeScript中extends的正确打开方式详解

    目录 前言 extends第一式:继承 类继承类 接口继承接口 接口继承类 extends第二式:三元表达式条件判断 普通的三元表达式条件判断 情况一:Type1和Type2为同一种类型. 情况二:Type1是Type2的子类型. 情况三: Type2类型兼容类型Type1. 带有泛型的三元表达式条件判断 extends第三式:泛型约束 前言 最近完整地看了一遍TypeScript的官方文档,发现文档中有一些知识点没有专门讲解到,或者是讲解了但却十分难以理解,因此就有了这一系列的文章,我将对没有

  • TypeScript 的条件类型使用示例详解

    目录 TypeScript 的条件类型使用方式 条件类型和 keyof 组合 在条件返回中使用 T 在类型输出中使用 T 时的联合类型 使用条件类型推断类型 总结 TypeScript 的条件类型使用方式 我们可以使用 TypeScript 中的条件类型来根据逻辑定义某些类型,就像是在编写代码那样. 它采用的语法和我们在 JavaScript 中熟悉的三元运算符很像:condition ? ifConditionTrue : ifConditionFalse. 我们来看看他是怎么工作的. 假设我

  • TypeScript编写自动创建长度固定数组的类型工具详解

    目录 前言 代码 判断 List 的长度是否等于 Len 前言 在 TypeScript 中,当需要一个长度固定的数组时,通常会想到使用元组来进行表示,不过相对于数组而言,元组的每个元素的类型都不必是一致的. 如果现在需要一个长度为 30,元素类型为 string 的数组类型,其实就是一个元组,如果直接手写出来,那也太麻烦了,本文因此有感而发,编写了自动创建的类型工具. 代码 首先,不管三七二十一,先把这个类型工具给定义出来: type FixedArray = any 然后开始逐步分析,先从泛

  • TypeScript 泛型推断实现示例详解

    目录 前言 基础类型准备 最终使用的方式 基于Interface的实现 (失败了) 所有内容都基于type 实现 完整Demo 结束语 前言 最近做东西都在用ts,有时候写比较复杂的功能,如果不熟悉,类型写起来还是挺麻烦的.有这样一个功能,在这里,我们就不以我们现有的业务来举例了,我们还是已Animal举例,来说明场景.通过一个工厂来创建不同的动物实例.在这里我们借助泛型来实现类型的约束和动态推到指定类型. 基础类型准备 用一个枚举来定义Animal的类型 enum EAnimalType {

  • TypeScript新语法之infer extends示例详解

    目录 正文 模式匹配 提取枚举的值的类型 总结 正文 我们知道,TypeScript 支持 infer 来提取类型的一部分,通过模式匹配的方式. 模式匹配 比如元组类型提取最后一个元素的类型: type Last<Arr extends unknown[]> = Arr extends [...infer rest,infer Ele] ? Ele : never; 比如函数提取返回值类型: type GetReturnType<Func extends Function> = F

  • TypeScript顺时针打印矩阵实现实例详解

    目录 前言 梳理思路 实现代码 示例代码 前言 有一个矩阵,如何按照从外向里以顺时针的顺序依次打印出每一个元素?本文将跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 梳理思路 当我们遇到一个复杂的问题时,可以通过举例将它画出来,这样就可以更直观的发现规律.那么我们就先构造一个矩阵出来,如下所示: const matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ]; 顺时针访问一个矩阵,那么它的访

  • TypeScript栈的压入与弹出序列校验

    目录 前言 思路分析 弹出序列满足条件 弹出序列不满足条件 实现代码 前言 有两个整数序列,第一个序列表示栈的压入顺序,判断第二个序列是否为该栈的弹出顺序.假设压入栈的数字均不相等.例如,序列[1, 2, 3, 4, 5]是某栈的压栈序列,序列[4, 5, 3, 2, 1]是该栈序列对应的一个弹出序列,但[4, 3, 5, 1, 2]就不可能是该压栈序列的弹出序列. 思路分析 仔细分析题目后,我们很直观的想法就是构造一个辅助栈,把压入序列中的数字依次压入该辅助栈.按照弹出序列的顺序依次从该栈中弹

  • js鼠标滑过弹出层的定位IE6bug解决办法

    大家在写div+css的时候经常会用到弹出层,由于IE6的bug,所以当使用多个标签重复写弹出层的时候会遇到后面的层压在了弹出层的上面,这种问题在火狐浏览器下可以用z-index来解决,但是在IE6下面是不起作用的,下面的代码给大家提供了一种此类问题的解决办法,原理如下:用Jquery给弹出层的z轴依次增加高度.代码很简单,效果很显著,吼吼! 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN&q

  • php array_push()数组函数:将一个或多个单元压入数组的末尾(入栈)

    复制代码 代码如下: <?php /*函数array_push():将一个或多个单元压入数组的末尾(入栈) * 1.语法:int array_push ( array &array, mixed var [, mixed ...] ) * 2.描述:将 array 当成一个栈,并将传入的变量压入 array 的末尾.array 的长度将根据入栈变量的数目增加. * 3.注意事项: * 3.1.该函数返回数组新的元素的总数 * 3.2.如var为数组,则该数组是作为一个数组变量入栈到数组栈中,

  • php array_pop()数组函数将数组最后一个单元弹出(出栈)

    复制代码 代码如下: <?php /*函数array_pop():将数组最后一个单元弹出(出栈) * 1.语法:mixed array_pop ( array &array ) * 2.描述: 弹出并返回 array 数组的最后一个单元,并将数组 array 的长度减一.如果 array 为空(或者不是数组)将返回 NULL. * 3.注意事项: * 3.1. */ echo "****************************************************

  • iOS开发中ViewController的页面跳转和弹出模态

    ViewController 页面跳转 从一个Controller跳转到另一个Controller时,一般有以下2种: 1.利用UINavigationController,调用pushViewController,进行跳转:这种采用压栈和出栈的方式,进行Controller的管理.调用popViewControllerAnimated方法可以返回. 复制代码 代码如下: PickImageViewController *ickImageViewController = [[PickImageV

  • PL/SQL Dev连接Oracle弹出空白提示框的解决方法分享

    没办法,只能自己研究,经过大概一天时间吧,还是搞好了,写个总结. 出现这种问题,解决方法大概有这几种: 1.权限不够,导致弹出空吧提示框.(直接上链接) http://jingyan.baidu.com/article/066074d6760959c3c21cb0d6.html 就PL/SQL图标上点右键---属性---兼容性--管理员身份运行此程序的勾打上,即可 2.环境变量没设对. ①在安装oracle服务器的机器上搜索下列文件,oci.dllocijdbc10.dll(其中10代表orac

  • IOS开发仿微信右侧弹出视图实现

    IOS开发仿微信右侧弹出视图实现 微信首页的+号,点击之后会弹出一个更多的视图,这个视图如何实现呢? 实现该效果可能需要以下技术要点: 1.图片拉伸,通过拉伸图片的中间的较小区域来保持图片的边上的形状 2.仿射变换,用到仿射变换的缩放,平移和合并,视图动画 3.navigationBar的样式设置 实现效果,如下: 本Demo图片来源微信安装包解压得到的图片 实现代码: // // ViewController.m // appXX-微信更多工具栏 // // Created by MRBean

  • jquery 弹出层注册页面等(asp.net后台)

    [一]需求如下: 1:注册不新开页面,改成弹出层, 2:新增用户买房欲望调查, 3:用户名自动检索出推荐的用户名, 4:出生日期用户输入改成控件选择. 5:尽力提高用户体验,吸引用户注册. [二]无图无真相. 1:简化后的页面: 2:浮出文字提示和圆角边框: 3:支持民意调查(异步提交) 4:自动检索推荐用户名(测试数据) 5:数据有效性验证 6:日历 7:支持拖拽 8:滑入显示 9:over [三]代码分析1.弹出层的制作, a.先引用这三个: 复制代码 代码如下: <script src=&qu

  • 使用jQuery实现页面定时弹出广告效果

    1.JQuery效果 2.步骤分析: 第一步:引入jQuery相关的文件 第二步:书写页面加载函数 第三步:在页面加载函数中,获取显示广告图片的元素. 第四步:设置定时操作(显示广告图片的函数) 第五步:在显示广告图片的函数中,使用jQuery的方法让广告图片显示(show()) 第六步:清除显示广告图片的定时操作 第七步:设置定时操作(隐藏广告图片的函数) 第八步:在隐藏广告图片的函数中,使用jQuery的方法让广告图片隐藏(hide()) 第九步:清除隐藏广告图片的定时操作 <script

  • javascript 控制弹出窗口

    前言:经常上网的朋友可能会到过这样一些网站,一进入首页立刻会弹出一个窗口,或者按一个连接或按钮弹出,通常在这个窗口里会显示一些注意事项.版权信息   .警告.欢迎光顾之类的话或者作者想要特别提示的信息.其实制作这样的页面效果非常的容易,只要往该页面的HTML里加入几段javascript代码即可实现.下面我就带您剖析它的奥秘.    [1.最基本的弹出窗口代码]                <SCRIPT   LANGUAGE="javascript">        

随机推荐