急求！！！！python列表里面根据一定的条件挑选元素各位有什么建议？

Question

我有一个list如下结构：L=["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"]想要挑出来后面没有跟着spec的ticket，具体规则如下：1.如果连续两个ticket后面跟着连续两个spec，那么这两个ticket算有spec，如ticket1，ticket2;ticket9,ticket102.如果一个ticket后面跟着一个或者连续多个spec,那么这个ticket也算有spec，如ticket4,ticket5,ticket13,ticket14;剩下的ticket都算是没有spec的，我想要挑出这些ticket，有哪些好的方法可以使用呀？没有spec的ticket如下：ticket3,ticket6,ticket7,ticket8,ticket11,ticket12,ticket15,ticket16,ticket17,ticket19,ticket21列表里面的信息是唯一的信息，请教各位大神有什么方法可以实现这样的挑选。

Answer 1

应该是2*n的时间复杂度，可以按这个原理再优化成n的时间复杂度和O(1)的空间复杂度
L=["ticket1","ticket2","spec1","spec2",
"ticket3","ticket4","spec3",
"ticket5","spec4","spec5",
"ticket6","ticket7","ticket8",
"ticket9","ticket10","spec6","spec7",
"ticket11","ticket12",
"ticket13","spec8",
"ticket14","spec9"]
defcalc(l):
iflen(l)<2:
return[]
t=0
s=0
foriinl:
ifi.startswith('ticket'):
t+=1
else:
s+=1
ift>=3:
ifs>=2:
returnl[:t-2]
else:
returnl[:t-s]
elift>s:
returnl[:t-s]
return[]
defmain(L):
res=[]
start=0
fori,curr_eleinenumerate(L[:-1]):
next_ele=L[i+1]
ifcurr_ele.startswith('spec')andnext_ele.startswith('ticket'):
res.extend(calc(L[start:i+1]))
start=i+1
res.extend(calc(L[start:]))
returnres
print(main(L))
['ticket3','ticket6','ticket7','ticket8','ticket11','ticket12']
                            

Answer 2

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)#无论何种，都会使表长-1
ifis_ticket(node):
returnnode
returnNone
defdeal2(L):
defmatch_ts(L):
node1,node2=L[:2]
returnis_ticket(node1)andis_spec(node2)
iflen(L)<2:
returnFalse
elifmatch_ts(L):
del(L[:2])#表长-2
returnTrue
else:
returnFalse
defdeal4(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:
returnFalse
elifmatch_ttss(L):
del(L[:4])#表长-4
returnTrue
else:
returnFalse
deffindout_no_spec_tickets(L):
res=[]
whilelen(L):
ifdeal4(L):
continue
elifdeal2(L):
continue
ret=deal1(L)
ifret:
res.append(ret)
returnres
L=["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']