Guia de Estruturas de dados básicas · 5/6
Por enquanto, este capítulo está disponível apenas em inglês.
These five problems are written for this guide. Each one is solved by choosing the right structure rather than by clever tricks. Try each before reading the approach.
A small browser starts at a home page. It supports three commands: visit url opens a new page, back returns to the previous page and forward undoes a back. Visiting a new page clears the forward history. Ignore back or forward when there is nowhere to go. Return the current page after all commands.
Approach: keep two stacks. back_stack holds pages behind the current one and forward_stack holds pages ahead of it. Going back moves the current page onto the forward stack; visiting clears the forward stack. Every command is O(1).
def browse(home, commands):
current, back_stack, forward_stack = home, [], []
for command in commands:
if command.startswith("visit "):
back_stack.append(current)
current = command[6:]
forward_stack.clear()
elif command == "back" and back_stack:
forward_stack.append(current)
current = back_stack.pop()
elif command == "forward" and forward_stack:
back_stack.append(current)
current = forward_stack.pop()
return current
cmds = ["visit a", "visit b", "back", "back", "back", "forward", "visit c", "forward"]
print(browse("home", cmds)) # cA server logs request timestamps in seconds, in non-decreasing order. After each request, report how many requests arrived in the last 60 seconds, counting the current one (timestamps t - 59 through t).
Approach: a queue holds the timestamps still inside the window. On each new timestamp, append it and pop from the front while the oldest is older than t - 59. Each timestamp enters and leaves once, so the total cost is O(n).
from collections import deque
def recent_counts(timestamps, window=60):
inside = deque()
result = []
for t in timestamps:
inside.append(t)
while inside[0] <= t - window:
inside.popleft()
result.append(len(inside))
return result
print(recent_counts([1, 10, 59, 60, 61, 125])) # [1, 2, 3, 4, 4, 1]At t = 61 the window covers 2 through 61, so the request at 1 drops out. At t = 125 the window is 66 through 125 and only the current request remains.
Order IDs arrive as a list of strings. Return the first ID that appears for the second time, judged by the position of that second appearance, or None if all IDs are unique. Also report how many distinct IDs were seen before the answer.
Approach: a set remembers IDs already seen. Scanning left to right, the first ID that is already in the set is the answer. Each check and insert is O(1) on average, so the scan is O(n) instead of the O(n squared) of comparing every pair.
def first_repeat(order_ids):
seen = set()
for order_id in order_ids:
if order_id in seen:
return order_id, len(seen)
seen.add(order_id)
return None, len(seen)
print(first_repeat(["A7", "B2", "C9", "B2", "A7"])) # ('B2', 3)
print(first_repeat(["X1", "X2"])) # (None, 2)Given hourly temperatures and a window size k, return the maximum temperature of every block of k consecutive hours.
Approach: a deque stores indices whose temperatures are in decreasing order. Before appending index i, pop from the back every index with a temperature less than or equal to the new one, because those can never be a maximum again. Pop from the front when an index slides out of the window. The front is always the maximum of the current window. Every index is pushed and popped at most once: O(n) total instead of O(n * k).
from collections import deque
def window_max(temps, k):
candidates = deque() # indices, temperatures decreasing
result = []
for i, t in enumerate(temps):
while candidates and temps[candidates[-1]] <= t:
candidates.pop()
candidates.append(i)
if candidates[0] <= i - k:
candidates.popleft()
if i >= k - 1:
result.append(temps[candidates[0]])
return result
print(window_max([12, 15, 11, 9, 14, 18, 13, 10], 3)) # [15, 15, 14, 18, 18, 18]Group words that are anagrams of each other, keeping groups in the order their first word appeared.
Approach: two words are anagrams exactly when their sorted letters are equal, so the sorted letters make a dictionary key. Python dictionaries keep insertion order, which gives the required group order for free.
def group_anagrams(words):
groups = {}
for word in words:
key = "".join(sorted(word))
groups.setdefault(key, []).append(word)
return list(groups.values())
print(group_anagrams(["listen", "stone", "silent", "notes", "enlist", "tones", "cat"]))
# [['listen', 'silent', 'enlist'], ['stone', 'notes', 'tones'], ['cat']]Undo and redo patterns call for stacks, sliding time windows call for queues, "have I seen this?" calls for a set, and "group or count by key" calls for a dictionary. When a nested loop compares every pair, ask whether a hash table or a monotonic deque can remember what the inner loop keeps recomputing.
0 comentários
Fazer login · Faça login para deixar um comentário.