滴滴2018.10.10笔试火车编组题

绝地灬酷狼 2022-05-08 09:48 168阅读 0赞

# 题目描述 #

原题不放了。其实就是考已知入栈序列为1,2,3,4，n=4，问输入的出栈序列是否合理（合理输入Yes，不合理输出No）。  
**输入：**  
4  
1  
3  
2  
**输出：**  
No

# 思路 #

inV为索引，指向入栈序列。outV为索引，指向出栈序列。  
新建一个栈stack来模拟出栈过程，如果合理，那么stack的出栈过程会与出栈序列依次匹配。  
考虑出栈序列合理，那么如果当前inV指向的元素与outV指向的元素不一样，那么就将当前inV指向的元素入栈stack，inV++；如果当前inV指向的元素与outV指向的元素一样，那么就出栈stack，outV++。  
考虑出栈序列不合理，那么inV就会 >= n。  
![在这里插入图片描述][70]  
以如上实际例子为例，当前stack已经入栈4321了，判断栈顶与出栈序列当前所指元素是否相等，当前相等，则进入if，stack出栈，即成功模拟了出栈序列当前所指元素的出栈，然后出栈序列索引后移。  
![在这里插入图片描述][70 1]  
判断栈顶与出栈序列当前所指元素是否相等，当前不相等，则进 入else，将入栈序列当前所指元素入栈stack，即成功模拟了入栈序列当前所指元素的入栈，然后入栈序列索引后移。  
![在这里插入图片描述][70 2]  
判断栈顶与出栈序列当前所指元素是否相等，当前相等，则进入if，stack出栈，即成功模拟了出栈序列当前所指元素的出栈，然后出栈序列索引后移。  
![在这里插入图片描述][70 3]  
判断栈顶与出栈序列当前所指元素是否相等，当前不相等，则进 入else，但入栈序列的索引指向了一个不存在的元素，因为所有元素都已经入栈，所以不应该再有元素可以入栈了。这时就说明了出栈序列是不合理的。

# 代码 #

outLI = []
    for i in range(4):
        outLI.append(eval(input()))
    n = len(outLI)
    inputLI = [i for i in range(1,n+1)]
    
    def solve(n,inputLI,outLI):
        stack = []
        stack.append(1)
        outV = 0#指向未被扫描的出栈序列的元素
        inV = 1#指向未被扫描的入栈序列的元素，已经扫描了一个 
        while(outV < n):
            if stack[-1] == outLI[outV]:
                #栈顶元素和出栈序列当前元素一样，说明匹配了一个出栈序列的元素
                #就出栈
                stack.pop()
                outV+=1
            else:
                if inV == n:
                    #扫描所有入栈序列后，inV会变成n，但变成n后就不应该再进入else了
                    #因为所有元素都已经入过栈了
                    return 'No'
                #栈顶元素和出栈序列当前元素不一样，说明它还没入栈
                #就入栈
                stack.append(inputLI[inV])
                inV+=1
        return 'Yes'
        
    print(solve(n,inputLI,outLI))

[70]: /images/20220508/6bc00b79a9a84422b17699bfe68aedd0.png
[70 1]: /images/20220508/ca95b94569e94c539e558d3071437998.png
[70 2]: /images/20220508/f42e2f47f0e74cabba5ccbd95fd58bce.png
[70 3]: /images/20220508/9000aa8bb92649588a153b3ef483916b.png