递归法 | #栈的压入、弹出序列#

栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

python3, 递归法。
初始情况:
  1. 都空,True。
  2. 长度不同;长度同,但元素对应不上。都返回False。(题目保证了pushV 的所有数字均不相同,这里用set(list)可以做判断)
  3. 长度<=2, 一定能对应压入和弹出,返回True。
递归关键:
    popV的第一个点是最先pop的,第二个点是其次pop的。反映在pushV中, 第二个点 一定在第一个点的 后面 或者 前一位 ,否则返回False。(这里先判断一下,是否在pushV的首位,因为首位没有前一位)
    上一步不返回False,则说明第一个点是暂时合格的,然后pushV和popV都弹出该点(脑中模拟一下栈弹出的过程),再继续递归。
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        def IsPalindrome(pu, po):
            if len(pu) <= 2:
                return True

            a = pu.index(po[0])
            if a == 0:
                return IsPalindrome(pu[1:], po[1:])
            if po[1] not in pu[a-1:]:
                return False
            pu.pop(a)
            po.pop(0)
            return IsPalindrome(pu, po)

        if not pushV and not popV: return True
        if len(pushV) != len(popV) or set(pushV) != set(popV): return False
        if len(pushV) <= 2: return True
        
        return IsPalindrome(pushV, popV)


全部评论

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务