8.1 Problema de encontrar duplicatas em um array
Problema: Dado um array de números. É necessário encontrar e retornar todas as duplicatas no array.
Solução: Usamos uma tabela hash para rastrear os números que já apareceram. Se um número aparecer novamente, adicionamos ele à lista de duplicatas.
Exemplo de implementação:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Exemplos de uso
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1)) # Saída: [2, 4]
arr2 = []
print(find_duplicates(arr2)) # Saída: []
arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3)) # Saída: []
Explicação:
- Criamos um conjunto vazio
seenpara rastrear os números únicos. - Percorremos cada elemento do array. Se o elemento já estiver em
seen, adicionamos ele à listaduplicates. - Se o elemento não for encontrado em
seen, adicionamos ele lá. - Retornamos a lista de duplicatas.
Observe que a função funciona corretamente com um array vazio e com um array sem duplicatas, retornando uma lista vazia em ambos os casos.
8.2 Problema de verificação de anagramas
Problema: Dadas duas strings. É necessário determinar se elas são anagramas (contêm os mesmos caracteres na mesma quantidade).
Solução: Usamos uma tabela hash para contar a frequência dos caracteres em ambas as strings e comparamos os resultados.
Exemplo de implementação:
def are_anagrams(str1, str2):
# Convertendo strings para minúsculas para considerar diferentes capitalizações
str1 = str1.lower()
str2 = str2.lower()
if len(str1) != len(str2):
return False
char_count = {}
# Contagem de frequência dos caracteres na primeira string
for char in str1:
char_count[char] = char_count.get(char, 0) + 1
# Subtração da frequência dos caracteres na segunda string
for char in str2:
if char in char_count:
char_count[char] -= 1
else:
return False
# Verificação se todos os valores no dicionário são iguais a 0
return all(count == 0 for count in char_count.values())
# Exemplos de uso
print(are_anagrams("listen", "silent")) # Saída: True
print(are_anagrams("hello", "world")) # Saída: False
print(are_anagrams("", "")) # Saída: True
print(are_anagrams("Tea", "Eat")) # Saída: True
Explicação:
- Se os comprimentos das strings não coincidem, não podem ser anagramas.
- Usamos um dicionário
char_countpara contar a frequência dos caracteres na primeira string. - Percorremos a segunda string e subtraímos a frequência dos caracteres.
- Verificamos se todos os valores no dicionário são iguais a zero. Se sim, as strings são anagramas.
Observe que a função considera a capitalização, convertendo ambas as strings para minúsculas antes da comparação. Também processa corretamente strings vazias, considerando-as anagramas entre si.
8.3 Problema de encontrar pares com uma soma dada
Problema: Dado um array de números e um valor de soma alvo. É necessário encontrar todos os pares de números que somam o valor alvo.
Solução: Usamos uma tabela hash para armazenar os números e verificar se eles formam um par com o número atual que dá a soma alvo.
Exemplo de implementação:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Exemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Saída: [(1, 5), (1, 5)]
Explicação:
- Criamos um conjunto vazio
seenpara rastrear os números. - Para cada número no array, calculamos seu complemento
complement(a diferença entre a soma alvo e o número atual). - Se o complemento já estiver em
seen, adicionamos o par (complement, num) à listapairs. - Adicionamos o número atual em
seen. - Retornamos a lista de pares.
É importante notar que esse algoritmo tem complexidade de tempo O(n), onde n é o número de elementos no array. Isto é significativamente mais eficiente do que a solução ingênua com um duplo loop, que tem complexidade O(n^2). Usar uma tabela hash nos permite encontrar todos os pares em uma única passagem pelo array, o que é especialmente importante ao lidar com grandes volumes de dados.
Para comparação, veja como seria a solução ingênua com complexidade de tempo O(n^2):
def find_pairs_naive(arr, target_sum):
pairs = []
n = len(arr)
for i in range(n):
for j in range(i+1, n):
if arr[i] + arr[j] == target_sum:
pairs.append((arr[i], arr[j]))
return pairs
# Exemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum)) # Saída: [(1, 5), (1, 5)]
Como se pode ver, a solução ingênua requer dois loops aninhados, o que a torna ineficiente para arrays grandes. A solução usando uma tabela hash nos permite alcançar o mesmo objetivo de forma muito mais rápida.
GO TO FULL VERSION