Guia de Algoritmos

Guia de Algoritmos para Entrevistas - Conteúdo Completo

Este documento contém todo o conteúdo do guia de algoritmos para entrevistas de
programação em um formato adequado para impressão. Utilize o botão de impressão
para salvar como PDF ou imprimir todo o material.

Índice de Conteúdo
Problemas simples
Loops
Arrays
Complexidade de tempo
Ordenação
Sets e Maps
Pilha
Lista Encadeada
Fila de Prioridade
Strings
Dois Ponteiros
Recursão
Backtracking
Matemática
Busca Binária
Grafos
Busca em Profundidade
Busca em Largura
Árvores Binárias
Programação Dinâmica
Trie

Problemas simples
 Problemas
Guia Simples
de Algoritmos
Antes de mergulhar em algoritmos mais complexos, vamos começar com alguns problemas simples. Estes
problemas são mais fáceis que os problemas típicos de entrevista, mas são ótimos para praticar suas
habilidades de programação básicas e se familiarizar com o processo de resolução de problemas.

Soma de dois números

Dado dois números inteiros, retorne sua soma.

def soma(a: int, b: int) -> int:

return a + b

# Exemplo de uso:
print(soma(2, 3)) # Imprime: 5

Maior de dois números

Dados dois números inteiros, retorne o maior deles.

def maior(a: int, b: int) -> int:

if a > b:
return a
return b

# Exemplo de uso:
print(maior(2, 3)) # Imprime: 3

Verificar se um número é par

Dado um número inteiro, retorne True se ele for par e False caso contrário.

def eh_par(n: int) -> bool:

return n % 2 == 0

# Exemplo de uso:
print(eh_par(4)) # Imprime: True
print(eh_par(3)) # Imprime: False

Dicas para resolver problemas simples

Leia o problema cuidadosamente e certifique-se de entender todos os requisitos
Pense em casos de teste simples antes de começar a codificar
Mantenha seu código limpo e bem organizado
 Teste seu código com diferentes casos de entrada
GuiaConsidere
de Algoritmos
casos especiais (números negativos, zero, etc.)

Próximos passos
Depois de se sentir confortável com estes problemas simples, você pode avançar para tópicos mais
complexos como Arrays e Loops. Lembre-se de que mesmo problemas aparentemente simples
podem ter nuances interessantes e podem ser usados para praticar boas práticas de programação.

Loops

Loops
Em muitos problemas, você não precisa conhecer algoritmos e técnicas especiais. O que você precisa é
apenas usar loops e variáveis simples. Nesta seção, vamos cobrir várias maneiras comuns de como você
pode resolver problemas com loops e praticar com vários exemplos.

Maior e segundo maior elemento

Encontrar o maior elemento em um array é extremamente comum. Aqui está uma forma simples de fazer
isso:

def encontrar_maior(arr):
if not arr: # Se o array estiver vazio
return None

maior = arr[0] # Começamos assumindo que o primeiro elemento é o maior

for num in arr[1:]: # Iteramos sobre o resto do array
if num > maior:
maior = num

return maior

# Exemplo de uso:
numeros = [5, 7, 8, 9, -1, 3]
print(encontrar_maior(numeros)) # Imprime: 9

E quanto ao segundo maior elemento? Aqui está como podemos encontrá-lo:

Guia deifAlgoritmos
def encontrar_dois_maiores(arr):
len(arr) < 2: # Precisamos de pelo menos 2 elementos
return None, None

# Inicializamos os dois maiores com os dois primeiros elementos

maior = max(arr[0], arr[1])
segundo_maior = min(arr[0], arr[1])

# Iteramos sobre o resto do array

for num in arr[2:]:
if num > maior:
segundo_maior = maior
maior = num
elif num > segundo_maior and num != maior:
segundo_maior = num

return maior, segundo_maior

# Exemplo de uso:
numeros = [5, 7, 8, 9, -1, 3]
maior, segundo = encontrar_dois_maiores(numeros)
print(f"Maior: {maior}, Segundo maior: {segundo}") # Imprime: Maior: 9, Segundo ma

Ponteiros convergentes
Às vezes, é muito conveniente ter duas variáveis se movendo uma em direção à outra em um loop. Por
exemplo, aqui está como você pode verificar se uma string é um palíndromo:

def eh_palindromo(texto):
if not texto: # String vazia é considerada palíndromo
return True

# Removemos espaços e convertemos para minúsculas

texto = [Link]().replace(" ", "")

# Usamos dois ponteiros: um no início e outro no fim

esquerda = 0
direita = len(texto) - 1

while esquerda < direita:

if texto[esquerda] != texto[direita]:
return False
esquerda += 1
direita -= 1

return True

# Exemplos de uso:
print(eh_palindromo("ana")) # Imprime: True
 print(eh_palindromo("radar")) # Imprime: True
Guia de Algoritmos
print(eh_palindromo("python")) # Imprime: False

Dígitos de um número
Outra técnica interessante é dividir um número inteiro em seus dígitos. Aqui está, por exemplo, como você
pode encontrar a soma dos dígitos de um número não negativo:

def soma_digitos(numero):
if numero < 0:
return None # Ou podemos trabalhar com o valor absoluto: abs(numero)

soma = 0
while numero > 0:
digito = numero % 10 # Obtém o último dígito
soma += digito
numero //= 10 # Remove o último dígito

return soma

# Exemplos de uso:
print(soma_digitos(123)) # Imprime: 6 (1 + 2 + 3)
print(soma_digitos(9045)) # Imprime: 18 (9 + 0 + 4 + 5)

Problemas práticos para exercitar

Aqui estão alguns problemas interessantes do LeetCode que você pode resolver usando apenas loops:

852 - Peak Index in a Mountain Array LeetCode

657 - Robot Return to Origin LeetCode

647 - Palindromic Substrings LeetCode

674 - Longest Continuous Increasing Subsequence LeetCode

118 - Pascal's Triangle LeetCode

Dica importante
Ao resolver problemas com loops, sempre considere os casos extremos:

Arrays/strings vazios
Arrays/strings com um único elemento
Números negativos (quando trabalhando com números)
 Valores muito grandes que podem causar overflow
Guia de Algoritmos

Próximos passos
Depois de praticar com loops simples, você estará pronto para combinar esse conhecimento com
estruturas de dados mais complexas. O próximo tópico será Arrays, onde veremos como usar loops
de maneira mais sofisticada para resolver problemas mais desafiadores.

Arrays

Arrays
Arrays são uma das estruturas de dados mais fundamentais e frequentemente utilizadas em entrevistas
de programação. Nesta seção, vamos explorar várias técnicas comuns para trabalhar com arrays e
resolver problemas relacionados.

Soma de Prefixos
Uma técnica muito útil ao trabalhar com arrays é calcular e armazenar as somas dos prefixos. Isso pode
ajudar a resolver vários tipos de problemas de maneira eficiente.

def criar_soma_prefixos(arr):
if not arr:
return []

soma_prefixos = [0] * len(arr)

soma_prefixos[0] = arr[0]

for i in range(1, len(arr)):

soma_prefixos[i] = soma_prefixos[i-1] + arr[i]

return soma_prefixos

# Exemplo de uso:
arr = [1, 2, 3, 4, 5]
somas = criar_soma_prefixos(arr)
print(somas) # Imprime: [1, 3, 6, 10, 15]

# Agora podemos facilmente encontrar a soma de qualquer intervalo

 def soma_intervalo(somas, inicio, fim):
Guia deifAlgoritmos
inicio == 0:
return somas[fim]
return somas[fim] - somas[inicio-1]

# Exemplo: soma do intervalo [1,3] (índices 1 a 3)

print(soma_intervalo(somas, 1, 3)) # Imprime: 9 (2 + 3 + 4)

Arrays Bidimensionais
Arrays bidimensionais (ou matrizes) são muito comuns em problemas de entrevista. Aqui está um exemplo
de como percorrer uma matriz em espiral:

def percorrer_espiral(matriz):
if not matriz:
return []

resultado = []
inicio_linha, fim_linha = 0, len(matriz)
inicio_col, fim_col = 0, len(matriz[0])

while inicio_linha < fim_linha and inicio_col < fim_col:

# Percorre para a direita
for j in range(inicio_col, fim_col):
[Link](matriz[inicio_linha][j])
inicio_linha += 1

# Percorre para baixo

for i in range(inicio_linha, fim_linha):
[Link](matriz[i][fim_col-1])
fim_col -= 1

if inicio_linha < fim_linha:

# Percorre para a esquerda
for j in range(fim_col-1, inicio_col-1, -1):
[Link](matriz[fim_linha-1][j])
fim_linha -= 1

if inicio_col < fim_col:

# Percorre para cima
for i in range(fim_linha-1, inicio_linha-1, -1):
[Link](matriz[i][inicio_col])
inicio_col += 1

return resultado

# Exemplo de uso:
matriz = [
[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
 [10, 9, 8, 7]
Guia
] de Algoritmos
print(percorrer_espiral(matriz))
# Imprime: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Técnicas Comuns com Arrays

Janela Deslizante: Útil para problemas que envolvem subarrays contíguos
Dois Ponteiros: Eficiente para problemas que requerem comparação de elementos
Varredura Bidirecional: Percorrer o array da esquerda para direita e vice-versa
Manipulação In-place: Modificar o array sem usar espaço extra

Problemas Práticos do LeetCode

53 - Maximum Subarray LeetCode

238 - Product of Array Except Self LeetCode

189 - Rotate Array LeetCode

283 - Move Zeroes LeetCode

448 - Find All Numbers Disappeared in an Array LeetCode

Dicas para Problemas com Arrays

Sempre considere o caso do array vazio
Verifique se você pode resolver o problema in-place
Pense em usar estruturas auxiliares (como hash maps) quando necessário
Considere ordenar o array se isso simplificar a solução
Cuidado com índices ao modificar o array durante a iteração

Próximos passos
Depois de dominar as técnicas básicas com arrays, você estará pronto para explorar conceitos mais
avançados como complexidade de tempo e espaço. Estes conceitos são cruciais para otimizar suas
soluções e se destacar nas entrevistas.
Complexidade
Guia de Algoritmosde tempo

Complexidade de Tempo
A complexidade de tempo é um conceito fundamental em ciência da computação que nos ajuda a
entender quanto tempo um algoritmo leva para executar em relação ao tamanho da entrada. Em
entrevistas, é crucial não apenas resolver o problema, mas também entender e otimizar a complexidade
de tempo da sua solução.

Notação Big O
A notação Big O é usada para descrever o limite superior do crescimento de um algoritmo. Aqui estão as
complexidades mais comuns, da mais eficiente para a menos eficiente:

O(1) - Constante: O tempo de execução é sempre o mesmo, independente do tamanho da entrada.

def primeiro_elemento(arr):
if not arr:
return None
return arr[0] # O(1) - sempre acessa apenas o primeiro elemento

O(log n) - Logarítmica: O tempo de execução cresce logaritmicamente com o tamanho da entrada.

def busca_binaria(arr, alvo):

esquerda, direita = 0, len(arr) - 1

while esquerda <= direita:

meio = (esquerda + direita) // 2
if arr[meio] == alvo:
return meio
elif arr[meio] < alvo:
esquerda = meio + 1
else:
direita = meio - 1

return -1 # O(log n) - divide o problema pela metade a cada iteração

O(n) - Linear: O tempo de execução cresce linearmente com o tamanho da entrada.

def soma_elementos(arr):
soma = 0
for num in arr: # O(n) - percorre cada elemento uma vez
soma += num
return soma

O(n log n) - Linearítmica: Comum em algoritmos eficientes de ordenação.

Guia de Algoritmos
def merge_sort(arr):
if len(arr) <= 1:
return arr

meio = len(arr) // 2
esquerda = merge_sort(arr[:meio])
direita = merge_sort(arr[meio:])

# O(n log n) - divide o array log n vezes e combina em tempo linear

return merge(esquerda, direita)

O(n²) - Quadrática: O tempo de execução cresce quadraticamente.

def bubble_sort(arr):
n = len(arr)
for i in range(n): # O(n²) - dois loops aninhados
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

Analisando Complexidade
Para analisar a complexidade de tempo de um algoritmo, considere:

Quantas vezes cada operação é executada

Como o número de operações cresce com o tamanho da entrada
Apenas o termo de maior crescimento é mantido
Constantes são descartadas

Exemplo Prático
def encontrar_par_soma(arr, alvo):
# Abordagem O(n²)
def forca_bruta():
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == alvo:
return [i, j]
return []

# Abordagem O(n)
def usando_hash():
visto = {}
for i, num in enumerate(arr):
complemento = alvo - num
if complemento in visto:
return [visto[complemento], i]
 visto[num] = i
Guia de Algoritmos
return []

# A segunda solução é muito mais eficiente!

return usando_hash()

Dicas para Otimização

Procure eliminar loops aninhados quando possível
Considere usar estruturas de dados auxiliares para melhorar o tempo
Às vezes, usar mais memória pode reduzir o tempo de execução
Busque padrões que permitam dividir o problema (como busca binária)

Próximos passos
Após entender bem a complexidade de tempo, é importante também estudar a complexidade de
espaço e como equilibrar esses dois aspectos. O próximo tópico será Ordenação, onde aplicaremos
muito desse conhecimento de complexidade.

Ordenação

Ordenação
Algoritmos de ordenação são fundamentais na ciência da computação e frequentemente aparecem em
entrevistas. Além disso, muitos problemas podem ser simplificados ordenando os dados primeiro. Vamos
explorar os principais algoritmos de ordenação e suas características.

Bubble Sort
O algoritmo mais simples de ordenação, mas não o mais eficiente. Útil para entender conceitos básicos
de ordenação.

def bubble_sort(arr):
n = len(arr)
for i in range(n):
 # Flag para otimização
Guia de Algoritmos
trocou = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
trocou = True
# Se não houve trocas, o array já está ordenado
if not trocou:
break
return arr

# Complexidade de tempo: O(n²)

# Complexidade de espaço: O(1)
print(bubble_sort([64, 34, 25, 12, 22, 11, 90])) # [11, 12, 22, 25, 34, 64, 90]

Merge Sort
Um algoritmo eficiente que usa a estratégia de dividir para conquistar. Garantido de ter complexidade O(n
log n) em todos os casos.

def merge_sort(arr):
if len(arr) <= 1:
return arr

meio = len(arr) // 2
esquerda = merge_sort(arr[:meio])
direita = merge_sort(arr[meio:])

return merge(esquerda, direita)

def merge(esquerda, direita):

resultado = []
i = j = 0

while i < len(esquerda) and j < len(direita):

if esquerda[i] <= direita[j]:
[Link](esquerda[i])
i += 1
else:
[Link](direita[j])
j += 1

[Link](esquerda[i:])
[Link](direita[j:])
return resultado

# Complexidade de tempo: O(n log n)

# Complexidade de espaço: O(n)
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # [3, 9, 10, 27, 38, 43, 82]
 Quick Sort
Guia de Algoritmos
Um dos algoritmos mais utilizados na prática. Muito eficiente em média, mas pode ter caso pior O(n²) se o
pivô não for bem escolhido.

def quick_sort(arr):
if len(arr) <= 1:
return arr

pivo = arr[len(arr) // 2]
esquerda = [x for x in arr if x < pivo]
meio = [x for x in arr if x == pivo]
direita = [x for x in arr if x > pivo]

return quick_sort(esquerda) + meio + quick_sort(direita)

# Complexidade de tempo média: O(n log n)

# Complexidade de tempo pior caso: O(n²)
# Complexidade de espaço: O(log n) em média
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # [1, 1, 2, 3, 6, 8, 10]

Comparação dos Algoritmos

Algoritmo Melhor Caso Médio Caso Pior Caso Espaço Estável

Bubble Sort O(n) O(n²) O(n²) O(1) Sim

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Sim

Quick Sort O(n log n) O(n log n) O(n²) O(log n) Não

Quando Usar Cada Algoritmo?

Bubble Sort: Arrays pequenos ou quase ordenados
Merge Sort: Quando precisa de ordenação estável e tem memória extra disponível
Quick Sort: Melhor opção geral para arrays grandes, quando estabilidade não é necessária

Dicas para Entrevistas

Saiba implementar pelo menos um algoritmo O(n log n) de memória
Entenda os trade-offs entre tempo e espaço
Considere se a estabilidade é importante para o problema
Pense se uma ordenação parcial seria suficiente
Guia de Algoritmos
Próximos passos
Após dominar os algoritmos de ordenação básicos, você pode explorar variações mais avançadas
como Heap Sort e Counting Sort. O próximo tópico será Sets e Maps, onde veremos como essas
estruturas de dados podem nos ajudar a resolver problemas de maneira eficiente.

Sets e Maps

Sets e Maps
Sets e Maps são estruturas de dados fundamentais que permitem armazenar e acessar dados de forma
eficiente. Em Python, temos sets (conjuntos) e dicionários (maps), que são implementados usando
tabelas hash, oferecendo operações O(1) em média.

Sets (Conjuntos)
Um set é uma coleção não ordenada de elementos únicos. Perfeito para verificar pertencimento e eliminar
duplicatas.

# Criando um set
numeros = {1, 2, 3, 4, 5}
numeros_duplicados = {1, 2, 2, 3, 3, 4, 5} # Automaticamente remove duplicatas
print(numeros_duplicados) # {1, 2, 3, 4, 5}

# Operações comuns - todas O(1) em média

[Link](6) # Adiciona um elemento
[Link](1) # Remove um elemento (erro se não existir)
[Link](1) # Remove um elemento (sem erro se não existir)
print(2 in numeros) # Verifica pertencimento

# Operações de conjunto
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b) # União: {1, 2, 3, 4, 5, 6}
print(a & b) # Interseção: {3, 4}
print(a - b) # Diferença: {1, 2}
print(a ^ b) # Diferença simétrica: {1, 2, 5, 6}

Maps (Dicionários)
 Um map (ou dicionário em Python) é uma coleção de pares chave-valor, onde cada chave é única.
Guia de Algoritmos
Excelente para associar dados relacionados.

# Criando um dicionário
notas = {
'João': 8.5,
'Maria': 9.0,
'Pedro': 7.5
}

# Operações básicas - todas O(1) em média

notas['Ana'] = 9.5 # Adiciona ou atualiza um valor
nota_joao = notas['João'] # Acessa um valor
[Link]('Pedro') # Remove um par chave-valor
print('Maria' in notas) # Verifica se uma chave existe

# Métodos úteis
print([Link]()) # Obtém todas as chaves
print([Link]()) # Obtém todos os valores
print([Link]()) # Obtém todos os pares chave-valor

# Exemplo prático: contando frequência de elementos

def contar_frequencia(lista):
frequencia = {}
for item in lista:
frequencia[item] = [Link](item, 0) + 1
return frequencia

nums = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
print(contar_frequencia(nums)) # {1: 1, 2: 2, 3: 3, 4: 4}

Problemas Comuns com Sets

Sets são particularmente úteis para resolver vários tipos de problemas:

Encontrar elementos únicos em uma lista

Verificar se duas listas têm elementos em comum
Remover duplicatas mantendo a ordem (usando list + set)
Verificar se uma string contém todos os caracteres de outra

# Encontrar elementos únicos

def elementos_unicos(arr):
return list(set(arr))

# Verificar elementos em comum

def tem_elementos_comuns(arr1, arr2):
return bool(set(arr1) & set(arr2))

# Remover duplicatas mantendo ordem

def remover_duplicatas_ordenado(arr):
 return list([Link](arr))
Guia de Algoritmos
# Verificar se uma string é anagrama
def eh_anagrama(s1, s2):
return set(s1) == set(s2) and len(s1) == len(s2)

Problemas Comuns com Maps

Maps são excelentes para resolver problemas que envolvem:

Contar frequência de elementos

Agrupar elementos por alguma característica
Criar índices ou caches
Implementar relacionamentos muitos-para-muitos

# Encontrar par que soma a um valor

def encontrar_par_soma(arr, alvo):
visto = {}
for i, num in enumerate(arr):
complemento = alvo - num
if complemento in visto:
return [visto[complemento], i]
visto[num] = i
return []

# Agrupar anagramas
def agrupar_anagramas(palavras):
grupos = {}
for palavra in palavras:
chave = ''.join(sorted(palavra))
[Link](chave, []).append(palavra)
return list([Link]())

Dicas para Entrevistas

Use sets quando precisar verificar pertencimento frequentemente
Use maps quando precisar associar valores a chaves
Lembre-se que as chaves de um map precisam ser imutáveis
Sets e maps podem reduzir a complexidade de O(n) para O(1) em buscas

Problemas Práticos do LeetCode

217 - Contains Duplicate LeetCode
 1 - Two Sum LeetCode
Guia de Algoritmos
49 - Group Anagrams LeetCode

128 - Longest Consecutive Sequence LeetCode

242 - Valid Anagram LeetCode

Próximos passos
Depois de dominar sets e maps, você estará pronto para explorar estruturas de dados mais
complexas como pilhas e filas. Estas estruturas são fundamentais para resolver problemas que
envolvem processamento em ordem específica.

Pilha

Pilha (Stack)
Uma pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out - Último a Entrar,
Primeiro a Sair). Pense nela como uma pilha de pratos: você só pode adicionar ou remover pratos do topo
da pilha.

Implementação Básica
Em Python, podemos implementar uma pilha usando uma lista, onde o final da lista representa o topo da
pilha.

class Pilha:
def __init__(self):
[Link] = []

def esta_vazia(self):
return len([Link]) == 0

def empilhar(self, item):

[Link](item) # O(1)

def desempilhar(self):
if not self.esta_vazia():
return [Link]() # O(1)
raise IndexError("Pilha vazia")
Guia dedefAlgoritmos
topo(self):
if not self.esta_vazia():
return [Link][-1] # O(1)
raise IndexError("Pilha vazia")

def tamanho(self):
return len([Link])

# Exemplo de uso
pilha = Pilha()
[Link](1)
[Link](2)
[Link](3)
print([Link]()) # Imprime: 3
print([Link]()) # Imprime: 3
print([Link]()) # Imprime: 2

Aplicações Comuns
Pilhas são usadas em vários cenários importantes:

Desfazer/refazer operações em editores

Avaliação de expressões matemáticas
Chamadas de funções (pilha de execução)
Verificação de parênteses balanceados
Conversão entre notações (infixa, pós-fixa)

Exemplo: Verificando Parênteses Balanceados

def parenteses_balanceados(expressao):
pilha = []
pares = {')': '(', '}': '{', ']': '['}

for char in expressao:

if char in '({[':
[Link](char)
elif char in ')}]':
if not pilha:
return False
if [Link]() != pares[char]:
return False

return len(pilha) == 0

# Exemplos de uso
print(parenteses_balanceados("(){}[]")) # True
print(parenteses_balanceados("([{}])")) # True
 print(parenteses_balanceados("({[}])")) # False
Guia de Algoritmos
print(parenteses_balanceados("((()")) # False

Exemplo: Avaliação de Expressão Pós-fixa

def avaliar_pos_fixa(expressao):
pilha = []
operadores = {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: x / y
}

for token in [Link]():

if token in operadores:
if len(pilha) < 2:
raise ValueError("Expressão inválida")
b = [Link]()
a = [Link]()
resultado = operadores[token](a, b)
[Link](resultado)
else:
[Link](float(token))

if len(pilha) != 1:
raise ValueError("Expressão inválida")
return pilha[0]

# Exemplos de uso
# "3 4 +" equivale a "3 + 4"
print(avaliar_pos_fixa("3 4 +")) # 7.0
# "5 3 4 * +" equivale a "5 + (3 * 4)"
print(avaliar_pos_fixa("5 3 4 * +")) # 17.0
# "10 5 2 * -" equivale a "10 - (5 * 2)"
print(avaliar_pos_fixa("10 5 2 * -")) # 0.0

Problemas Práticos do LeetCode

20 - Valid Parentheses LeetCode

155 - Min Stack LeetCode

232 - Implement Queue using Stacks LeetCode

844 - Backspace String Compare LeetCode

1047 - Remove All Adjacent Duplicates In String LeetCode

Guia de Algoritmos
Dicas para Entrevistas
Considere usar pilha quando precisar rastrear o elemento mais recente
Pilhas são ótimas para problemas que envolvem correspondência ou balanceamento
Em Python, listas podem ser usadas como pilhas eficientemente
Lembre-se de tratar o caso da pilha vazia

Próximos passos
Depois de dominar pilhas, você pode avançar para listas encadeadas, que são estruturas de dados
fundamentais que frequentemente aparecem em conjunto com pilhas em problemas de entrevista.

Lista Encadeada

Lista Encadeada (Linked List)

Uma lista encadeada é uma estrutura de dados linear onde cada elemento (nó) contém um valor e uma
referência (ou ponteiro) para o próximo elemento. Diferente de arrays, os elementos não precisam estar
em posições contíguas na memória.

Implementação Básica
Vamos implementar uma lista encadeada simples em Python:

class No:
def __init__(self, valor):
[Link] = valor
[Link] = None

class ListaEncadeada:
def __init__(self):
[Link] = None

def esta_vazia(self):
return [Link] is None

def inserir_inicio(self, valor):

 novo_no = No(valor)
Guia de Algoritmos
novo_no.proximo = [Link]
[Link] = novo_no

def inserir_fim(self, valor):

novo_no = No(valor)
if self.esta_vazia():
[Link] = novo_no
return

atual = [Link]
while [Link]:
atual = [Link]
[Link] = novo_no

def remover_inicio(self):
if self.esta_vazia():
raise ValueError("Lista vazia")
valor = [Link]
[Link] = [Link]
return valor

def imprimir(self):
atual = [Link]
elementos = []
while atual:
[Link](str([Link]))
atual = [Link]
print(" -> ".join(elementos))

# Exemplo de uso
lista = ListaEncadeada()
lista.inserir_inicio(3)
lista.inserir_inicio(2)
lista.inserir_inicio(1)
lista.inserir_fim(4)
[Link]() # 1 -> 2 -> 3 -> 4

Lista Duplamente Encadeada

Uma variação comum é a lista duplamente encadeada, onde cada nó tem referências para o próximo e o
anterior:

class NoDuplo:
def __init__(self, valor):
[Link] = valor
[Link] = None
[Link] = None

class ListaDuplamenteEncadeada:
def __init__(self):
 [Link] = None
Guia de Algoritmos
[Link] = None

def inserir_inicio(self, valor):

novo_no = NoDuplo(valor)
if self.esta_vazia():
[Link] = [Link] = novo_no
else:
novo_no.proximo = [Link]
[Link] = novo_no
[Link] = novo_no

def inserir_fim(self, valor):

novo_no = NoDuplo(valor)
if self.esta_vazia():
[Link] = [Link] = novo_no
else:
novo_no.anterior = [Link]
[Link] = novo_no
[Link] = novo_no

def esta_vazia(self):
return [Link] is None

Operações Comuns e Complexidades

Operação Lista Simples Lista Dupla

Inserir no início O(1) O(1)

Inserir no fim O(n) O(1)

Remover do início O(1) O(1)

Remover do fim O(n) O(1)

Buscar elemento O(n) O(n)

Técnicas Comuns
1. Técnica do Corredor Rápido e Lento (Floyd's Cycle Finding)
def detectar_ciclo(cabeca):
if not cabeca or not [Link]:
return False

lento = cabeca
rapido = [Link]

while rapido and [Link]:

if lento == rapido:
return True
 lento = [Link]
Guia de Algoritmos
rapido = [Link]

return False

2. Reverter uma Lista Encadeada

def reverter_lista(cabeca):
anterior = None
atual = cabeca

while atual:
proximo = [Link]
[Link] = anterior
anterior = atual
atual = proximo

return anterior # Nova cabeça da lista

Problemas Práticos do LeetCode

206 - Reverse Linked List LeetCode

21 - Merge Two Sorted Lists LeetCode

141 - Linked List Cycle LeetCode

19 - Remove Nth Node From End of List LeetCode

876 - Middle of the Linked List LeetCode

Dicas para Entrevistas

Sempre verifique casos de lista vazia ou com um único nó
Use a técnica do corredor rápido/lento para problemas de ciclos ou meio da lista
Mantenha referências para nós anteriores quando necessário
Considere usar uma cabeça sentinela para simplificar operações

Próximos passos
 Após dominar listas encadeadas, você pode avançar para estruturas mais complexas como árvores e
Guiagrafos.
de Algoritmos
A compreensão de listas encadeadas é fundamental para entender como os nós se conectam
nessas estruturas mais avançadas.

Fila de Prioridade

Fila de Prioridade (Priority Queue)

Uma fila de prioridade é uma estrutura de dados que mantém elementos em ordem de prioridade. Em
Python, ela é implementada usando um heap binário, que garante que o elemento de maior (ou menor)
prioridade sempre esteja acessível em O(1).

Heap Binário
Um heap binário é uma árvore binária completa onde cada nó pai tem um valor menor (min-heap) ou
maior (max-heap) que seus filhos.

# Em Python, usamos o módulo heapq que implementa um min-heap

import heapq

# Criando um heap vazio

heap = []

# Adicionando elementos (heappush) - O(log n)

[Link](heap, 5)
[Link](heap, 3)
[Link](heap, 7)
[Link](heap, 1)

# Removendo o menor elemento (heappop) - O(log n)

menor = [Link](heap) # retorna 1

# Visualizando o menor elemento sem remover (peek) - O(1)

menor_atual = heap[0] # retorna 3

# Convertendo uma lista em heap - O(n)

lista = [5, 3, 7, 1, 9, 2]
[Link](lista) # lista agora é um min-heap

Implementação de Max Heap

 Como o heapq do Python implementa um min-heap, para criar um max-heap precisamos inverter os
Guia deouAlgoritmos
valores usar uma classe auxiliar:

# Método 1: Invertendo os valores

max_heap = []
valores = [5, 3, 7, 1, 9, 2]
for valor in valores:
[Link](max_heap, -valor)

# Para obter o maior valor

maior = -[Link](max_heap)

# Método 2: Usando uma classe auxiliar

class Item:
def __init__(self, valor):
[Link] = valor

def __lt__(self, outro):

return [Link] > [Link] # Inverte a comparação

max_heap = []
for valor in valores:
[Link](max_heap, Item(valor))

Fila de Prioridade com Objetos

Em situações reais, frequentemente precisamos ordenar objetos por múltiplos critérios:

class Tarefa:
def __init__(self, prioridade, descricao):
[Link] = prioridade
[Link] = descricao

def __lt__(self, outra):

return [Link] < [Link]

# Criando uma fila de prioridade de tarefas

fila_tarefas = []
[Link](fila_tarefas, Tarefa(3, "Baixa prioridade"))
[Link](fila_tarefas, Tarefa(1, "Urgente"))
[Link](fila_tarefas, Tarefa(2, "Média prioridade"))

# Processando tarefas em ordem de prioridade

while fila_tarefas:
tarefa = [Link](fila_tarefas)
print(f"Executando: {[Link]} (Prioridade: {[Link]})")

k-ésimo Menor/Maior Elemento

 Uma aplicação comum de filas de prioridade é encontrar o k-ésimo menor ou maior elemento:
Guia de Algoritmos
def k_menor_elemento(arr, k):
# Usando min-heap
heap = arr[:k]
[Link](heap)

for num in arr[k:]:

if num < heap[0]:
[Link](heap, num)

return heap[0]

def k_maior_elemento(arr, k):

# Usando max-heap (com valores negativos)
heap = [-num for num in arr[:k]]
[Link](heap)

for num in arr[k:]:

if -num > heap[0]:
[Link](heap, -num)

return -heap[0]

# Exemplo de uso
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(k_menor_elemento(arr, k)) # 7 (3º menor elemento)
print(k_maior_elemento(arr, k)) # 10 (3º maior elemento)

Problemas Práticos do LeetCode

215 - Kth Largest Element in an Array LeetCode

347 - Top K Frequent Elements LeetCode

23 - Merge k Sorted Lists LeetCode

973 - K Closest Points to Origin LeetCode

1046 - Last Stone Weight LeetCode

Dicas para Entrevistas

Use fila de prioridade quando precisar manter elementos ordenados dinamicamente
Para problemas de "top-k", considere usar uma fila de prioridade de tamanho k
Lembre-se que heapq implementa min-heap por padrão
 A complexidade de inserção e remoção é O(log n)
Guia de Algoritmos

Próximos passos
Após dominar filas de prioridade, você estará pronto para explorar estruturas de dados mais
avançadas como árvores binárias de busca e grafos. Filas de prioridade são frequentemente usadas
como componentes em algoritmos mais complexos, como o algoritmo de Dijkstra.

Strings

Strings
Strings são uma das estruturas de dados mais comuns em programação e frequentemente aparecem em
entrevistas. Em Python, strings são imutáveis, o que significa que cada operação que modifica uma string
cria uma nova string.

Operações Básicas
# Criação e concatenação
texto = "Hello"
texto += " World" # Cria uma nova string

# Fatiamento (slicing)
texto = "Python"
print(texto[0:2]) # "Py"
print(texto[2:]) # "thon"
print(texto[::-1]) # "nohtyP" (reverso)

# Métodos úteis
texto = " Python é incrível! "
print([Link]()) # Remove espaços em branco
print([Link]()) # Converte para minúsculas
print([Link]()) # Converte para maiúsculas
print([Link]()) # Divide em palavras
print(",".join(["a", "b"])) # Une strings com separador

# Verificações comuns
texto = "Python3.9"
print([Link]()) # Contém apenas letras?
 print([Link]()) # Contém letras ou números?
Guia de Algoritmos
print([Link]()) # Contém apenas números?
print([Link]("Py")) # Começa com "Py"?
print([Link](".9")) # Termina com ".9"?

Técnicas Comuns
1. Verificar Palíndromo
def eh_palindromo(texto):
# Remove espaços e converte para minúsculas
texto = [Link]().replace(" ", "")
return texto == texto[::-1]

# Exemplos
print(eh_palindromo("ana")) # True
print(eh_palindromo("A man a plan a canal Panama")) # True
print(eh_palindromo("python")) # False

2. Contar Caracteres
from collections import Counter

def contar_caracteres(texto):
# Usando Counter
return Counter(texto)

def contar_manual(texto):
# Implementação manual
contagem = {}
for char in texto:
contagem[char] = [Link](char, 0) + 1
return contagem

texto = "programação"
print(contar_caracteres(texto)) # Counter({'a': 2, 'r': 2, 'o': 2, ...})
print(contar_manual(texto)) # {'p': 1, 'r': 2, 'o': 2, ...}

3. Verificar Anagrama
def sao_anagramas(s1, s2):
# Método 1: Usando ordenação
return sorted(s1) == sorted(s2)

def sao_anagramas_counter(s1, s2):

# Método 2: Usando Counter
return Counter(s1) == Counter(s2)

# Exemplos
 print(sao_anagramas("listen", "silent")) # True
Guia de Algoritmos
print(sao_anagramas("triangle", "integral")) # True
print(sao_anagramas("python", "java")) # False

4. Encontrar Substring
def encontrar_todas_ocorrencias(texto, padrao):
ocorrencias = []
pos = [Link](padrao)

while pos != -1:

[Link](pos)
pos = [Link](padrao, pos + 1)

return ocorrencias

texto = "banana"
padrao = "ana"
print(encontrar_todas_ocorrencias(texto, padrao)) # [1, 3]

Problemas Práticos do LeetCode

5 - Longest Palindromic Substring LeetCode

3 - Longest Substring Without Repeating Characters LeetCode

20 - Valid Parentheses LeetCode

242 - Valid Anagram LeetCode

49 - Group Anagrams LeetCode

Dicas para Entrevistas

Lembre-se que strings são imutáveis em Python
Use Counter para problemas de frequência de caracteres
Considere usar dicionários para mapear caracteres
Cuidado com maiúsculas/minúsculas e espaços em branco
Para problemas de substring, considere a técnica de janela deslizante

Técnicas Avançadas
1. Janela Deslizante (Sliding Window)
Guia deinicio
Algoritmos
def maior_substring_sem_repeticao(s):
= 0
max_tamanho = 0
caracteres = {}

for fim, char in enumerate(s):

if char in caracteres and caracteres[char] >= inicio:
inicio = caracteres[char] + 1
else:
max_tamanho = max(max_tamanho, fim - inicio + 1)
caracteres[char] = fim

return max_tamanho

# Exemplo
print(maior_substring_sem_repeticao("abcabcbb")) # 3 ("abc")

2. Manacher (Palíndromos)
def expandir_centro(s, esquerda, direita):
while esquerda >= 0 and direita < len(s) and s[esquerda] == s[direita]:
esquerda -= 1
direita += 1
return s[esquerda + 1:direita]

def maior_palindromo(s):
if not s:
return ""

maior = s[0]
for i in range(len(s)):
# Palíndromo ímpar
palindromo1 = expandir_centro(s, i, i)
if len(palindromo1) > len(maior):
maior = palindromo1

# Palíndromo par
palindromo2 = expandir_centro(s, i, i + 1)
if len(palindromo2) > len(maior):
maior = palindromo2

return maior

# Exemplo
print(maior_palindromo("babad")) # "bab" ou "aba"

Próximos passos
 Depois de dominar as operações básicas com strings, você pode explorar algoritmos mais
Guiaavançados
de Algoritmos
como KMP (Knuth-Morris-Pratt) para busca de padrões e Árvores de Sufixos para
problemas mais complexos de strings.

Dois Ponteiros

Dois Ponteiros (Two Pointers)

A técnica dos dois ponteiros é uma abordagem muito útil para resolver problemas que envolvem arrays ou
listas encadeadas. Ela usa dois ponteiros que se movem através da estrutura de dados de forma
coordenada, geralmente reduzindo a complexidade de O(n²) para O(n).

Padrões Comuns
1. Ponteiros nas Extremidades
Um ponteiro no início e outro no fim, movendo-se em direção ao centro.

def soma_dois_numeros(nums, alvo):

esquerda, direita = 0, len(nums) - 1

while esquerda < direita:

soma_atual = nums[esquerda] + nums[direita]
if soma_atual == alvo:
return [esquerda, direita]
elif soma_atual < alvo:
esquerda += 1
else:
direita -= 1

return [] # Não encontrou

# Exemplo (array ordenado)

nums = [2, 7, 11, 15]
alvo = 9
print(soma_dois_numeros(nums, alvo)) # [0, 1]

2. Ponteiros na Mesma Direção

Dois ponteiros que se movem na mesma direção, mas com velocidades diferentes.
Guia deifAlgoritmos
def remover_duplicatas(nums):
not nums:
return 0

# ponteiro_escrita mantém a posição do próximo elemento único

ponteiro_escrita = 1

# ponteiro_leitura encontra elementos únicos

for ponteiro_leitura in range(1, len(nums)):
if nums[ponteiro_leitura] != nums[ponteiro_leitura - 1]:
nums[ponteiro_escrita] = nums[ponteiro_leitura]
ponteiro_escrita += 1

return ponteiro_escrita

# Exemplo
nums = [1, 1, 2, 2, 3, 4, 4]
tamanho = remover_duplicatas(nums)
print(nums[:tamanho]) # [1, 2, 3, 4]

3. Janela Deslizante
Dois ponteiros que definem uma "janela" que pode crescer ou encolher.

def menor_subarray_soma(nums, alvo):

inicio = 0
soma_atual = 0
menor_tamanho = float('inf')

for fim in range(len(nums)):

soma_atual += nums[fim]

while soma_atual >= alvo:

menor_tamanho = min(menor_tamanho, fim - inicio + 1)
soma_atual -= nums[inicio]
inicio += 1

return menor_tamanho if menor_tamanho != float('inf') else 0

# Exemplo
nums = [2, 3, 1, 2, 4, 3]
alvo = 7
print(menor_subarray_soma(nums, alvo)) # 2 ([4, 3])

4. Ponteiros Rápido e Lento

Dois ponteiros que se movem em velocidades diferentes, útil para detectar ciclos.

def encontrar_duplicata(nums):
# Algoritmo da Lebre e da Tartaruga (Floyd's Cycle Finding)
 lento = nums[0]
Guia derapido
Algoritmos
= nums[0]

# Encontrar interseção
while True:
lento = nums[lento]
rapido = nums[nums[rapido]]
if lento == rapido:
break

# Encontrar entrada do ciclo

lento = nums[0]
while lento != rapido:
lento = nums[lento]
rapido = nums[rapido]

return lento

# Exemplo
nums = [1, 3, 4, 2, 2] # Array com números de 1 a n, com uma duplicata
print(encontrar_duplicata(nums)) # 2

Problemas Práticos do LeetCode

167 - Two Sum II - Input Array Is Sorted LeetCode

15 - 3Sum LeetCode

11 - Container With Most Water LeetCode

283 - Move Zeroes LeetCode

75 - Sort Colors LeetCode

Dicas para Entrevistas

Identifique se o problema pode ser resolvido com dois ponteiros
Considere se o array precisa estar ordenado
Cuidado com condições de parada dos ponteiros
Verifique casos especiais (array vazio, um elemento)
Pense em como mover os ponteiros de forma eficiente

Variações da Técnica
Guia de Algoritmos
# Três ponteiros (para soma
def soma_tres_numeros(nums,
de três números)
alvo):
[Link]() # Importante ordenar primeiro
n = len(nums)

for i in range(n - 2):

if i > 0 and nums[i] == nums[i - 1]:
continue

esquerda, direita = i + 1, n - 1
while esquerda < direita:
soma = nums[i] + nums[esquerda] + nums[direita]
if soma == alvo:
return [nums[i], nums[esquerda], nums[direita]]
elif soma < alvo:
esquerda += 1
else:
direita -= 1

return []

# Exemplo
nums = [-1, 0, 1, 2, -1, -4]
alvo = 0
print(soma_tres_numeros(nums, alvo)) # [-1, 0, 1]

Próximos passos
Depois de dominar a técnica dos dois ponteiros, você pode explorar variações mais complexas como
múltiplos ponteiros e combiná-la com outras técnicas como programação dinâmica e backtracking
para resolver problemas mais desafiadores.

Recursão

Recursão
Recursão é uma técnica de programação onde uma função resolve um problema chamando a si mesma
com uma entrada menor. É fundamental entender recursão para resolver problemas complexos e é
frequentemente usada em estruturas de dados como árvores e grafos.
 Conceitos Fundamentais
Guia de Algoritmos
1. Caso Base
O caso base é a condição que para a recursão. Sem ele, a função continuaria chamando a si mesma
indefinidamente.

def fatorial(n):
# Caso base
if n == 0 or n == 1:
return 1
# Caso recursivo
return n * fatorial(n - 1)

print(fatorial(5)) # 120

2. Fibonacci
Um exemplo clássico de recursão é a sequência de Fibonacci.

def fibonacci(n):
# Casos base
if n <= 1:
return n
# Caso recursivo
return fibonacci(n - 1) + fibonacci(n - 2)

# Exemplo
print([fibonacci(i) for i in range(7)]) # [0, 1, 1, 2, 3, 5, 8]

# Versão otimizada com memoização

def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]

print(fibonacci_memo(7)) # 13

3. Soma de Array
Um exemplo simples de como a recursão pode ser usada para processar arrays.

def soma_array(arr):
# Caso base
if not arr:
 return 0
Guia de Algoritmos
# Caso recursivo
return arr[0] + soma_array(arr[1:])

# Exemplo
print(soma_array([1, 2, 3, 4, 5])) # 15

# Versão otimizada (evita criar novos arrays)

def soma_array_otimizada(arr, inicio=0):
if inicio >= len(arr):
return 0
return arr[inicio] + soma_array_otimizada(arr, inicio + 1)

print(soma_array_otimizada([1, 2, 3, 4, 5])) # 15

4. Torre de Hanoi
Um problema clássico que demonstra a elegância da recursão.

def torre_hanoi(n, origem, destino, auxiliar):

if n == 1:
print(f"Mover disco 1 de {origem} para {destino}")
return

torre_hanoi(n - 1, origem, auxiliar, destino)

print(f"Mover disco {n} de {origem} para {destino}")
torre_hanoi(n - 1, auxiliar, destino, origem)

# Exemplo
print("Resolvendo Torre de Hanoi com 3 discos:")
torre_hanoi(3, 'A', 'C', 'B')

Problemas Práticos do LeetCode

21 - Merge Two Sorted Lists LeetCode

509 - Fibonacci Number LeetCode

206 - Reverse Linked List LeetCode

70 - Climbing Stairs LeetCode

104 - Maximum Depth of Binary Tree LeetCode

Dicas para Entrevistas

Identifique claramente o caso base
Verifique se há necessidade de memoização
 Considere o espaço da pilha de recursão
Guia de Algoritmos
Pense se uma solução iterativa seria mais eficiente
Cuidado com a profundidade máxima da recursão em Python

Técnicas Avançadas
1. Recursão com Cauda
def fatorial_cauda(n, acumulador=1):
if n <= 1:
return acumulador
return fatorial_cauda(n - 1, n * acumulador)

print(fatorial_cauda(5)) # 120

2. Divisão e Conquista
def merge_sort(arr):
# Caso base
if len(arr) <= 1:
return arr

# Dividir
meio = len(arr) // 2
esquerda = merge_sort(arr[:meio])
direita = merge_sort(arr[meio:])

# Conquistar e Combinar
return merge(esquerda, direita)

def merge(esquerda, direita):

resultado = []
i = j = 0

while i < len(esquerda) and j < len(direita):

if esquerda[i] <= direita[j]:
[Link](esquerda[i])
i += 1
else:
[Link](direita[j])
j += 1

[Link](esquerda[i:])
[Link](direita[j:])
return resultado

# Exemplo
 arr = [64, 34, 25, 12, 22, 11, 90]
Guia de Algoritmos
print(merge_sort(arr)) # [11, 12, 22, 25, 34, 64, 90]

Próximos passos
Depois de dominar os conceitos básicos de recursão, você pode explorar tópicos mais avançados
como programação dinâmica, backtracking e algoritmos de divisão e conquista, que frequentemente
utilizam recursão como base.

Backtracking

Backtracking
Backtracking é uma técnica algorítmica que considera a exploração de todas as possíveis soluções de
forma sistemática. Quando percebe que um caminho não levará a uma solução válida, "volta atrás"
(backtrack) e tenta outro caminho.

Problemas Clássicos
1. N-Rainhas
Posicionar N rainhas em um tabuleiro NxN sem que se ataquem.

def n_rainhas(n):
def pode_colocar(tabuleiro, linha, coluna):
# Verifica a coluna
for i in range(linha):
if tabuleiro[i][coluna] == 1:
return False

# Verifica diagonal superior esquerda

for i, j in zip(range(linha-1, -1, -1), range(coluna-1, -1, -1)):
if tabuleiro[i][j] == 1:
return False

# Verifica diagonal superior direita

for i, j in zip(range(linha-1, -1, -1), range(coluna+1, n)):
if tabuleiro[i][j] == 1:
return False

return True
Guia dedefAlgoritmos
resolver(tabuleiro, linha):
if linha >= n:
return True

for coluna in range(n):

if pode_colocar(tabuleiro, linha, coluna):
tabuleiro[linha][coluna] = 1
if resolver(tabuleiro, linha + 1):
return True
tabuleiro[linha][coluna] = 0

return False

tabuleiro = [[0 for x in range(n)] for y in range(n)]

if resolver(tabuleiro, 0):
return tabuleiro
return None

# Exemplo
solucao = n_rainhas(4)
for linha in solucao:
print(linha) # Mostra uma solução possível para 4 rainhas

2. Subconjuntos
Gerar todos os subconjuntos possíveis de um conjunto.

def subconjuntos(nums):
resultado = []

def backtrack(inicio, subconjunto_atual):

[Link](subconjunto_atual[:])

for i in range(inicio, len(nums)):

# Adiciona o elemento atual
subconjunto_atual.append(nums[i])
# Explora com o elemento adicionado
backtrack(i + 1, subconjunto_atual)
# Remove o elemento (backtrack)
subconjunto_atual.pop()

backtrack(0, [])
return resultado

# Exemplo
nums = [1, 2, 3]
print(subconjuntos(nums)) # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

3. Permutações
 Gerar todas as permutações possíveis de um conjunto.
Guia de Algoritmos
def permutacoes(nums):
resultado = []

def backtrack(inicio):
if inicio == len(nums):
[Link](nums[:])
return

for i in range(inicio, len(nums)):

# Troca os elementos
nums[inicio], nums[i] = nums[i], nums[inicio]
# Recursão
backtrack(inicio + 1)
# Desfaz a troca (backtrack)
nums[inicio], nums[i] = nums[i], nums[inicio]

backtrack(0)
return resultado

# Exemplo
nums = [1, 2, 3]
print(permutacoes(nums)) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]

Problemas Práticos do LeetCode

51 - N-Queens LeetCode

78 - Subsets LeetCode

46 - Permutations LeetCode

39 - Combination Sum LeetCode

79 - Word Search LeetCode

Dicas para Entrevistas

Identifique a condição de parada
Defina claramente o estado que precisa ser mantido
Determine as restrições do problema
Pense em como podar caminhos inválidos cedo
Considere usar uma função auxiliar recursiva
 Otimizações
Guia de Algoritmos
def combinacao_soma(candidatos, alvo):
resultado = []

def backtrack(inicio, alvo, combinacao_atual):

if alvo == 0:
[Link](combinacao_atual[:])
return
if alvo < 0:
return

for i in range(inicio, len(candidatos)):

# Poda: se o próximo número já é maior que o alvo, podemos parar
if candidatos[i] > alvo:
break

# Evita duplicatas ordenando os candidatos e pulando números iguais

if i > inicio and candidatos[i] == candidatos[i-1]:
continue

combinacao_atual.append(candidatos[i])
backtrack(i, alvo - candidatos[i], combinacao_atual)
combinacao_atual.pop()

[Link]() # Importante para otimização

backtrack(0, alvo, [])
return resultado

# Exemplo
candidatos = [2, 3, 6, 7]
alvo = 7
print(combinacao_soma(candidatos, alvo)) # [[2, 2, 3], [7]]

Próximos passos
Após dominar backtracking, você pode explorar sua aplicação em problemas mais complexos de
grafos, como coloração de grafos e problemas de satisfatibilidade booleana (SAT). Também é
importante estudar como combinar backtracking com programação dinâmica para problemas que
exigem ambas as técnicas.

Matemática
 Matemática
Guia de Algoritmos
Problemas matemáticos são comuns em entrevistas de programação. Eles geralmente envolvem
conceitos como números primos, divisibilidade, teoria dos números e manipulação de bits.

Conceitos Fundamentais
1. Números Primos
Verificação e geração de números primos são problemas comuns.

def eh_primo(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True

def crivo_eratostenes(n):
# Gera todos os primos até n
primos = [True] * (n + 1)
primos[0] = primos[1] = False

for i in range(2, int(n ** 0.5) + 1):

if primos[i]:
# Marca múltiplos como não primos
for j in range(i * i, n + 1, i):
primos[j] = False

return [i for i in range(n + 1) if primos[i]]

# Exemplos
print(eh_primo(17)) # True
print(crivo_eratostenes(20)) # [2, 3, 5, 7, 11, 13, 17, 19]

2. MDC e MMC
Máximo Divisor Comum e Mínimo Múltiplo Comum são conceitos importantes.

def mdc(a, b):

# Algoritmo de Euclides
while b:
a, b = b, a % b
return a

def mmc(a, b):

# MMC = (a * b) / MDC(a, b)
return abs(a * b) // mdc(a, b)
Guia de Algoritmos
# Exemplos
print(mdc(48, 18)) # 6
print(mmc(48, 18)) # 144

3. Manipulação de Bits
Operações com bits são úteis para otimização e problemas específicos.

def conta_bits(n):
# Conta bits 1 em um número
return bin(n).count('1')

def eh_potencia_de_dois(n):
# Verifica se é potência de 2
return n > 0 and (n & (n - 1)) == 0

def inverte_bits(n):
# Inverte os bits de um número
return ~n

def get_bit(n, i):

# Obtém o bit na posição i
return (n >> i) & 1

def set_bit(n, i):

# Define o bit na posição i como 1
return n | (1 << i)

def clear_bit(n, i):

# Define o bit na posição i como 0
return n & ~(1 << i)

# Exemplos
print(conta_bits(7)) # 3 (111 em binário)
print(eh_potencia_de_dois(8)) # True
print(bin(set_bit(10, 2))) # 0b1110 (14 em decimal)

Problemas Práticos do LeetCode

204 - Contagem de Números Primos
50 - Pow(x, n)
9 - Número Palíndromo
191 - Número de Bits 1
231 - Potência de Dois
Guia de Algoritmos
Dicas para Entrevistas
Considere casos especiais (0, negativos, overflow)
Procure otimizações matemáticas
Use propriedades de bits quando possível
Cuidado com divisão por zero
Verifique se há padrões matemáticos no problema

Técnicas Avançadas
1. Exponenciação Rápida
def pow_mod(base, expoente, modulo):
# Calcula (base ^ expoente) % modulo eficientemente
if expoente == 0:
return 1

resultado = 1
base = base % modulo

while expoente > 0:

# Se o bit atual é 1, multiplica o resultado
if expoente & 1:
resultado = (resultado * base) % modulo
# Eleva a base ao quadrado
base = (base * base) % modulo
# Move para o próximo bit
expoente >>= 1

return resultado

# Exemplo
print(pow_mod(2, 10, 1000)) # 24

2. Números de Fibonacci com Matriz

def multiplica_matriz(A, B):
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]

def fibonacci_matriz(n):
if n <= 0:
return 0
 # Matriz base [[1,1],[1,0]]
Guia de Algoritmos
A = [[1, 1], [1, 0]]
resultado = [[1, 0], [0, 1]] # Matriz identidade

# Exponenciação rápida da matriz

while n > 0:
if n & 1:
resultado = multiplica_matriz(resultado, A)
A = multiplica_matriz(A, A)
n >>= 1

return resultado[0][1]

# Exemplo
print(fibonacci_matriz(10)) # 55

Próximos passos
Após dominar os conceitos básicos de matemática, você pode explorar tópicos mais avançados
como teoria dos números, combinatória e probabilidade. Também é importante estudar como esses
conceitos se aplicam em problemas de otimização e criptografia.

Busca Binária

Busca Binária
Busca binária é um algoritmo eficiente para encontrar um elemento em uma coleção ordenada, reduzindo
o espaço de busca pela metade a cada iteração. Sua complexidade é O(log n), tornando-o muito mais
rápido que a busca linear O(n).

Implementação Básica
def busca_binaria(arr, alvo):
esquerda, direita = 0, len(arr) - 1

while esquerda <= direita:

meio = (esquerda + direita) // 2

if arr[meio] == alvo:
return meio # Elemento encontrado, retorna o índice
 elif arr[meio] < alvo:
Guia de Algoritmos
esquerda = meio + 1 # Busca na metade direita
else:
direita = meio - 1 # Busca na metade esquerda

return -1 # Elemento não encontrado

# Exemplo
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(busca_binaria(arr, 7)) # 3
print(busca_binaria(arr, 10)) # -1

Variações Comuns
1. Primeiro Elemento Maior ou Igual
Encontra o primeiro elemento maior ou igual ao alvo (lower bound).

def lower_bound(arr, alvo):

esquerda, direita = 0, len(arr)

while esquerda < direita:

meio = (esquerda + direita) // 2
if arr[meio] < alvo:
esquerda = meio + 1
else:
direita = meio

return esquerda if esquerda < len(arr) else -1

# Exemplo
arr = [1, 3, 3, 5, 5, 5, 7]
print(lower_bound(arr, 5)) # 3 (primeiro 5)

2. Último Elemento Menor ou Igual

Encontra o último elemento menor ou igual ao alvo (upper bound).

def upper_bound(arr, alvo):

esquerda, direita = 0, len(arr)

while esquerda < direita:

meio = (esquerda + direita) // 2
if arr[meio] <= alvo:
esquerda = meio + 1
else:
direita = meio

return esquerda - 1
 # Exemplo
Guia
arrde
= Algoritmos
[1, 3, 3, 5, 5, 5, 7]
print(upper_bound(arr, 5)) # 5 (último 5)

3. Busca em Array Rotacionado

Encontra um elemento em um array ordenado que foi rotacionado.

def busca_array_rotacionado(arr, alvo):

esquerda, direita = 0, len(arr) - 1

while esquerda <= direita:

meio = (esquerda + direita) // 2

if arr[meio] == alvo:
return meio

# Verifica qual metade está ordenada

if arr[esquerda] <= arr[meio]:
# Metade esquerda está ordenada
if arr[esquerda] <= alvo < arr[meio]:
direita = meio - 1
else:
esquerda = meio + 1
else:
# Metade direita está ordenada
if arr[meio] < alvo <= arr[direita]:
esquerda = meio + 1
else:
direita = meio - 1

return -1

# Exemplo
arr = [4, 5, 6, 7, 0, 1, 2]
print(busca_array_rotacionado(arr, 0)) # 4

Problemas Práticos do LeetCode

704 - Binary Search LeetCode

35 - Search Insert Position LeetCode

33 - Search in Rotated Sorted Array LeetCode

69 - Sqrt(x) LeetCode

153 - Find Minimum in Rotated Sorted Array LeetCode

Guia de Algoritmos
Dicas para Entrevistas
Verifique se o array está ordenado
Cuidado com overflow ao calcular o meio
Considere duplicatas no array
Teste casos de borda (array vazio, um elemento)
Verifique se o problema pode ser reduzido a uma busca binária

Aplicações Avançadas
def raiz_quadrada(x):
if x < 2:
return x

esquerda, direita = 1, x // 2

while esquerda <= direita:

meio = (esquerda + direita) // 2
quadrado = meio * meio

if quadrado == x:
return meio
elif quadrado < x:
esquerda = meio + 1
else:
direita = meio - 1

return direita # Retorna o maior inteiro cuja raiz quadrada é menor ou igual a

# Exemplo
print(raiz_quadrada(8)) # 2 (maior inteiro cuja raiz quadrada é <= 8)

def busca_pico(arr):
# Encontra um elemento que é maior que seus vizinhos
esquerda, direita = 0, len(arr) - 1

while esquerda < direita:

meio = (esquerda + direita) // 2
if arr[meio] > arr[meio + 1]:
direita = meio
else:
esquerda = meio + 1

return esquerda

# Exemplo
 arr = [1, 2, 3, 1]
Guia de Algoritmos
print(busca_pico(arr)) # 2 (3 é o pico)

Próximos passos
Depois de dominar a busca binária básica, explore suas aplicações em problemas mais complexos,
como busca em matrizes 2D ordenadas, minimização de valores máximos e maximização de valores
mínimos. A busca binária também é útil em problemas de otimização onde você pode verificar a
viabilidade de uma solução.

Grafos

Grafos
Grafos são estruturas de dados que representam relações entre objetos. Consistem em vértices (ou nós)
conectados por arestas. São amplamente utilizados para modelar redes sociais, mapas, dependências
entre tarefas e muito mais.

Representações de Grafos
1. Lista de Adjacências
Representa o grafo usando um dicionário onde cada vértice mapeia para seus vizinhos.

# Usando dicionário de listas

grafo = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

# Usando classe para mais flexibilidade

class Grafo:
def __init__(self):
[Link] = {}

def adiciona_vertice(self, v):

 if v not in [Link]:
Guia de Algoritmos
[Link][v] = []

def adiciona_aresta(self, v1, v2):

self.adiciona_vertice(v1)
self.adiciona_vertice(v2)
[Link][v1].append(v2)
[Link][v2].append(v1) # Para grafo não direcionado

2. Matriz de Adjacências
Representa o grafo usando uma matriz onde matriz[i][j] indica se existe aresta entre i e j.

def cria_matriz_adjacencias(n):
return [[0] * n for _ in range(n)]

def adiciona_aresta(matriz, i, j):

matriz[i][j] = 1
matriz[j][i] = 1 # Para grafo não direcionado

# Exemplo
n = 4 # número de vértices
matriz = cria_matriz_adjacencias(n)
adiciona_aresta(matriz, 0, 1)
adiciona_aresta(matriz, 1, 2)
adiciona_aresta(matriz, 2, 3)

Algoritmos Fundamentais
1. Busca em Profundidade (DFS)
Explora o grafo indo o mais fundo possível em cada ramo antes de retroceder.

def dfs(grafo, inicio, visitados=None):

if visitados is None:
visitados = set()

[Link](inicio)
print(inicio, end=' ') # Processa o vértice

for vizinho in grafo[inicio]:

if vizinho not in visitados:
dfs(grafo, vizinho, visitados)

# Versão iterativa usando pilha

def dfs_iterativo(grafo, inicio):
visitados = set()
pilha = [inicio]

while pilha:
 vertice = [Link]()
Guia de Algoritmos
if vertice not in visitados:
[Link](vertice)
print(vertice, end=' ')
[Link](v for v in grafo[vertice] if v not in visitados)

# Exemplo
grafo = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
dfs(grafo, 'A') # A B D C

2. Busca em Largura (BFS)

Explora o grafo em níveis, visitando todos os vizinhos antes de avançar.

from collections import deque

def bfs(grafo, inicio):

visitados = set([inicio])
fila = deque([inicio])

while fila:
vertice = [Link]()
print(vertice, end=' ')

for vizinho in grafo[vertice]:

if vizinho not in visitados:
[Link](vizinho)
[Link](vizinho)

# Exemplo com distâncias

def bfs_com_distancia(grafo, inicio):
distancias = {inicio: 0}
fila = deque([inicio])

while fila:
vertice = [Link]()
for vizinho in grafo[vertice]:
if vizinho not in distancias:
distancias[vizinho] = distancias[vertice] + 1
[Link](vizinho)

return distancias

# Exemplo
grafo = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
print(bfs_com_distancia(grafo, 'A')) # {'A': 0, 'B': 1, 'C': 1, 'D': 2}

3. Detecção de Ciclo
Verifica se existe um ciclo no grafo.
Guia devisitados
Algoritmos
def tem_ciclo(grafo):
= set()
pilha_rec = set()

def dfs_ciclo(vertice):
[Link](vertice)
pilha_rec.add(vertice)

for vizinho in grafo[vertice]:

if vizinho not in visitados:
if dfs_ciclo(vizinho):
return True
elif vizinho in pilha_rec:
return True

pilha_rec.remove(vertice)
return False

for vertice in grafo:

if vertice not in visitados:
if dfs_ciclo(vertice):
return True
return False

# Exemplo
grafo_com_ciclo = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(tem_ciclo(grafo_com_ciclo)) # True

Problemas Práticos do LeetCode

200 - Number of Islands LeetCode

133 - Clone Graph LeetCode

207 - Course Schedule LeetCode

785 - Is Graph Bipartite? LeetCode

997 - Find the Town Judge LeetCode

Dicas para Entrevistas

Escolha a representação adequada para o problema
Considere se o grafo é direcionado ou não
Verifique se há ciclos quando relevante
Use BFS para menor caminho em grafos não ponderados
 Mantenha registro de nós visitados para evitar loops infinitos
Guia de Algoritmos

Aplicações Avançadas
def encontra_componentes(grafo):
visitados = set()
componentes = []

def dfs_componente(vertice, componente_atual):

[Link](vertice)
componente_atual.append(vertice)

for vizinho in grafo[vertice]:

if vizinho not in visitados:
dfs_componente(vizinho, componente_atual)

for vertice in grafo:

if vertice not in visitados:
componente_atual = []
dfs_componente(vertice, componente_atual)
[Link](componente_atual)

return componentes

def eh_bipartido(grafo):
cores = {}

def pode_colorir(vertice, cor):

cores[vertice] = cor

for vizinho in grafo[vertice]:

if vizinho not in cores:
if not pode_colorir(vizinho, not cor):
return False
elif cores[vizinho] == cor:
return False
return True

for vertice in grafo:

if vertice not in cores:
if not pode_colorir(vertice, True):
return False
return True

# Exemplos
grafo_componentes = {
'A': ['B'], 'B': ['A'],
'C': ['D'], 'D': ['C'],
'E': []
}
 print(encontra_componentes(grafo_componentes)) # [['A', 'B'], ['C', 'D'], ['E']]
Guia de Algoritmos
grafo_bipartido = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
print(eh_bipartido(grafo_bipartido)) # True

Próximos passos
Após dominar os conceitos básicos de grafos, explore algoritmos mais avançados como Dijkstra,
Bellman-Ford, Floyd-Warshall para caminhos mínimos, e algoritmos de árvore geradora mínima como
Kruskal e Prim. Também é importante estudar fluxo em redes e algoritmos de emparelhamento.

Busca em Profundidade

Busca em Profundidade (DFS)

A Busca em Profundidade (DFS - Depth-First Search) é um algoritmo para percorrer estruturas de dados
em forma de árvore ou grafo. O algoritmo começa em um nó raiz e explora o máximo possível ao longo de
cada ramo antes de retroceder.

Implementações Básicas
1. DFS Recursivo
A forma mais intuitiva de implementar DFS usando recursão.

def dfs_recursivo(grafo, vertice, visitados=None):

if visitados is None:
visitados = set()

# Marca o vértice atual como visitado

[Link](vertice)
print(vertice, end=' ') # Processa o vértice

# Visita recursivamente todos os vizinhos não visitados

for vizinho in grafo[vertice]:
if vizinho not in visitados:
dfs_recursivo(grafo, vizinho, visitados)

# Exemplo
grafo = {
'A': ['B', 'C'],
 'B': ['A', 'D', 'E'],
Guia de'C':
Algoritmos
['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

dfs_recursivo(grafo, 'A') # A B D E F C

2. DFS Iterativo
Implementação usando pilha, útil para evitar estouro de pilha em grafos muito profundos.

def dfs_iterativo(grafo, inicio):

visitados = set()
pilha = [inicio]

while pilha:
vertice = [Link]()
if vertice not in visitados:
[Link](vertice)
print(vertice, end=' ')
# Adiciona vizinhos não visitados à pilha
[Link](v for v in grafo[vertice] if v not in visitados)

# Exemplo
dfs_iterativo(grafo, 'A') # A C F E B D

Aplicações Comuns
1. Detecção de Ciclos
def detecta_ciclo(grafo):
visitados = set()
pilha_recursao = set()

def dfs_ciclo(vertice):
[Link](vertice)
pilha_recursao.add(vertice)

for vizinho in grafo[vertice]:

if vizinho not in visitados:
if dfs_ciclo(vizinho):
return True
elif vizinho in pilha_recursao:
return True

pilha_recursao.remove(vertice)
return False
 for vertice in grafo:
Guia de Algoritmos
if vertice not in visitados:
if dfs_ciclo(vertice):
return True
return False

# Exemplo
grafo_ciclico = {
'A': ['B'],
'B': ['C'],
'C': ['A']
}
print(detecta_ciclo(grafo_ciclico)) # True

2. Ordenação Topológica
Útil para ordenar tarefas com dependências.

def ordenacao_topologica(grafo):
visitados = set()
pilha = []

def dfs_topologico(vertice):
[Link](vertice)

for vizinho in grafo[vertice]:

if vizinho not in visitados:
dfs_topologico(vizinho)

[Link](vertice)

for vertice in grafo:

if vertice not in visitados:
dfs_topologico(vertice)

return pilha[::-1] # Inverte a pilha

# Exemplo: Grafo de dependências

grafo_deps = {
'vestir_roupa': ['colocar_sapato'],
'colocar_sapato': [],
'tomar_banho': ['vestir_roupa'],
'escovar_dentes': []
}
print(ordenacao_topologica(grafo_deps))
# ['tomar_banho', 'vestir_roupa', 'colocar_sapato', 'escovar_dentes']

Problemas Práticos do LeetCode

200 - Number of Islands LeetCode
 695 - Max Area of Island LeetCode
Guia de Algoritmos
130 - Surrounded Regions LeetCode

417 - Pacific Atlantic Water Flow LeetCode

797 - All Paths From Source to Target LeetCode

Dicas para Entrevistas

Identifique quando usar DFS vs BFS
Considere espaço da pilha de recursão
Use versão iterativa para grafos profundos
Mantenha estado de visitados corretamente
Considere ordem de processamento dos vizinhos

Variações e Técnicas Avançadas

# DFS com caminho
def dfs_com_caminho(grafo, inicio, fim):
def dfs(vertice, caminho):
if vertice == fim:
return caminho

for vizinho in grafo[vertice]:

if vizinho not in caminho:
resultado = dfs(vizinho, caminho + [vizinho])
if resultado:
return resultado
return None

return dfs(inicio, [inicio])

# DFS com limite de profundidade

def dfs_limitado(grafo, vertice, limite, profundidade=0):
if profundidade == limite:
return

print(vertice, end=' ')

for vizinho in grafo[vertice]:
dfs_limitado(grafo, vizinho, limite, profundidade + 1)

# DFS para encontrar componentes fortemente conectados

def kosaraju_dfs(grafo):
def primeira_passagem(v, visitados, ordem):
[Link](v)
 for u in grafo[v]:
Guia de Algoritmos
if u not in visitados:
primeira_passagem(u, visitados, ordem)
[Link](v)

def segunda_passagem(v, visitados, componente):

[Link](v)
[Link](v)
for u in grafo_transposto[v]:
if u not in visitados:
segunda_passagem(u, visitados, componente)

# Primeira passagem: ordem de finalização

visitados = set()
ordem = []
for v in grafo:
if v not in visitados:
primeira_passagem(v, visitados, ordem)

# Cria grafo transposto

grafo_transposto = {v: [] for v in grafo}
for v in grafo:
for u in grafo[v]:
grafo_transposto[u].append(v)

# Segunda passagem: encontra componentes

visitados = set()
componentes = []
for v in reversed(ordem):
if v not in visitados:
componente = []
segunda_passagem(v, visitados, componente)
[Link](componente)

return componentes

# Exemplo
grafo_direcionado = {
'A': ['B'],
'B': ['C', 'D'],
'C': ['A'],
'D': ['E'],
'E': ['F'],
'F': ['D']
}
print(kosaraju_dfs(grafo_direcionado))
# [['A', 'C', 'B'], ['D', 'F', 'E']]

Próximos passos
 Após dominar DFS, explore suas aplicações em problemas mais complexos como encontrar pontes
Guiaemde Algoritmos
grafos, articulações, e componentes fortemente conectados. Também é importante estudar como
DFS se relaciona com outros algoritmos de grafos como Tarjan e Kosaraju.

Busca em Largura

Busca em Largura (BFS)

A Busca em Largura (BFS - Breadth-First Search) é um algoritmo para percorrer estruturas de dados em
forma de árvore ou grafo. O algoritmo explora todos os vértices na distância atual antes de mover para os
vértices na próxima distância.

Implementação Básica
from collections import deque

def bfs(grafo, inicio):

visitados = set([inicio])
fila = deque([inicio])

while fila:
vertice = [Link]()
print(vertice, end=' ') # Processa o vértice

for vizinho in grafo[vertice]:

if vizinho not in visitados:
[Link](vizinho)
[Link](vizinho)

# Exemplo
grafo = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

bfs(grafo, 'A') # A B C D E F

Aplicações Comuns
 1. Menor Caminho em Grafo Não Ponderado
Guia de Algoritmos
def menor_caminho(grafo, inicio, fim):
if inicio == fim:
return [inicio]

visitados = {inicio}
fila = deque([(inicio, [inicio])])

while fila:
vertice, caminho = [Link]()

for vizinho in grafo[vertice]:

if vizinho == fim:
return caminho + [vizinho]
if vizinho not in visitados:
[Link](vizinho)
[Link]((vizinho, caminho + [vizinho]))

return None # Caminho não encontrado

# Exemplo
grafo = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
print(menor_caminho(grafo, 'A', 'E')) # ['A', 'B', 'D', 'E']

2. Matriz de Distâncias
Calcula a distância mínima de um ponto inicial para todos os outros pontos.

def matriz_distancias(grafo, inicio):

distancias = {inicio: 0}
fila = deque([inicio])

while fila:
vertice = [Link]()
for vizinho in grafo[vertice]:
if vizinho not in distancias:
distancias[vizinho] = distancias[vertice] + 1
[Link](vizinho)

return distancias

# Exemplo
grafo = {
'A': ['B', 'C'],
 'B': ['A', 'D', 'E'],
Guia de'C':
Algoritmos
['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(matriz_distancias(grafo, 'A'))
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

Problemas Práticos do LeetCode

994 - Rotting Oranges LeetCode

542 - 01 Matrix LeetCode

127 - Word Ladder LeetCode

317 - Shortest Distance from All Buildings LeetCode

1162 - As Far from Land as Possible LeetCode

Dicas para Entrevistas

Use BFS para encontrar o menor caminho em grafos não ponderados
Considere usar uma matriz de visitados para problemas em grade
Mantenha controle das distâncias quando necessário
Use uma fila para garantir a ordem correta de processamento
Considere múltiplos pontos de partida quando apropriado

Variações e Técnicas Avançadas

1. BFS em Matriz
def bfs_matriz(matriz, inicio_i, inicio_j):
if not matriz or not matriz[0]:
return

n, m = len(matriz), len(matriz[0])
visitados = set([(inicio_i, inicio_j)])
fila = deque([(inicio_i, inicio_j, 0)]) # (i, j, distância)
direcoes = [(0, 1), (1, 0), (0, -1), (-1, 0)] # direita, baixo, esquerda, cima

while fila:
i, j, dist = [Link]()
print(f'({i},{j}) distância: {dist}')
Guia de Algoritmos
for di, dj in direcoes:
novo_i, novo_j = i + di, j + dj
if (0 <= novo_i < n and 0 <= novo_j < m and
(novo_i, novo_j) not in visitados and
matriz[novo_i][novo_j] == 1): # assume 1 como célula válida
[Link]((novo_i, novo_j))
[Link]((novo_i, novo_j, dist + 1))

# Exemplo
matriz = [
[1, 1, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 1]
]
bfs_matriz(matriz, 0, 0)

2. BFS Bidirecional
Busca a partir do início e do fim simultaneamente, útil para encontrar o menor caminho.

def bfs_bidirecional(grafo, inicio, fim):

if inicio == fim:
return [inicio]

# Inicializa as duas buscas

frente = {inicio: [inicio]}
tras = {fim: [fim]}
visitados_frente = {inicio}
visitados_tras = {fim}

while frente and tras:

# Expande a partir do início
novos_frente = {}
for vertice in frente:
for vizinho in grafo[vertice]:
if vizinho in visitados_tras:
# Encontrou um caminho
return frente[vertice] + tras[vizinho][::-1][1:]
if vizinho not in visitados_frente:
visitados_frente.add(vizinho)
novos_frente[vizinho] = frente[vertice] + [vizinho]
frente = novos_frente

# Expande a partir do fim

novos_tras = {}
for vertice in tras:
for vizinho in grafo[vertice]:
if vizinho in visitados_frente:
# Encontrou um caminho
return frente[vizinho] + tras[vertice][::-1][1:]
if vizinho not in visitados_tras:
 visitados_tras.add(vizinho)
Guia de Algoritmos novos_tras[vizinho] = tras[vertice] + [vizinho]
tras = novos_tras

return None # Caminho não encontrado

# Exemplo
grafo = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs_bidirecional(grafo, 'A', 'F')) # ['A', 'C', 'F']

Próximos passos
Após dominar BFS, explore suas aplicações em problemas mais complexos como busca em múltiplas
fontes, problemas de roteamento em redes e otimização de caminhos. Também é importante estudar
como BFS se relaciona com algoritmos de caminho mínimo como Dijkstra e com problemas de fluxo
em redes.

Árvores Binárias

Árvores Binárias
Árvores binárias são estruturas de dados hierárquicas onde cada nó tem no máximo dois filhos,
geralmente chamados de filho esquerdo e filho direito. São amplamente utilizadas em problemas que
envolvem hierarquia, busca e ordenação.

Implementação Básica
class No:
def __init__(self, valor=0, esquerda=None, direita=None):
[Link] = valor
[Link] = esquerda
[Link] = direita
 # Exemplo de criação de uma árvore
Guia
# de Algoritmos
1
# / \
# 2 3
# / \
# 4 5

raiz = No(1)
[Link] = No(2)
[Link] = No(3)
[Link] = No(4)
[Link] = No(5)

Travessias
1. Percurso em Ordem (Inorder)
Visita o filho esquerdo, a raiz e depois o filho direito.

def inorder(raiz):
if not raiz:
return

inorder([Link])
print([Link], end=' ')
inorder([Link])

# Versão iterativa
def inorder_iterativo(raiz):
pilha = []
atual = raiz

while atual or pilha:

# Vai até o nó mais à esquerda
while atual:
[Link](atual)
atual = [Link]

atual = [Link]()
print([Link], end=' ')
atual = [Link]

# Para a árvore do exemplo: 4 2 5 1 3

2. Percurso em Pré-ordem (Preorder)

Visita a raiz, depois o filho esquerdo e por fim o filho direito.

def preorder(raiz):
if not raiz:
 return
Guia de Algoritmos
print([Link], end=' ')
preorder([Link])
preorder([Link])

# Versão iterativa
def preorder_iterativo(raiz):
if not raiz:
return

pilha = [raiz]
while pilha:
no = [Link]()
print([Link], end=' ')

if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])

# Para a árvore do exemplo: 1 2 4 5 3

3. Percurso em Pós-ordem (Postorder)

Visita o filho esquerdo, o filho direito e por fim a raiz.

def postorder(raiz):
if not raiz:
return

postorder([Link])
postorder([Link])
print([Link], end=' ')

# Versão iterativa
def postorder_iterativo(raiz):
if not raiz:
return

pilha1 = [raiz]
pilha2 = []

while pilha1:
no = [Link]()
[Link](no)

if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
 while pilha2:
Guia de Algoritmos
no = [Link]()
print([Link], end=' ')

# Para a árvore do exemplo: 4 5 2 3 1

Operações Comuns
1. Altura da Árvore
def altura(raiz):
if not raiz:
return 0
return 1 + max(altura([Link]), altura([Link]))

# Versão iterativa usando BFS

from collections import deque

def altura_iterativa(raiz):
if not raiz:
return 0

altura = 0
fila = deque([raiz])

while fila:
nivel_tamanho = len(fila)

for _ in range(nivel_tamanho):
no = [Link]()
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])

altura += 1

return altura

2. Verificação de Árvore Binária de Busca (BST)

def eh_bst(raiz, minimo=float('-inf'), maximo=float('inf')):
if not raiz:
return True

if [Link] <= minimo or [Link] >= maximo:

return False

return (eh_bst([Link], minimo, [Link]) and

eh_bst([Link], [Link], maximo))
Guia de Algoritmos
# Versão usando travessia inorder
def eh_bst_inorder(raiz):
anterior = float('-inf')

def inorder(no):
nonlocal anterior
if not no:
return True

if not inorder([Link]):
return False

if [Link] <= anterior:

return False
anterior = [Link]

return inorder([Link])

return inorder(raiz)

Problemas Práticos do LeetCode

94 - Binary Tree Inorder Traversal LeetCode

144 - Binary Tree Preorder Traversal LeetCode

145 - Binary Tree Postorder Traversal LeetCode

104 - Maximum Depth of Binary Tree LeetCode

98 - Validate Binary Search Tree LeetCode

Dicas para Entrevistas

Considere soluções recursivas e iterativas
Use BFS para problemas relacionados a níveis
Mantenha controle dos limites em problemas de BST
Pense em casos especiais (árvore vazia, um nó)
Considere usar variáveis globais ou classes auxiliares

Técnicas Avançadas
# Serialização e Deserialização
def serializar(raiz):
 if not raiz:
Guia de Algoritmos
return "null"
return f"{[Link]},{serializar([Link])},{serializar([Link])}"

def deserializar(dados):
def dfs():
val = next(valores)
if val == "null":
return None
no = No(int(val))
[Link] = dfs()
[Link] = dfs()
return no

valores = iter([Link](','))
return dfs()

# Construção de Árvore a partir de Travessias

def constroi_arvore(inorder, preorder):
if not inorder:
return None

raiz_valor = preorder[0]
raiz = No(raiz_valor)

indice = [Link](raiz_valor)

[Link] = constroi_arvore(inorder[:indice],
preorder[1:indice+1])
[Link] = constroi_arvore(inorder[indice+1:],
preorder[indice+1:])

return raiz

# Menor Ancestral Comum (LCA)

def lca(raiz, p, q):
if not raiz or [Link] == p or [Link] == q:
return raiz

esquerda = lca([Link], p, q)
direita = lca([Link], p, q)

if esquerda and direita:

return raiz
return esquerda if esquerda else direita

Próximos passos
Após dominar árvores binárias básicas, explore estruturas mais avançadas como árvores AVL,
árvores Rubro-Negras e B-Trees. Também é importante estudar aplicações práticas como índices de
 banco de dados e estruturas de dados persistentes.
Guia de Algoritmos

Programação Dinâmica

Programação Dinâmica (DP)

Programação Dinâmica é uma técnica de otimização que resolve problemas complexos dividindo-os em
subproblemas mais simples. A chave é armazenar os resultados dos subproblemas para evitar recálculos,
um processo chamado de "memoização".

Conceitos Fundamentais
1. Fibonacci com DP
Exemplo clássico que mostra a diferença entre abordagem recursiva e DP.

# Recursivo (exponencial)
def fib_recursivo(n):
if n <= 1:
return n
return fib_recursivo(n-1) + fib_recursivo(n-2)

# DP Top-Down (memoização)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n

memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)

return memo[n]

# DP Bottom-Up (tabulação)
def fib_tabela(n):
if n <= 1:
return n

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):

dp[i] = dp[i-1] + dp[i-2]
Guia dereturn
Algoritmos
dp[n]

# Versão otimizada de espaço

def fib_otimizado(n):
if n <= 1:
return n

a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b

return b

2. Problema da Mochila (Knapsack)

Problema clássico de otimização com restrições.

def mochila(valores, pesos, capacidade):

n = len(valores)
dp = [[0] * (capacidade + 1) for _ in range(n + 1)]

for i in range(1, n + 1):

for w in range(capacidade + 1):
if pesos[i-1] <= w:
dp[i][w] = max(valores[i-1] + dp[i-1][w-pesos[i-1]],
dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]

return dp[n][capacidade]

# Exemplo
valores = [60, 100, 120]
pesos = [10, 20, 30]
capacidade = 50
print(mochila(valores, pesos, capacidade)) # 220

3. Subsequência Comum Mais Longa (LCS)

Encontra a maior subsequência comum entre duas strings.

def lcs(texto1, texto2):

m, n = len(texto1), len(texto2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):

for j in range(1, n + 1):
if texto1[i-1] == texto2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
 else:
Guia de Algoritmos
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# Reconstruir a subsequência
subsequencia = []
i, j = m, n
while i > 0 and j > 0:
if texto1[i-1] == texto2[j-1]:
[Link](texto1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1

return ''.join(reversed(subsequencia))

# Exemplo
print(lcs("ABCDGH", "AEDFHR")) # "ADH"

Problemas Práticos do LeetCode

70 - Climbing Stairs LeetCode

322 - Coin Change LeetCode

300 - Longest Increasing Subsequence LeetCode

1143 - Longest Common Subsequence LeetCode

516 - Longest Palindromic Subsequence LeetCode

Dicas para Entrevistas

Identifique a subestrutura ótima
Defina a relação de recorrência
Decida entre top-down ou bottom-up
Considere otimizações de espaço
Teste com casos pequenos primeiro

Padrões Comuns
1. Subsequência Crescente Mais Longa (LIS)
Guia deifAlgoritmos
def lis(nums):
not nums:
return 0

n = len(nums)
dp = [1] * n # dp[i] é o tamanho da LIS terminando em nums[i]

for i in range(1, n):

for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

# Versão O(n log n)

from bisect import bisect_left

def lis_otimizado(nums):
pilha = []

for num in nums:

if not pilha or num > pilha[-1]:
[Link](num)
else:
idx = bisect_left(pilha, num)
pilha[idx] = num

return len(pilha)

# Exemplo
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis(nums)) # 4 ([2, 3, 7, 101])

2. Soma do Caminho Mínimo

def caminho_minimo(grid):
if not grid:
return 0

m, n = len(grid), len(grid[0])
dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
dp[0][1] = dp[1][0] = 0

for i in range(1, m + 1):

for j in range(1, n + 1):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

return dp[m][n]

# Versão com otimização de espaço

def caminho_minimo_otimizado(grid):
 if not grid:
Guia de Algoritmos
return 0

m, n = len(grid), len(grid[0])
dp = [float('inf')] * (n + 1)
dp[1] = 0

for i in range(1, m + 1):

novo_dp = [float('inf')] * (n + 1)
for j in range(1, n + 1):
novo_dp[j] = min(dp[j], novo_dp[j-1]) + grid[i-1][j-1]
dp = novo_dp

return dp[n]

# Exemplo
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(caminho_minimo(grid)) # 7

Próximos passos
Após dominar os conceitos básicos de DP, explore problemas mais complexos como programação
dinâmica em árvores, problemas de particionamento e otimização de expressões. Também é
importante estudar a relação entre DP e outros paradigmas como algoritmos gulosos e divisão e
conquista.

Trie

Trie (Árvore de Prefixos)

Uma Trie, também conhecida como árvore de prefixos, é uma estrutura de dados em forma de árvore
otimizada para busca e armazenamento de strings. É especialmente útil para autocompletar, verificação
ortográfica e problemas de correspondência de prefixos.

Implementação Básica
Guia dedefAlgoritmos
class TrieNode:
__init__(self):
[Link] = {} # Mapa de caractere para nó filho
self.is_end = False # Marca fim de palavra

class Trie:
def __init__(self):
[Link] = TrieNode()

def insert(self, word: str) -> None:

node = [Link]
for char in word:
if char not in [Link]:
[Link][char] = TrieNode()
node = [Link][char]
node.is_end = True

def search(self, word: str) -> bool:

node = [Link]
for char in word:
if char not in [Link]:
return False
node = [Link][char]
return node.is_end

def starts_with(self, prefix: str) -> bool:

node = [Link]
for char in prefix:
if char not in [Link]:
return False
node = [Link][char]
return True

# Exemplo de uso
trie = Trie()
[Link]("apple")
print([Link]("apple")) # True
print([Link]("app")) # False
print(trie.starts_with("app")) # True

Aplicações Comuns
1. Autocompletar
class TrieNode:
def __init__(self):
[Link] = {}
self.is_end = False
[Link] = [] # Lista de sugestões para autocompletar

class Autocomplete:
 def __init__(self):
Guia de Algoritmos
[Link] = TrieNode()

def insert(self, word: str) -> None:

node = [Link]
prefix = ""
for char in word:
prefix += char
if char not in [Link]:
[Link][char] = TrieNode()
node = [Link][char]
if len([Link]) < 3: # Mantém top 3 sugestões
[Link](word)
node.is_end = True

def search(self, prefix: str) -> list:

node = [Link]
for char in prefix:
if char not in [Link]:
return []
node = [Link][char]
return [Link]

# Exemplo
auto = Autocomplete()
palavras = ["amor", "amigo", "amizade", "amar", "alegria"]
for palavra in palavras:
[Link](palavra)
print([Link]("am")) # ['amor', 'amigo', 'amizade']

2. Verificador Ortográfico
class SpellChecker:
def __init__(self):
[Link] = Trie()

def add_to_dictionary(self, words):

for word in words:
[Link](word)

def suggest_corrections(self, word, max_distance=1):

def dfs(node, prefix, distance):
suggestions = []
if node.is_end and distance <= max_distance:
[Link](prefix)

for char in [Link]:

if char == word[len(prefix)] if len(prefix) < len(word) else False
[Link](dfs([Link][char], prefix + char, dist
elif distance < max_distance:
# Substituição
[Link](dfs([Link][char], prefix + char, dist
 return suggestions
Guia de Algoritmos
return dfs([Link], "", 0)

# Exemplo
checker = SpellChecker()
checker.add_to_dictionary(["casa", "carro", "carta", "caso"])
print(checker.suggest_corrections("casa")) # ['casa']
print(checker.suggest_corrections("caza")) # ['casa']

Problemas Práticos do LeetCode

208 - Implement Trie Prefix Tree LeetCode

211 - Design Add and Search Words Data Structure LeetCode

212 - Word Search II LeetCode

421 - Maximum XOR of Two Numbers in an Array LeetCode

648 - Replace Words LeetCode

Dicas para Entrevistas

Use Trie quando trabalhar com strings e prefixos
Considere o trade-off entre espaço e tempo
Lembre-se de marcar o fim das palavras
Pense em otimizações como compressão de caminhos
Combine com outras estruturas quando necessário

Otimizações Avançadas
class CompressedTrieNode:
def __init__(self):
[Link] = {}
self.is_end = False
[Link] = "" # Armazena prefixo comprimido

class CompressedTrie:
def __init__(self):
[Link] = CompressedTrieNode()

def insert(self, word: str) -> None:

node = [Link]
i = 0
 while i < len(word):
Guia de Algoritmos
if not [Link]:
# Nó folha, adiciona todo o resto da palavra
[Link][word[i]] = CompressedTrieNode()
[Link][word[i]].prefix = word[i:]
[Link][word[i]].is_end = True
break

if word[i] not in [Link]:

# Adiciona novo nó com prefixo
[Link][word[i]] = CompressedTrieNode()
[Link][word[i]].prefix = word[i:]
[Link][word[i]].is_end = True
break

node = [Link][word[i]]
prefix = [Link]

# Encontra o ponto de divergência

j = 0
while j < len(prefix) and i < len(word) and prefix[j] == word[i]:
i += 1
j += 1

if j < len(prefix):
# Divide o nó atual
novo_no = CompressedTrieNode()
novo_no.prefix = prefix[j:]
novo_no.is_end = node.is_end
novo_no.children = [Link]

[Link] = prefix[:j]
node.is_end = (i == len(word))
[Link] = {prefix[j]: novo_no}

if i < len(word):
continue
else:
node.is_end = True
break

# Exemplo
trie = CompressedTrie()
[Link]("romane")
[Link]("romanus")
[Link]("romulus")
[Link]("rubens")

Próximos passos
 Após dominar os conceitos básicos de Trie, explore variações como Ternary Search Tree, Radix Tree
Guiae Suffix
de Algoritmos
Tree. Estude também aplicações práticas em sistemas de autocompletar, corretores
ortográficos e processamento de linguagem natural.