递归法 | #栈的压入、弹出序列#
栈的压入、弹出序列
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
python3， 递归法。
初始情况：
- 都空，True。
- 长度不同；长度同，但元素对应不上。都返回False。（题目保证了pushV 的所有数字均不相同，这里用set(list)可以做判断）
- 长度<=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)
三环集团开奖93人在聊
投递BOSS直聘等公司8个岗位