最近做阿里的笔试题,美团的笔试题都出现了栈的顺序的问题。

2024-09-06 06:32

本文主要是介绍最近做阿里的笔试题,美团的笔试题都出现了栈的顺序的问题。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述:   已知abcdef,依次入栈,在栈中可停留也可出栈,求下面哪个出栈的顺序不正确?或者有多少种出栈的顺序?

f(0):1

f(1):1

f(2):2

f(3):5

f(4):14

f(5):42

f(6):132

所以对于abcdef共有132种顺序

一:对于出栈的顺序

A:fedcba
B:dcbaef  // abcd入栈,dcba依次出栈,e入栈,e出栈,f入栈,
C:edcbaf  // abcde入栈,edcba依次出栈,f入栈,f出栈
D:dbcaef   

对于这样的题,也不是无规律可循,主要就是满足三个条件:

1、在原序列中相对位置比它小的,必须是逆序;
2、在原序列中相对位置比它大的,顺序没有要求;
3、以上两点可以间插进行。

这三个条件咋一看,比较蒙,那么我们就举例来看:

第一个选项

当f第一个出栈时,在原序列中相对位置比它小的,是abcde,他们在这个f之后的出栈中是否是abcde相反的呢?edcba满足条件
当e第二个出栈,在原序列中相对位置比它小的,是abcd,他们在e出栈之后的出栈中是否是abcd相反的呢?dcba满足条件
当d第三个出栈,在原序列中相对位置比它小的,是abc,他们在d出栈之后的出栈中是否是abc相反的呢?cba满足条件
……

第二个选项

当d第一个出栈,在原序列中相对位置比它小的是abc,abc三个元素在d出栈之后的出栈中是否是相反排序的呢?cba满足
当c第二个出栈,在原序列中相对位置比它小的是ab,ab二个元素在c出栈之后的出栈中是否是相反排序的呢?ba满足
当b第三个出栈,在原序列中相对位置比它小的是a,a一个元素在b出栈之后的出栈中是否是相反排序的呢?a满足
当a第四个出栈,在原序列中没有比a更小的啦,所以满足条件。
当e第五个出栈,在原序列中相对位置比它小的是abcd,abcd四个元素在d出栈之后的出栈中是否是相反排序的呢?由于e之后只有f,因此满足条件

第三个选项

当e第一个出栈,在原序列中相对位置比它小的是abcd,abcd四个元素在e出栈之后的出栈中是否是相反排序的呢?dcba满足
当d第二个出栈,在原序列中相对位置比它小的是abc,abc三个元素在d出栈之后的出栈中是否是相反排序的呢?cba满足
当c第三个出栈,在原序列中相对位置比它小的是ba,ba二个元素在c出栈之后的出栈中是否是相反排序的呢?ba满足
当b第四个出栈,在原序列中相对位置比它小的是a,a一个元素在b出栈之后的出栈中是否是相反排序的呢?a满足
当a第五个出栈,在原序列中没有比a更小的了,所以满足条件

第四个选项

当d第一个出栈,在原序列中相对位置比它小的是abc,abc三个元素在b出栈之后的出栈中是否是相反排序的呢?bca不满足


二:对于有多少种出栈的顺序

n个元素进栈,共有多少种出栈顺序?

1.基于栈的问题分析

我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:

                                  f(1) = 1     //即 1

                                     f(2) = 2     //即 12、21

                                     f(3) = 5     //即 123、132、213、321、231


然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。

分析:


1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);

2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2),     根据乘法原理,一共的顺序个数为f(1) * f(2);

3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),

    根据乘法原理,一共的顺序个数为f(2) * f(1);

4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即f(3);


结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:

f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0) 


然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)


 



但这只是一个递推公式(若编程实现,需要维护一个一维数组,时间复杂度为O(n^2))。怎么把它转化为通项公式呢,复杂度仅为O(1)?

2. 相关的求解方法

(1)非常规数值分析

对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。

在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。

不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。

因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。

显然,不符合要求的方案数为c(2n,n+1)。

      由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)。其中,n为节点的个数。

(2)从图像上分析

事实上,可以认为问题是,任意两种操作,要求每种操作的总次数一样,且进行第k次操作2前必须先进行至少k次操作1。我们假设一个人在原点,操作1是此人沿右上角45°走一个单位(一个单位设为根号2,这样他第一次进行操作1就刚好走到(1,1)点),操作2是此人沿右下角45°走一个单位。第k次操作2前必须先进行至少k次操作1,就是说明所走出来的折线不能跨越x轴走到y=-1这条线上!在进行n次操作1和n此操作2后,此人必将到到达(2n,0)!若无跨越x轴的限制,折线的种数将为C(2n,n),即在2n次操作中选出n次作为操作1的方法数。

折线法

现在只要减去跨越了x轴的情况数。对于任意跨越x轴的情况,必有将与y=-1相交。找出第一个与y=-1相交的点k,将k点以右的折线根据y=-1对称(即操作1与操作2互换了)。可以发现终点最终都会从(2n,0)对称到(2n,-2)。由于对称总是能进行的,且是可逆的。我们可以得出所有跨越了x轴的折线总数是与从(0,0)到(2n,-2)的折线总数。而后者的操作2比操作1要多0-(-2)=2次。即操作1为n-1,操作2为n+1。总数为C(2n,n-1)。(此处类似于上面的数值角度分析)

折线法

(3)卡特兰数介绍

令h(0)=1,h(1)=1,catalan数满足递推式[1]

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

 

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)

3.类似的问题

(1)买票找零

有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)

(2)一个有n个1和n个-1组成的字串,且前k个数的和均不小于0,那这种字串的总数为多少?

(3)饭后,姐姐洗碗,妹妹把姐姐洗过的碗一个一个地放进碗橱摞成一摞。一共有n个不同的碗,洗前也是摞成一摞的,也许因为小妹贪玩而使碗拿进碗橱不及时,姐姐则把洗过的碗摞在旁边,问:小妹摞起的碗有多少种可能的方式?

最终结果:C(2n,n)-C(2n,n+1)


这篇关于最近做阿里的笔试题,美团的笔试题都出现了栈的顺序的问题。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141260

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR