update:之前一版是錯的，忽略了兩層棧深還必須ticket、spce連續的要求換個解法，代碼有些冗長#!/usr/bin/envpython#-*-coding:utf-8-*-defis_ticket(node):returnnode.startswith('ticket')defis_spec(node):returnnode.startswith('spec')defdeal1(L):ifL:node=L.pop(0)#無論何種，都會使表長-1ifis_ticket(node):returnnodereturnNonedefdeal2(L):defmatch_ts(L):node1,node2=L[:2]returnis_ticket(node1)andis_spec(node2)iflen(L)<2:returnFalseelifmatch_ts(L):del(L[:2])#表長-2returnTrueelse:returnFalsedefdeal4(L):defmatch_ttss(L):n1,n2,n3,n4=L[:4]returnis_ticket(n1)andis_ticket(n2)andis_spec(n3)andis_spec(n4)iflen(L)<4:returnFalseelifmatch_ttss(L):del(L[:4])#表長-4returnTrueelse:returnFalsedeffindout_no_spec_tickets(L):res=[]whilelen(L):ifdeal4(L):continueelifdeal2(L):continueret=deal1(L)ifret:res.append(ret)returnresL=["ticket1","ticket2","spec1","spec2","ticket3","ticket4","spec3","ticket5","spec4","spec5","ticket6","ticket7","ticket8","ticket9","ticket10","spec6","spec7","ticket11","ticket12","ticket13","spec8","ticket14","spec9","ticket15","ticket16","ticket17","ticket18","spec1","ticket19","ticket20","spec2","ticket21"]if__name__=='__main__':res=findout_no_spec_tickets(L)print(res)還有個短的寫法,無非是前向判斷，濾出非'ts','ttss'：defis_ticket(node):returnnode.startswith('ticket')deffind(L):length=len(L)foriinrange(length):ifis_ticket(L[i]):ifi==length-1:yieldL[i]eliflength-4ifis_ticket(L[i+1]):yieldL[i]else:ifis_ticket(L[i+1])and(is_ticket(L[i+2])oris_ticket(L[i+3])):yieldL[i]if__name__=='__main__':print(list(find(L)))--------------------------------before---------------------------------------用棧是最優的deffindout_no_spect(L):defis_ticket(s):returns.startswith("ticket")defis_spec(s):returns.startswith("spec")no_spec_tickets=[]stack=[]foriinL:ifstackandis_spec(i):stack.pop()ifis_ticket(i):stack.append(i)iflen(stack)>2:no_spec_tickets.append(stack.pop(0))no_spec_tickets.extend(stack)returnno_spec_tickets輸出>>>find_no_spect(L)['ticket6','ticket7','ticket8','ticket11','ticket12']
