O princípio de substituição de Liskov afirma que um pedaço de código deve permanecer correto se uma superclasse for substituída por sua subclasse (parafraseando). O que eu não entendo; Por que nos importamos com essa propriedade? Ela torna nosso código mais reutilizável, flexível ou sustentável?
Eu apreciaria um exemplo de código que respeitasse o princípio e que o violasse ao explicar a relevância da propriedade de substituição.
Dada uma lista Python que contém listas aninhadas de níveis arbitrários de aninhamento, o objetivo é retornar uma lista completamente simplificada, ou seja, para a entrada de exemplo [1, [2], [[[3]]], 1], a saída deve ser [1, 2, 3, 1].
Minha solução:
def flatten(lst):
stack = [[lst, 0]]
result = []
while stack:
current_lst, start_index = stack[-1]
for i in range(start_index, len(current_lst)):
if isinstance(current_lst[i], list):
# Update the start_index of current list
# to the next element after the nested list
stack[-1][1] = i + 1
# Add nested list to stack
# and initialize its start_index to 0
stack.append([current_lst[i], 0])
# Pause current_lst traversal
break
# non list item
# add item to result
result.append(current_lst[i])
else:
# no nested list
# remove current list from stack
stack.pop()
return result
Gostaria de saber a complexidade de tempo e espaço (espaço auxiliar) da minha solução, se estiver correta.
O que eu penso
Complexidade de tempo:
Acredito que a solução tem uma complexidade de tempo de O(m + n), onde m é o número total de listas aninhadas em todos os níveis e n é o número total de elementos atômicos em todos os níveis (elementos não listados).
Complexidade do Espaço:
Acredito que a complexidade do espaço é O(d) , onde d é a profundidade da lista mais aninhada. Isso ocorre porque a pilha rastreia o estado atual da travessia, e seu tamanho é proporcional à profundidade de aninhamento
A solução está correta?
A análise de tempo e espaço está correta?
Dada uma lista pythonlists = [ [1, 2], [2, 1], [3, 4] ] de listas contendo números ie , o problema é retornar uma lista de todas as listas exclusivas da lista de entrada. Uma lista é considerada uma duplicata se puder ser gerada de outra lista reordenando os itens na lista. ie [2, 1]é uma duplicata de [1, 2].Dada a entrada [ [1, 2], [2, 1], [3, 4] ], a saída deve ser [ [1, 2], [3, 4]]. Qualquer reordenação de [ [1, 2], [3, 4]] também está correta ie [1, 2], [4, 3]],
Minha abordagem é primeiro classificar todas as listas na lista de entrada, converter as listas em tuplas, usar uma estrutura de dados definida para filtrar tuplas duplicadas e, finalmente, converter as tuplas exclusivas de volta para listas. A complexidade de tempo para classificar todas as listas é O(m*nlogn)onde m é o número de listas e n é o tamanho de cada lista (assumindo listas do mesmo tamanho). Converter as listas em tuplas leva O(mn)tempo, criar um conjunto a partir das tuplas leva O(mn), converter o conjunto de tuplas exclusivas de volta para listas também leva, O(mn) tornando a complexidade de tempo total O (mnlogn + mn + mn + mn) = O(mnlogn).
Podemos fazer melhor do que O(mnlogn)?
Código:
def find_unique(lists):
sorted_lists = [ sorted(lst) for lst in lists]
tuples = [tuple(lst) for lst in sorted_lists]
unique_tuples = set(tuples)
return list(unique_tuples)