Análise de Algoritmos e Estruturas de Dados: Resolução de Problemas Clássicos
A resolução eficiente de problemas algorítmicos requer a compreensão profunda das estruturas de dados e a aplicação de paradigmas como programação gulosa, busca em profundidade e manipulação matemática. A seguir, são apresentadas estratégias otimizadas para um conjunto de problemas clássicos.
1. Jogo de Beisebol (Baseball Game)
O problema exige o processamento de uma sequência de operações que modificam um histórico de pontuações. A abordagem ideal utiliza uma pilha para manter o registro dos valores válidos, permitindo operações de soma, duplicação e invalidação em tempo constante.
def calculate_baseball_score(ops):
stack = []
for op in ops:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'D':
stack.append(2 * stack[-1])
elif op == 'C':
stack.pop()
else:
stack.append(int(op))
return sum(stack)
2. Exponenciação Modular Dupla
Para calcular a exponenciação modular em duas etapas de forma eficiente, deve-se evitar laços de repetição ingênuos. A utilização da função nativa de potência modular reduz a complexidade de tempo exponencialmente, garantindo a validação rápida de cada conjunto de variáveis.
def find_valid_indices(variables, target):
valid_indices = []
for idx, (a, b, c, m) in enumerate(variables):
first_mod = pow(a, b, 10)
second_mod = pow(first_mod, c, m)
if second_mod == target:
valid_indices.append(idx)
return valid_indices
3. Quantidade Mínima de Retângulos para Cobrir Pontos
Como a altura dos retângulos não restringe a cobertura, o problema pode ser reduzido a uma dimensão. Projeta-se os pontos no eixo X, remove-se as coordenadas duplicadas e aplica-se uma estratégia gulosa após a ordenação, contando a quantidade mínima de segmentos de largura fixa necessários.
def min_rectangles_to_cover(points, width):
unique_x = sorted(set(x for x, y in points))
rectangles_count = 0
current_limit = -1
for x in unique_x:
if x > current_limit:
rectangles_count += 1
current_limit = x + width
return rectangles_count
4. Maximização de Pontuação com Paridade
A estratégia consiste em ordenar os valores em ordem decrescente e selecionar os maiores elementos. Caso a soma resultante seja ímpar, avalia-se a troca do menor valor ímpar selecionado pelo maior par não selecionado, ou vice-versa, assegurando que o resultado final seja par e maximizado.
def max_even_score(cards, count):
sorted_cards = sorted(cards, reverse=True)
sum_top = sum(sorted_cards[:count])
if sum_top % 2 == 0:
return sum_top
min_odd = min((x for x in sorted_cards[:count] if x % 2 != 0), default=None)
min_even = min((x for x in sorted_cards[:count] if x % 2 == 0), default=None)
max_possible = 0
for card in sorted_cards[count:]:
if card % 2 != 0 and min_even is not None:
max_possible = max(max_possible, sum_top - min_even + card)
elif card % 2 == 0 and min_odd is not None:
max_possible = max(max_possible, sum_top - min_odd + card)
return max_possible
5. Contagem de Triângulos Retângulos
Para contar os triângulos retângulos em uma matriz binária, pré-calcula-se a quantidade de células com valor 1 em cada linha e coluna. Para cada célula que contém 1, o número de triângulos onde ela atua como o vértice do ângulo reto é o produto das quantidades de 1s na mesma linha e coluna, subtraindo a própria célula.
def count_right_triangles(grid):
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
row_counts = [sum(row) for row in grid]
col_counts = [sum(grid[r][c] for r in range(rows)) for c in range(cols)]
total_triangles = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
total_triangles += (row_counts[r] - 1) * (col_counts[c] - 1)
return total_triangles
6. Pontos Máximos Dentro de um Quadrado em Expansão
Calcula-se a distância de Chebyshev de cada ponto até a origem. Ordenando os pontos por essa distância, o quadrado é expandido gradualmente. Acumula-se pontos com rótulos únicos até que um rótulo duplicado seja encontrado na mesma distância, interrompendo a contagem para garantir a unicidade.
def max_points_in_square(points, labels):
point_data = []
for i, (x, y) in enumerate(points):
dist = max(abs(x), abs(y))
point_data.append((dist, labels[i]))
point_data.sort()
max_points = 0
current_points = 0
seen_labels = set()
prev_dist = -1
for dist, label in point_data:
if dist > prev_dist:
max_points += current_points
current_points = 0
seen_labels = set()
prev_dist = dist
if label not in seen_labels:
current_points += 1
seen_labels.add(label)
else:
break
return max_points + current_points
7. Verificação de Subárvore
A verificação de se uma árvore binária é subárvore de outra requer uma função auxiliar para comparar a identidade estrutural e de valores. Utiliza-se a busca em profundidade (DFS) na árvore principle, invocando a função de comparação em cada nó até que uma correspondência exata seja encontrada.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_subtree(root, sub_root):
def is_identical(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return (node1.val == node2.val and
is_identical(node1.left, node2.left) and
is_identical(node1.right, node2.right))
def traverse(node):
if not node:
return False
if is_identical(node, sub_root):
return True
return traverse(node.left) or traverse(node.right)
return traverse(root)