Histórico de voltar e avançar
A missão
Problema
Simule o histórico de uma única aba do navegador que começa em uma página inicial. Uma visita abre uma nova página depois da atual e descarta todas as páginas para as quais antes seria possível avançar. Uma operação back de k volta até k páginas em direção ao início, e uma forward de k avança até k páginas em direção à mais nova, parando antes quando não há mais para onde ir. Dada a página inicial e uma lista de operações, retorne a página em que você está depois de cada back ou forward, em ordem.
Exemplos
Input: home = "home"
ops = [("visit", "a"), ("visit", "b"), ("back", 1),
("visit", "c"), ("forward", 1), ("back", 5)]
Output: ['a', 'c', 'home']
Por quê: visitar c a partir de a descarta b, então o forward não tem para onde ir
Input: home = "x", ops = [("back", 2), ("forward", 3)]
Output: ['x', 'x']
Por quê: edge case: uma aba nova não consegue ir nem para trás nem para a frente
Dicas
0 / 3
Cada página precisa conhecer tanto a página anterior quanto a seguinte, e back e forward só percorrem uma dessas ligações.
Uma visita não apaga as páginas da frente uma por uma. Apontar a página atual para uma página seguinte totalmente nova as torna inalcançáveis de uma só vez.
Mantenha um nó por página com ligações prev e next e um ponteiro para o nó atual. A visita liga um novo nó depois do atual e vai para ele; back e forward seguem prev ou next até k vezes, parando quando a ligação estiver vazia.
- Tempo-alvo
- O(n + Σk)
- Espaço-alvo
- O(n)
Solução
Cada página é um nó com ligações para a página anterior e para a seguinte, e um ponteiro marca onde a aba está. Uma visita pendura um novo nó depois do atual, o que corta silenciosamente as antigas páginas da frente, e então vai para ele. Back e forward seguem as ligações prev ou next um passo por vez e param na primeira ligação ausente, então pedir passos demais não causa problema. Uma visita é O(1), um movimento de k passos é O(k), e o espaço é O(número de visitas).
class Page:
def __init__(self, url, prev=None): self.url, self.prev, self.next = url, prev, None
def run_history(home, ops):
current, seen = Page(home), []
for op, arg in ops:
if op == "visit":
current.next = Page(arg, current) # the old forward pages become unreachable
current = current.next
continue
for _ in range(arg): # back or forward, at most arg steps
step = current.prev if op == "back" else current.next
if step is None:
break
current = step
seen.append(current.url)
return seen
print(run_history("home", [("visit", "a"), ("visit", "b"), ("back", 1), ("visit", "c"), ("forward", 1), ("back", 5)])) # -> ['a', 'c', 'home']
print(run_history("x", [("back", 2), ("forward", 3)])) # -> ['x', 'x']
print(run_history("x", [])) # -> []Travou na ideia, e não no código? Listas duplamente encadeadas explica isso.