Problema
Cada opening bracket precisa ser fechado antes do seu correspondente closing bracket.
Solução
Estrutura de Dados
A solução para o problema de validação de parênteses usa uma stack. A stack segue a regra LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a ser removido.
Como funciona
- Adicionamos os opening brackets à stack.
- Quando encontramos um closing bracket, verificamos se o último elemento da stack é o seu correspondente opening bracket.
- Se sim, removemos o elemento da stack.
- Se não, a string é inválida.
Exemplo
``python``
def isValidParentheses(s: str) -> bool:
stack = []
for char in s:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or (stack[-1] + char) not in '()[]{}':
return False
stack.pop()
return not stack
Inverter uma Linked List
Problema
A linked list é formada por nodes que apontam para o próximo node. Para inverter a lista, precisamos inverter essas referências.
Solução
Estrutura de Dados
Para inverter a linked list, usamos uma stack para acompanhar os nodes.
Como funciona
- Adicionamos cada node à stack.
- Quando precisamos de um novo head da lista, removemos os nodes da stack e os adicionamos à lista.
Exemplo
``python``
def reverseLinkedList(head: ListNode) -> ListNode:
stack = []
current = head
while current:
stack.append(current)
current = current.next
if not stack:
return None
new_head = stack.pop()
current = new_head
while stack:
current.next = stack.pop()
current = current.next
current.next = None
return new_head
Max Depth de uma Árvore
Problema
A max depth de uma árvore é a maior distância entre a raiz e um nó.
Solução
Estrutura de Dados
Para calcular a max depth, usamos uma recursão.
Como funciona
- Se o nó for None, a depth é 0.
- Se o nó não for None, a depth é 1 mais a maior depth de seus filhos.
Exemplo
``python``
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
Conclusão
O DSA View View é uma ferramenta poderosa para entender como a implementação de DSA realmente funciona. Com a ajuda do DSA View View, pudemos visualizar passo a passo como a stack e a recursão são usadas para resolver esses problemas complexos.
Tags
- DSA
- Stack
- Recursão
- Linked List
- Árvore
- Visualização Passo a Passo