| Matrícula | Nome |
|---|---|
| 231011079 | Ana Luiza Komatsu Aroeira |
| xx/xxxxxxx | xxxx xxxx xxxxx |
O projeto são resoluções de problemas de difícil e média dificuldade que são resolvidas usando conceitos de busca, árvores e lógica de programação.
Nível: Difícil Nome: Median of Two Sorted Arrays
O exercício pede para encontrar a mediana de duas listas ordenadas (nums1 e nums2). A mediana é o valor central de um conjunto de números: se o tamanho total for ímpar, é o elemento do meio; se for par, é a média dos dois elementos centrais.
A solução implementada não realiza a fusão completa das listas, pois isso custaria tempo O(m+n). Em vez disso, aplica-se uma busca binária sobre a lista menor, de modo a encontrar uma partição válida entre as duas listas. Essa partição divide os elementos em dois grupos (esquerda e direita), garantindo que todos os valores da esquerda sejam menores ou iguais a todos os da direita.
Com a partição correta encontrada, a mediana pode ser obtida diretamente a partir das bordas dessa divisão:
Se o número total de elementos é ímpar, a mediana é o maior elemento da metade esquerda.
Se for par, a mediana é a média entre o maior elemento da metade esquerda e o menor da metade direita.
Esse problema se conecta a busca em estruturas ordenadas, um conceito importante em algoritmos e também presente em estruturas de grafos e árvores. Assim como na exploração de grafos, a ideia é percorrer o espaço de busca de forma eficiente, evitando o processamento desnecessário de todos os elementos.
Nível: Difícil Nome: Binary Tree Maximum Path Sum
O exercício pede o maior somatório de um caminho em uma árvore binária, onde um caminho é qualquer sequência de nós conectados por arestas, sem repetir nós e não precisa passar pela raiz. O path sum é a soma dos valores dos nós ao longo desse caminho.
A solução utiliza uma busca em profundidade (DFS) em pós-ordem para cada nó da árvore. Para cada nó, calculamos:
Ganho esquerdo (L): o maior valor que podemos obter começando no filho esquerdo e subindo até o nó atual sem ramificar (ou 0, se esse ganho for negativo).
Ganho direito (R): análogo para o lado direito (ou 0, se negativo).
Com esses dois ganhos, avaliamos dois cenários:
Caminho que passa pelo nó atual: node->val + L + R. Esse é um candidato global ao melhor caminho, porque aqui podemos “abrir” para os dois lados (esquerdo e direito) ao mesmo tempo, o caminho fica em “V” com o nó atual no centro. Atualizamos a melhor resposta global com esse valor.
Caminho que o nó devolve ao pai: node->val + max(L, R). Para o pai, não é possível levar os dois lados simultaneamente (senão quebraria a definição de caminho simples, pois teríamos três ramos). Por isso, o retorno da função deve ser um ramo só: o melhor entre seguir pela esquerda ou pela direita.
Também ignoramos ganhos negativos com max(0, …), pois incluir um ramo negativo só diminuiria a soma do caminho ideal. O acumulador global começa em INT_MIN para cobrir o caso em que todos os valores são negativos, assim garantimos que ao menos um nó (o de maior valor) será considerado.
Complexidade:
Tempo: O(n), cada nó é processado uma vez.
Espaço: O(h) na pilha de recursão, onde h é a altura da árvore.
Conexão com grafos:
Árvores são grafos acíclicos conectados. O que fazemos é uma busca em profundidade (DFS) típica de grafos, mas explorando a estrutura restrita de uma árvore. Calculamos localmente o melhor caminho que “passa” por um nó e propagamos apenas o melhor ramo para cima, mantendo globalmente a melhor soma encontrada.
Nível: Médio Nome: Find First and Last Position of Element in Sorted Array
O exercício pede para encontrar, em um array ordenado em ordem não decrescente, a primeira e a última posição em que um valor target aparece. Caso o valor não esteja presente, deve-se retornar [-1, -1].
A solução aproveita o fato de o array estar ordenado e utiliza busca binária, garantindo a complexidade O(log n). A ideia é aplicar duas variações da função lower_bound:
lower(target) → retorna o índice da primeira ocorrência de um valor maior ou igual a target.
lower(target+1) - 1 → retorna o índice da última ocorrência de target, já que lower(target+1) aponta para o primeiro elemento maior que o target.
Com esses dois resultados, conseguimos identificar o intervalo completo onde o target aparece. Caso lower(target) aponte para um valor diferente de target (ou esteja fora do array), significa que o elemento não existe, e retornamos [-1, -1].
Esse problema se conecta a estruturas de busca em dados ordenados, uma variação de estratégias usadas em árvores binárias de busca e até em grafos, onde a exploração é guiada por propriedades estruturais. Aqui, a ordenação dos elementos cumpre o papel de “estrutura”, permitindo que a busca binária encontre posições específicas sem percorrer todos os elementos.
Nível: Médio Nome: Validate Binary Search Tree
O exercício pede verificar se uma árvore binária é uma BST válida. Em uma BST válida:
todos os valores da subárvore esquerda de um nó são estritamente menores que o valor do nó;
todos os valores da subárvore direita são estritamente maiores;
e ambas as subárvores também devem ser BSTs.
A solução usa busca em profundidade (DFS) carregando, para cada nó, o intervalo permitido de valores (low, high):
ao descer para a esquerda, o novo limite superior vira o valor do nó (high = node->val);
ao descer para a direita, o novo limite inferior vira o valor do nó (low = node->val).
Se em algum momento node->val não estiver estritamente dentro de (low, high), a árvore viola as regras de BST e retornamos false. Para cobrir casos-limite com INT_MIN/INT_MAX, os limites iniciais usam LLONG_MIN e LLONG_MAX.
Complexidade
Tempo: O(n), cada nó é visitado uma vez.
Espaço: O(h), profundidade da recursão, onde h é a altura da árvore.
Conexão com grafos/árvores
A árvore é um grafo acíclico. A estratégia de validar a BST por propagação de restrições (intervalos) é típica em problemas de árvores: cada nó impõe limites às subestruturas, e a verificação é feita localmente e propagada pela DFS.
Usei algoritmos como busca binária e DFS para resolução dos problemas. https://github.com/edsomjr/TEP