python列表里面根据一定的条件挑选元素
我有一个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,ticket10
2.如果一个ticket后面跟着一个或者连续多个spec,那么这个ticket也算有spec，如ticket4,ticket5,ticket13,ticket14;
剩下的ticket都算是没有spec的，我想要挑出这些ticket，有哪些好的方法可以使用呀？
没有spec的ticket如下：ticket3,ticket6,ticket7,ticket8,ticket11,ticket12,ticket15,ticket16,ticket17,ticket19,ticket21
列表里面的信息是唯一的信息，请教各位大神有什么方法可以实现这样的挑选。
回答：
应该是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"]
def calc(l):
if len(l) < 2:
return []
t = 0
s = 0
for i in l:
if i.startswith('ticket'):
t += 1
else:
s += 1
if t >= 3:
if s >= 2:
return l[:t-2]
else:
return l[:t-s]
elif t > s:
return l[:t-s]
return []
def main(L):
res = []
start = 0
for i, curr_ele in enumerate(L[:-1]):
next_ele = L[i+1]
if curr_ele.startswith('spec') and next_ele.startswith('ticket'):
res.extend(calc(L[start:i+1]))
start = i + 1
res.extend(calc(L[start:]))
return res
print(main(L))
['ticket3', 'ticket6', 'ticket7', 'ticket8', 'ticket11', 'ticket12']
回答：
update:
之前一版是错的，忽略了两层栈深还必须ticket、spce连续的要求
换个解法，代码有些冗长
python">#!/usr/bin/env python# -*- coding: utf-8 -*-
def is_ticket(node):
return node.startswith('ticket')
def is_spec(node):
return node.startswith('spec')
def deal1(L):
if L:
node = L.pop(0) # 无论何种，都会使表长 -1
if is_ticket(node):
return node
return None
def deal2(L):
def match_ts(L):
node1, node2 = L[:2]
return is_ticket(node1) and is_spec(node2)
if len(L) < 2:
return False
elif match_ts(L):
del(L[:2]) # 表长 -2
return True
else:
return False
def deal4(L):
def match_ttss(L):
n1, n2, n3, n4 = L[:4]
return is_ticket(n1) and is_ticket(n2) and is_spec(n3) and is_spec(n4)
if len(L) < 4:
return False
elif match_ttss(L):
del(L[:4]) # 表长 -4
return True
else:
return False
def findout_no_spec_tickets(L):
res = []
while len(L):
if deal4(L):
continue
elif deal2(L):
continue
ret = deal1(L)
if ret:
res.append(ret)
return res
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'：
def is_ticket(node): return node.startswith('ticket')
def find(L):
length = len(L)
for i in range(length):
if is_ticket(L[i]):
if i == length - 1:
yield L[i]
elif length - 4 < i < length - 1:
if is_ticket(L[i+1]):
yield L[i]
else:
if is_ticket(L[i+1]) and (is_ticket(L[i+2])
or is_ticket(L[i+3])):
yield L[i]
if __name__ == '__main__':
print(list(find(L)))
--------------------------------before---------------------------------------
用栈是最优的
def findout_no_spect(L): def is_ticket(s): return s.startswith("ticket")
def is_spec(s): return s.startswith("spec")
no_spec_tickets = []
stack = []
for i in L:
if stack and is_spec(i): stack.pop()
if is_ticket(i): stack.append(i)
if len(stack) > 2: no_spec_tickets.append(stack.pop(0))
no_spec_tickets.extend(stack)
return no_spec_tickets
输出
>>> find_no_spect(L)['ticket6', 'ticket7', 'ticket8', 'ticket11', 'ticket12']
回答：
倒过来看， 发现一个spec, 可以pop一个ticket, 两个就pop两个，剩下的就是无主的。
回答：
stack = []for i in L:
stack.append(i)
if 'spec' in i:
stack.pop(-1)
stack.pop(-1)
print(stack)
以上是 python列表里面根据一定的条件挑选元素 的全部内容， 来源链接： utcz.com/a/164889.html
