Array e String
1. Soma de Dois Números (Two Sum)
Dado um array de números inteiros nums e um alvo target, retorne os índices dos dois números que somam ao alvo.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> indicador;
for (int i = 0; i < nums.size(); ++i) {
int complemento = target - nums[i];
if (indicador.count(complemento)) {
return {indicador[complemento], i};
}
indicador[nums[i]] = i;
}
return {};
}
};
15. Soma de Três (Three Sum)
Encontre todos os tripletos únicos no array que somam zero.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> resultado;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int esquerda = i + 1, direita = n - 1;
while (esquerda < direita) {
int soma = nums[i] + nums[esquerda] + nums[direita];
if (soma > 0) {
--direita;
} else if (soma < 0) {
++esquerda;
} else {
resultado.push_back({nums[i], nums[esquerda], nums[direita]});
while (esquerda < direita && nums[esquerda] == nums[esquerda + 1]) ++esquerda;
while (esquerda < direita && nums[direita] == nums[direita - 1]) --direita;
++esquerda;
--direita;
}
}
}
return resultado;
}
};
11. Recipiente com Mais Água (Container With Most Water)
Dado n linhas verticais, encontre duas linhas que formam um recipiente contendo a maior quantidade de água.
class Solution {
public:
int maxArea(vector<int>& altura) {
int i = 0, j = altura.size() - 1, area_max = 0;
while (i < j) {
int h = min(altura[i], altura[j]);
area_max = max(area_max, h * (j - i));
if (altura[i] < altura[j]) ++i;
else --j;
}
return area_max;
}
};
42. Chuva (Trapping Rain Water)
Dado n números inteiros representando a elevação do terreno, calcule a quantidade de água que pode ser retida após a chuva.
class Solution {
public:
int trap(vector<int>& altura) {
int n = altura.size();
if (n < 3) return 0;
vector<int> esquerda_max(n), direita_max(n);
esquerda_max[0] = altura[0];
for (int i = 1; i < n; ++i) {
esquerda_max[i] = max(esquerda_max[i - 1], altura[i]);
}
direita_max[n - 1] = altura[n - 1];
for (int i = n - 2; i >= 0; --i) {
direita_max[i] = max(direita_max[i + 1], altura[i]);
}
int agua_total = 0;
for (int i = 0; i < n; ++i) {
int nivel_agua = min(esquerda_max[i], direita_max[i]);
agua_total += max(0, nivel_agua - altura[i]);
}
return agua_total;
}
};
Técnicas de Deslizamento de Janela (Sliding Window)
3. Maior Substrign Sem Caracteres Repetidos (Longest Substring Without Repeating Characters)
Dada uma string s, encontre o comprimento da maior substring sem caracteres repetidos.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> janela;
int max_len = 0, esq = 0;
for (int dir = 0; dir < s.size(); ++dir) {
while (janela.count(s[dir])) {
janela.erase(s[esq++]);
}
janela.insert(s[dir]);
max_len = max(max_len, dir - esq + 1);
}
return max_len;
}
};
438. Todas as Anagramas em Uma String (Find All Anagrams in a String)
Dada uma string s e uma string p, encontre todos os índices de início de anagramas de p em s.
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int s_len = s.size(), p_len = p.size();
if (s_len < p_len) return {};
vector<int> contagem_p(26, 0), contagem_s(26, 0), indices;
for (char c : p) contagem_p[c - 'a']++;
for (int i = 0; i < s_len; ++i) {
contagem_s[s[i] - 'a']++;
if (i >= p_len) contagem_s[s[i - p_len] - 'a']--;
if (contagem_s == contagem_p) indices.push_back(i - p_len + 1);
}
return indices;
}
};
239. Valor Máximo da Janela Dselizante (Sliding Window Maximum)
Dado um array de inteiros nums e um tamanho de janela k, retorne o valor máximo em cada janela deslizante.
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> fila; // Índices dos elementos, valores em ordem decrescente
vector<int> resultado;
for (int i = 0; i < nums.size(); ++i) {
// Remove índices fora da janela atual
while (!fila.empty() && fila.front() <= i - k) fila.pop_front();
// Mantém a fila em ordem decrescente
while (!fila.empty() && nums[fila.back()] < nums[i]) fila.pop_back();
fila.push_back(i);
if (i >= k - 1) resultado.push_back(nums[fila.front()]);
}
return resultado;
}
};
Hash Map e Prefixo
560. Subarray com Soma Igual a K (Subarray Sum Equals K)
Dado um array de inteiros nums e um inteiro k, retorne o número total de subarrays cuja soma é igual a k.
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixos;
prefixos[0] = 1;
int soma_atual = 0, contador = 0;
for (int num : nums) {
soma_atual += num;
contador += prefixos[soma_atual - k];
prefixos[soma_atual]++;
}
return contador;
}
};
238. Produto do Array Exceto a Si Mesmo (Product of Array Except Self)
Dado um array de inteiros nums, retorne um array answer tal que answer[i] é o produto de todos os elementos de nums exceto nums[i].
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> produtos_esquerda(n, 1), produtos_direita(n, 1), resultado(n);
for (int i = 1; i < n; ++i) {
produtos_esquerda[i] = produtos_esquerda[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; --i) {
produtos_direita[i] = produtos_direita[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; ++i) {
resultado[i] = produtos_esquerda[i] * produtos_direita[i];
}
return resultado;
}
};
Algoritmos de Ordenação e Busca
75. Classificar Cores (Sort Colors / Dutch National Flag Problem)
Dado um array nums com objetos representados por 0, 1 e 2, ordene-os in-place.
class Solution {
public:
void sortColors(vector<int>& nums) {
int baixo = 0, meio = 0, alto = nums.size() - 1;
while (meio <= alto) {
if (nums[meio] == 0) {
swap(nums[meio++], nums[baixo++]);
} else if (nums[meio] == 1) {
++meio;
} else {
swap(nums[meio], nums[alto--]);
}
}
}
};
215. K-ésimo Maior Elemento em um Array (Kth Largest Element in an Array)
Dado um array de inteiros nums e um inteiro k, retorne o k-ésimo maior elemento.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// Ajusta para encontrar o (n - k)-ésimo menor
return busca_rapida(nums, 0, nums.size() - 1, nums.size() - k);
}
private:
int busca_rapida(vector<int>& arr, int esq, int dir, int k_posicao) {
if (esq == dir) return arr[esq];
int pivo_idx = particionar(arr, esq, dir);
if (k_posicao == pivo_idx) {
return arr[k_posicao];
} else if (k_posicao < pivo_idx) {
return busca_rapida(arr, esq, pivo_idx - 1, k_posicao);
} else {
return busca_rapida(arr, pivo_idx + 1, dir, k_posicao);
}
}
int particionar(vector<int>& arr, int esq, int dir) {
int pivo = arr[esq];
int i = esq + 1, j = dir;
while (true) {
while (i <= j && arr[i] < pivo) ++i;
while (i <= j && arr[j] > pivo) --j;
if (i >= j) break;
swap(arr[i++], arr[j--]);
}
swap(arr[esq], arr[j]);
return j;
}
};
Estrutura de Dados: Lista Ligada (Linked List)
Problemas Fundamentais
Conhecimento básico essencial:
- Inversão de Lista: Use um ponteiro
previnicializado comonullptr. Itere, guardando o próximo, redirecionando o atual paraprev, e avançando ambos. - Ponteiro Lento/Rápido (Slow/Fast): Para encontrar o meio, avance lento por 1 e rápido por 2. O lento estará no meio quando rápido chegar ao fim.
- Detectar Ciclo: Use lento/rápido. Se se encontrarem, há ciclo. Para achar o início, mova um ponteiro de volta ao início e avance ambos um por um até se encontrarem novamente.
- Nó Cabeça Fictícia (Dummy Head): Simplifica operações que podem modificar a cabeça, como remoções no início.
206. Inverter Lista Ligada (Reverse Linked List)
Inverta uma lista ligada simples.
ListNode* inverterLista(ListNode* cabeca) {
ListNode* anterior = nullptr;
ListNode* atual = cabeca;
while (atual) {
ListNode* proximo = atual->next;
atual->next = anterior;
anterior = atual;
atual = proximo;
}
return anterior;
}
19. Remover o N-ésimo Nó do Final (Remove Nth Node From End of List)
Dada a cabeça de uma lista ligada, remova o n-ésimo nó do final da lista e retorne sua cabeça.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* cabeca, int n) {
ListNode* dummy = new ListNode(0, cabeca);
ListNode* rapido = dummy;
ListNode* lento = dummy;
// Avança o rápido n+1 passos
for (int i = 0; i <= n; ++i) {
rapido = rapido->next;
}
// Quando rápido chegar ao final, lento estará no nó anterior ao a ser removido
while (rapido) {
rapido = rapido->next;
lento = lento->next;
}
lento->next = lento->next->next;
return dummy->next;
}
};
148. Ordenar Lista Ligada (Sort List)
Ordene a lista ligada em ordem crescente usando Merge Sort.
class Solution {
public:
ListNode* sortList(ListNode* cabeca) {
if (!cabeca || !cabeca->next) return cabeca;
ListNode* meio = encontrarMeio(cabeca);
ListNode* direita = meio->next;
meio->next = nullptr;
ListNode* esquerda_ordenada = sortList(cabeca);
ListNode* direita_ordenada = sortList(direita);
return mesclarListas(esquerda_ordenada, direita_ordenada);
}
private:
ListNode* encontrarMeio(ListNode* cabeca) {
ListNode* lento = cabeca, *rapido = cabeca->next;
while (rapido && rapido->next) {
lento = lento->next;
rapido = rapido->next->next;
}
return lento;
}
ListNode* mesclarListas(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cauda = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cauda->next = l1;
l1 = l1->next;
} else {
cauda->next = l2;
l2 = l2->next;
}
cauda = cauda->next;
}
cauda->next = l1 ? l1 : l2;
return dummy->next;
}
};
23. Mesclar K Listas Ligadas (Merge k Sorted Lists)
Dado um array de k listas ligadas, cada uma ordenada em ordem crescente, mesclar todas as listas em uma única lista ligada ordenada.
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& listas) {
auto comparar = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(comparar)> fila_prioridade(comparar);
for (ListNode* lista : listas) {
if (lista) fila_prioridade.push(lista);
}
ListNode* dummy = new ListNode(0);
ListNode* cauda = dummy;
while (!fila_prioridade.empty()) {
ListNode* no_min = fila_prioridade.top();
fila_prioridade.pop();
cauda->next = no_min;
cauda = cauda->next;
if (no_min->next) fila_prioridade.push(no_min->next);
}
return dummy->next;
}
};
Árvores
Problemas Fundamentais
Percursos: Pré-ordem, em-ordem, pós-ordem, nível por nível. Para uma Árvore Binária de Busca (BST), o percurso em-ordem resulta em uma sequência ordenada.
226. Inverter Árvore Binária (Invert Binary Tree)
Inverta uma árvore binária.
class Solution {
public:
TreeNode* invertTree(TreeNode* raiz) {
if (!raiz) return nullptr;
TreeNode* esquerda_invertida = invertTree(raiz->left);
TreeNode* direita_invertida = invertTree(raiz->right);
raiz->left = direita_invertida;
raiz->right = esquerda_invertida;
return raiz;
}
};
236. Ancestral Comum Mais Próximo de Uma Árvore Binária (Lowest Common Ancestor of a Binary Tree)
Dada uma árvore binária, encontre o ancestral comum mais baixo (LCA) de dois nós fornecidos.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* raiz, TreeNode* p, TreeNode* q) {
if (!raiz || raiz == p || raiz == q) return raiz;
TreeNode* esquerda = lowestCommonAncestor(raiz->left, p, q);
TreeNode* direita = lowestCommonAncestor(raiz->right, p, q);
if (esquerda && direita) return raiz;
return esquerda ? esquerda : direita;
}
};
124. Maior Soma de Caminho em Árvore Binária (Binary Tree Maximum Path Sum)
Dada uma árvore binária de números inteiros, retorne a soma máxima de um caminho.
class Solution {
public:
int maxPathSum(TreeNode* raiz) {
int max_soma_global = INT_MIN;
calcularMaximo(raiz, max_soma_global);
return max_soma_global;
}
private:
int calcularMaximo(TreeNode* no, int& max_global) {
if (!no) return 0;
int max_esq = max(0, calcularMaximo(no->left, max_global));
int max_dir = max(0, calcularMaximo(no->right, max_global));
max_global = max(max_global, no->val + max_esq + max_dir);
return no->val + max(max_esq, max_dir);
}
};
Algoritmos de Grafos
200. Número de Ilhas (Number of Islands)
Dado um grid 2D de '1's (terra) e '0's (água), conte o número de ilhas.
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int ilhas = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++ilhas;
bfs(grid, i, j);
}
}
}
return ilhas;
}
private:
void bfs(vector<vector<char>>& grid, int linha, int coluna) {
queue<pair<int, int>> fila;
fila.push({linha, coluna});
grid[linha][coluna] = '0';
vector<int> dirs = {0, 1, 0, -1, 0};
while (!fila.empty()) {
auto [x, y] = fila.front(); fila.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d], ny = y + dirs[d + 1];
if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
fila.push({nx, ny});
}
}
}
}
};
207. Curso (Course Schedule)
Há um total de numCourses cursos que você precisa fazer. Determine se é possível finalizar todos os cursos.
class Solution {
public:
bool canFinish(int numCursos, vector<vector<int>>& prerequisitos) {
vector<int> grauEntrada(numCursos, 0);
unordered_map<int, vector<int>> adjacencias;
for (auto& pre : prerequisitos) {
grauEntrada[pre[0]]++;
adjacencias[pre[1]].push_back(pre[0]);
}
queue<int> fila;
for (int i = 0; i < numCursos; ++i) {
if (grauEntrada[i] == 0) fila.push(i);
}
int concluidos = 0;
while (!fila.empty()) {
int curso = fila.front(); fila.pop();
++concluidos;
for (int vizinho : adjacencias[curso]) {
if (--grauEntrada[vizinho] == 0) {
fila.push(vizinho);
}
}
}
return concluidos == numCursos;
}
};
Programação Dinâmica (Dynamic Programming)
300. Maior Subsequência Crescente (Longest Increasing Subsequence)
Dado um array de inteiros nums, retorne o comprimento da maior subsequência estritamente crescente.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> pilha;
for (int num : nums) {
auto it = lower_bound(pilha.begin(), pilha.end(), num);
if (it == pilha.end()) {
pilha.push_back(num);
} else {
*it = num;
}
}
return pilha.size();
}
};
322. Troco (Coin Change)
Dado um array de moedas de valores diferentes e um valor total, retorne o menor número de moedas necessárias.
class Solution {
public:
int coinChange(vector<int>& moedas, int valor) {
vector<int> dp(valor + 1, valor + 1);
dp[0] = 0;
for (int v = 1; v <= valor; ++v) {
for (int moeda : moedas) {
if (v >= moeda) {
dp[v] = min(dp[v], dp[v - moeda] + 1);
}
}
}
return dp[valor] > valor ? -1 : dp[valor];
}
};
139. Quebra de Palavras (Word Break)
Dada uma string s e um dicionário de strings wordDict, retorne true se s puder ser segmentada.
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
Técnicas de Backtracking
22. Gerar Parênteses (Generate Parentheses)
Dado n pares de parênteses, gere todas as combinações de parênteses bem formados.
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> resultado;
backtrack(resultado, "", 0, 0, n);
return resultado;
}
private:
void backtrack(vector<string>& res, string caminho, int aberto, int fechado, int n) {
if (caminho.size() == n * 2) {
res.push_back(caminho);
return;
}
if (aberto < n) backtrack(res, caminho + "(", aberto + 1, fechado, n);
if (fechado < aberto) backtrack(res, caminho + ")", aberto, fechado + 1, n);
}
};
46. Permutações (Permutations)
Dado um array de inteiros distintos, retorne todas as permutações possíveis.
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> resultado;
vector<int> caminho;
vector<bool> usado(nums.size(), false);
backtrack(resultado, caminho, nums, usado);
return resultado;
}
private:
void backtrack(vector<vector<int>>& res, vector<int>& caminho, vector<int>& nums, vector<bool>& usado) {
if (caminho.size() == nums.size()) {
res.push_back(caminho);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (!usado[i]) {
usado[i] = true;
caminho.push_back(nums[i]);
backtrack(res, caminho, nums, usado);
caminho.pop_back();
usado[i] = false;
}
}
}
};
Estrutura de Dados Avançada: Cache LRU
146. Cache LRU (LRU Cache)
Implemente uma estrutura de dados Cache LRU com operações get e put em complexidade O(1).
class LRUCache {
private:
struct No {
int chave, valor;
No* anterior;
No* proximo;
No(int k, int v) : chave(k), valor(v), anterior(nullptr), proximo(nullptr) {}
};
int capacidade;
unordered_map<int, No*> mapa;
No* cabeca; // Nó sentinela
No* cauda; // Nó sentinela
void remover(No* no) {
no->anterior->proximo = no->proximo;
no->proximo->anterior = no->anterior;
}
void adicionarNaCabeca(No* no) {
no->proximo = cabeca->proximo;
no->anterior = cabeca;
cabeca->proximo->anterior = no;
cabeca->proximo = no;
}
public:
LRUCache(int cap) : capacidade(cap) {
cabeca = new No(0, 0);
cauda = new No(0, 0);
cabeca->proximo = cauda;
cauda->anterior = cabeca;
}
int get(int chave) {
if (!mapa.count(chave)) return -1;
No* no = mapa[chave];
remover(no);
adicionarNaCabeca(no);
return no->valor;
}
void put(int chave, int valor) {
if (mapa.count(chave)) {
No* no = mapa[chave];
no->valor = valor;
remover(no);
adicionarNaCabeca(no);
} else {
if (mapa.size() == capacidade) {
No* no_removido = cauda->anterior;
remover(no_removido);
mapa.erase(no_removido->chave);
delete no_removido;
}
No* novo_no = new No(chave, valor);
adicionarNaCabeca(novo_no);
mapa[chave] = novo_no;
}
}
};
Algoritmos de Ordenação por Divisão e Conquista (Divide and Conquer)
4. Mediana de Duas Matrizes Ordenadas (Median of Two Sorted Arrays)
Dada duas matrizes ordenadas de tamanho m e n, retorne a mediana das duas matrizes ordenadas.
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// Garante que nums1 é o array mais curto
if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
int m = nums1.size(), n = nums2.size();
int baixo = 0, alto = m, metade = (m + n + 1) / 2;
while (baixo <= alto) {
int i = (baixo + alto) / 2; // Elementos de nums1 na partição esquerda
int j = metade - i; // Elementos de nums2 na partição esquerda
int nums1_esq = (i == 0) ? INT_MIN : nums1[i - 1];
int nums1_dir = (i == m) ? INT_MAX : nums1[i];
int nums2_esq = (j == 0) ? INT_MIN : nums2[j - 1];
int nums2_dir = (j == n) ? INT_MAX : nums2[j];
if (nums1_esq <= nums2_dir && nums2_esq <= nums1_dir) {
// Partição correta encontrada
if ((m + n) % 2 == 1) {
return max(nums1_esq, nums2_esq);
} else {
return (max(nums1_esq, nums2_esq) + min(nums1_dir, nums2_dir)) / 2.0;
}
} else if (nums1_esq > nums2_dir) {
alto = i - 1;
} else {
baixo = i + 1;
}
}
return 0.0; // Nunca deve chegar aqui com entradas válidas
}
};