- Two Sum
Para resolver o problema Two Sum com complexidade O(n), utilize uma tabela de espalhamento para armazenar os números já percorridos e seus índices. Durante a iteração, verifique se o complemento (alvo - número atual) existe na tabela. Se existir, retorne os índices correspondentes.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int int=""> mapa;
vector<int> resultado;
for (int i = 0; i < nums.size(); ++i) {
int complemento = target - nums[i];
if (mapa.find(complemento) != mapa.end()) {
resultado.push_back(mapa[complemento]);
resultado.push_back(i);
return resultado;
}
mapa[nums[i]] = i;
}
return resultado;
}
};</int></int></int></int>
- Longest Substring Without Repeating Characters
Utilize uma tabela de espalhamento para registrar a posição mais recente de cada caractere. Mantenha um ponteiro para o início da substring sem repetição e atualize-o ao encontrar um caractere já visto. Calcule o comprimento máximo durante a iteração.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char int=""> posicoes;
int inicio = -1;
int maximo = 0;
for (int i = 0; i < s.length(); ++i) {
if (posicoes.find(s[i]) != posicoes.end() && posicoes[s[i]] > inicio) {
inicio = posicoes[s[i]];
}
posicoes[s[i]] = i;
maximo = max(maximo, i - inicio);
}
return maximo;
}
};</char>
- Valid Sudoku
Verifique a validade de um Sudoku usando uma tabela de espalhamento do tipo multimap para rastrear a posição de cada número. Para cada célula preenchida, confira se o número já apareceu na mesma linha, coluna ou bloco 3x3.
class Solution {
public:
bool isValidSudoku(vector<vector>>& board) {
unordered_multimap<char int="" pair="">> registro;
if (board.empty()) return false;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == '.') continue;
auto intervalo = registro.equal_range(board[i][j]);
for (auto it = intervalo.first; it != intervalo.second; ++it) {
int linha = it->second.first;
int coluna = it->second.second;
if (linha == i || coluna == j || (linha / 3 == i / 3 && coluna / 3 == j / 3)) {
return false;
}
}
registro.insert({board[i][j], {i, j}});
}
}
return true;
}
};</char></vector>
- Group Anagrams
Agrupe palavras anagramas ordenando cada string e usando-a como chave em uma tabela de espalhamento. As palavras com a mesma chave são anagramas e devem ser agrupadas.
vector<vector>> groupAnagrams(vector<string>& strs) {
map<string vector="">> agrupamentos;
for (const auto& palavra : strs) {
string chave = palavra;
sort(chave.begin(), chave.end());
agrupamentos[chave].push_back(palavra);
}
vector<vector>> resultado;
for (const auto& par : agrupamentos) {
resultado.push_back(par.second);
}
return resultado;
}</vector></string></string></vector>
- Repeated DNA Sequences
Para encontrar sequências de DNA repetidas, percorra a string com uma janela deslizante de tamanho 10. Use uma tabela de espalhamento para contar as ocorrências de cada subsequência.
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> resultado;
map<string int=""> contagem;
for (int i = 0; i + 10 <= s.size(); ++i) {
string subsequencia = s.substr(i, 10);
contagem[subsequencia]++;
if (contagem[subsequencia] == 2) {
resultado.push_back(subsequencia);
}
}
return resultado;
}
};</string></string></string>
- Happy Number
Determine se um número é feliz calculando repetidamente a soma dos quadrados de seus dígitos. Use uma tabela de espalhamento para detectar ciclos, retornando falso se um número já foi visto.
class Solution {
public:
bool isHappy(int n) {
set<int> visitados;
while (n != 1) {
if (visitados.count(n)) return false;
visitados.insert(n);
int soma = 0;
while (n > 0) {
int digito = n % 10;
soma += digito * digito;
n /= 10;
}
n = soma;
}
return true;
}
};</int>
- Count Primes
Para contar números primos até n, utilize o crivo de Eratóstenes. Inicialize um array booleano e marque os múltiplos de cada primo como não primos.
class Solution {
public:
int countPrimes(int n) {
if (n < 2) return 0;
vector<bool> ehPrimo(n, true);
ehPrimo[0] = ehPrimo[1] = false;
for (int i = 2; i * i < n; ++i) {
if (ehPrimo[i]) {
for (int j = i * i; j < n; j += i) {
ehPrimo[j] = false;
}
}
}
int contagem = 0;
for (int i = 2; i < n; ++i) {
if (ehPrimo[i]) contagem++;
}
return contagem;
}
};</bool>
- Isomorphic Strings
Verifique se duas strings são isomórficas usando duas tabelas de espalhamento para mapear caracteres entre si. Se o mapeamento não to consistente, as strings não são isomórficas.
class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s.size() != t.size()) return false;
map<char char=""> mapa1, mapa2;
for (int i = 0; i < s.size(); ++i) {
char c1 = s[i], c2 = t[i];
if ((mapa1.count(c1) && mapa1[c1] != c2) || (mapa2.count(c2) && mapa2[c2] != c1)) {
return false;
}
mapa1[c1] = c2;
mapa2[c2] = c1;
}
return true;
}
};</char>
- Contains Duplicate
Detecte duplicatas em um array usando uma tabela de espalhamento do tipo set. Se um elemento já estiver no conjunto, há duplicata.
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> conjunto;
for (int num : nums) {
if (conjunto.count(num)) return true;
conjunto.insert(num);
}
return false;
}
};</int></int>
- Contains Duplicate II
Para verificar duplicatas dentro de uma distância k, use uma tabela de espalhamento para armazenar o último índice de cada número. Calcule a diferença entre índices durante a iteração.
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int int=""> indice;
for (int i = 0; i < nums.size(); ++i) {
if (indice.count(nums[i]) && i - indice[nums[i]] <= k) {
return true;
}
indice[nums[i]] = i;
}
return false;
}
};</int></int>
- Valid Anagram
Para verificar se duas strings são anagramas, ordena-as e compare-as, ou use uma tabela de espalhamento para contar frequências de caracteres.
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
map<char int=""> frequencia;
for (char c : s) frequencia[c]++;
for (char c : t) {
frequencia[c]--;
if (frequencia[c] < 0) return false;
}
return true;
}
};</char>
- H-Index
Calcule o H-Index usando uma tabela de espalhamento ou array para contar citações. Ordene ou acumule contagens para encontrar o maior h tal que h artigos tenham pelo menos h citações.
class Solution {
public:
int hIndex(vector<int>& citations) {
if (citations.empty()) return 0;
int n = citations.size();
vector<int> contagem(n + 1, 0);
for (int c : citations) {
if (c >= n) contagem[n]++;
else contagem[c]++;
}
int total = 0;
for (int i = n; i >= 0; --i) {
total += contagem[i];
if (total >= i) return i;
}
return 0;
}
};</int></int>
- Word Pattern
Verifique se um padrão corresponde a uma string usando duas tabelas de espalhamento para mapear caracteres para palavras e vice-versa. Certifique-se de que o comprimento do padrão e o número de palavras sejam iguais.
bool wordPattern(string pattern, string str) {
map<char string=""> charParaPalavra;
map<string char=""> palavraParaChar;
istringstream iss(str);
string palavra;
int i = 0;
while (iss >> palavra) {
if (i >= pattern.size()) return false;
char c = pattern[i];
if (charParaPalavra.count(c) && charParaPalavra[c] != palavra) return false;
if (palavraParaChar.count(palavra) && palavraParaChar[palavra] != c) return false;
charParaPalavra[c] = palavra;
palavraParaChar[palavra] = c;
i++;
}
return i == pattern.size();
}</string></char>
- Bulls and Cows
Para calcular bulls e cows, use tabelas de espalhamento para contar frequências de dígitos. Primeiro, conte bulls (corretos em posição) e, em seguida, conte cows usando as frequências restantes.
string getHint(string secret, string guess) {
int bulls = 0, cows = 0;
vector<int> contagemS(10, 0), contagemG(10, 0);
for (int i = 0; i < secret.size(); ++i) {
if (secret[i] == guess[i]) {
bulls++;
} else {
contagemS[secret[i] - '0']++;
contagemG[guess[i] - '0']++;
}
}
for (int i = 0; i < 10; ++i) {
cows += min(contagemS[i], contagemG[i]);
}
return to_string(bulls) + "A" + to_string(cows) + "B";
}</int>
- Top K Frequent Elements
Encontre os k elementos mais frequentes usando uma tabela de espalhamento para contar frequências e um balde (bucket sort) para agrupar por frequência. Retorne os k maiores.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int int=""> frequencia;
for (int num : nums) frequencia[num]++;
vector<vector>> baldes(nums.size() + 1);
for (const auto& par : frequencia) {
baldes[par.second].push_back(par.first);
}
vector<int> resultado;
for (int i = baldes.size() - 1; i >= 0 && resultado.size() < k; --i) {
for (int num : baldes[i]) {
resultado.push_back(num);
if (resultado.size() == k) break;
}
}
return resultado;
}
};</int></vector></int></int></int>
- Intersection of Two Arrays
Encontre a interseção de dois arrays usando uma tabela de espalhamento para armazenar elementos do primeiro array e verificar contra o segundo, evitando duplicatas no resultado.
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> conjunto(nums1.begin(), nums1.end());
vector<int> resultado;
for (int num : nums2) {
if (conjunto.count(num)) {
resultado.push_back(num);
conjunto.erase(num);
}
}
return resultado;
}
};</int></int></int></int></int>
- Intersection of Two Arrays II
Para a interseção com duplicatas, use uma tabela de espalhamento para contar frequências no primeiro array e decremente ao percorrer o segundo.
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int int=""> contagem;
for (int num : nums1) contagem[num]++;
vector<int> resultado;
for (int num : nums2) {
if (contagem[num] > 0) {
resultado.push_back(num);
contagem[num]--;
}
}
return resultado;
}
};</int></int></int></int></int>
- Design Twitter
Implemente um sistema de Twitter usando tabelas de espalhamento para armazenar usuários, seguidores e tweets. Gerencie feeds combinando tweets de usuários seguidos.
// Implementação omitida por brevidade, mas envolve estruturas de dados como mapas e listas.
- Insert Delete GetRandom O(1)
Projete uma estrutura que suporte inserção, remoção e obtenção aleatória em tempo O(1). Use uma tabela de espalhamento e um array para acesso rápido.
// Implementação omitida por brevidade, com foco em eficiência usando hash maps e vetores.
- First Unique Character in a String
Encontre o primeiro caractere não repetido usando uma tabela de espalhamento para contar frequências e, em seguida, percorra a string para encontrar o primeiro com contagem 1.
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char int=""> contagem;
for (char c : s) contagem[c]++;
for (int i = 0; i < s.size(); ++i) {
if (contagem[s[i]] == 1) return i;
}
return -1;
}
};</char>
- Find the Difference
Encontre o caractere extra em t usando uma tabela de espalhamento para contar frequências em ambas as strings e identificar a diferença.
class Solution {
public:
char findTheDifference(string s, string t) {
unordered_map<char int=""> contagem;
for (char c : t) contagem[c]++;
for (char c : s) contagem[c]--;
for (const auto& par : contagem) {
if (par.second == 1) return par.first;
}
return ' ';
}
};</char>
- Longest Palindrome
Calcule o comprimento do maior palíndromo possível usando uma tabela de espalhamento para contar frequências de caracteres. Some pare e adicione um caractere central se disponível.
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char int=""> contagem;
for (char c : s) contagem[c]++;
int comprimento = 0;
bool temImpar = false;
for (const auto& par : contagem) {
if (par.second % 2 == 0) {
comprimento += par.second;
} else {
comprimento += par.second - 1;
temImpar = true;
}
}
if (temImpar) comprimento++;
return comprimento;
}
};</char>
- Find All Anagrams in a String
Encontre todos os anagramas de p em s usando uma janela deslizante e tabelas de espalhamento para comparar frequências de caracteres.
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> resultado;
if (s.size() < p.size()) return resultado;
vector<int> freqP(26, 0), freqS(26, 0);
for (char c : p) freqP[c - 'a']++;
for (int i = 0; i < s.size(); ++i) {
freqS[s[i] - 'a']++;
if (i >= p.size()) freqS[s[i - p.size()] - 'a']--;
if (freqS == freqP) resultado.push_back(i - p.size() + 1);
}
return resultado;
}
};</int></int></int>
- Number of Boomerangs
Conte o número de boomerangs (pares de pontos à mesma distância) usando uma tabela de espalhamento para agrupar distâncias entre pontos.
class Solution {
public:
int numberOfBoomerangs(vector<pair int="">>& points) {
int resultado = 0;
for (int i = 0; i < points.size(); ++i) {
unordered_map<int int=""> distancias;
for (int j = 0; j < points.size(); ++j) {
if (i == j) continue;
int dx = points[i].first - points[j].first;
int dy = points[i].second - points[j].second;
int dist = dx * dx + dy * dy;
distancias[dist]++;
}
for (const auto& par : distancias) {
if (par.second > 1) resultado += par.second * (par.second - 1);
}
}
return resultado;
}
};</int></pair>
- Sort Characters By Frequency
Ordene caracteres por frequência usando uma tabela de espalhamento para contar ocorrências e uma função de comparação personalizada.
class Solution {
public:
string frequencySort(string s) {
unordered_map<char int=""> contagem;
for (char c : s) contagem[c]++;
sort(s.begin(), s.end(), [&contagem](char a, char b) {
if (contagem[a] != contagem[b]) return contagem[a] > contagem[b];
return a < b;
});
return s;
}
};</char>
- 4Sum II
Resolva 4Sum II calculando somas de pares de arrays e usando uma tabela de espalhamento para contar combinações que resultam em zero.
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int int=""> somaAB;
for (int a : A) {
for (int b : B) somaAB[a + b]++;
}
int contagem = 0;
for (int c : C) {
for (int d : D) {
int alvo = -c - d;
if (somaAB.count(alvo)) contagem += somaAB[alvo];
}
}
return contagem;
}
};</int></int></int></int></int>
- Island Perimeter
Calcule o perímetro de uma ilha em uma grade percorrendo cada célula e somando bordas adjacentes a água ou fora dos limites.
class Solution {
public:
int islandPerimeter(vector<vector>>& grid) {
int perimetro = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
perimetro += 4;
if (i > 0 && grid[i - 1][j] == 1) perimetro -= 2;
if (j > 0 && grid[i][j - 1] == 1) perimetro -= 2;
}
}
}
return perimetro;
}
};</vector>
- Keyboard Row
Filtre palavras que podem ser digitadas em uma linha do teclado usando uma tabela de espalhamento ou array para mapear caracteres às linhas.
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> linhas = {2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3};
vector<string> resultado;
for (const string& palavra : words) {
int linha = linhas[tolower(palavra[0]) - 'a'];
bool mesmaLinha = true;
for (char c : palavra) {
if (linhas[tolower(c) - 'a'] != linha) {
mesmaLinha = false;
break;
}
}
if (mesmaLinha) resultado.push_back(palavra);
}
return resultado;
}
};</string></int></string></string>