No primeiro exercício (Problema 997 - Encontrar o Juiz), um erro comum envolve esquecer os limites do array. A solução utiliza dois arrays auxiliares para contar a confiança recebida e dada por cada pessoa.
public static int findJuiz(int totalPessoas, int[][] confianca) {
int[] confiancaRecebida = new int[totalPessoas + 1];
int[] confiancaDada = new int[totalPessoas + 1];
for (int[] par : confianca) {
int quemConfia = par[0];
int emQuemConfia = par[1];
confiancaRecebida[emQuemConfia]++;
confiancaDada[quemConfia]++;
}
for (int id = 1; id <= totalPessoas; id++) {
if (confiancaRecebida[id] == totalPessoas - 1 && confiancaDada[id] == 0) {
return id;
}
}
return -1;
}
Para o problema 977 (Quadrados de Array Orednado), a abordagem direta é elevar todos os elementos ao quadrado e ordenar o resultado.
public int[] quadradosOrdenados(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
Arrays.sort(nums);
return nums;
}
Uma solução mais eficiente emprega dois ponteiros, considerando que os maiores quadrados podem estar nas extremidades do array original devido aos números negtaivos.
public int[] quadradosOrdenadosOtimizado(int[] nums) {
int tamanho = nums.length;
int[] resultado = new int[tamanho];
int esquerda = 0;
int direita = tamanho - 1;
for (int indice = tamanho - 1; indice >= 0; indice--) {
int quadradoEsq = nums[esquerda] * nums[esquerda];
int quadradoDir = nums[direita] * nums[direita];
if (quadradoEsq > quadradoDir) {
resultado[indice] = quadradoEsq;
esquerda++;
} else {
resultado[indice] = quadradoDir;
direita--;
}
}
return resultado;
}
No problema 209 (Menor Subarray com Soma ≥ S), a técnica de janela deslizante é aplicada. A posição inicial da janela é crucial para a eficiência.
public int menorComprimentoSubarray(int alvo, int[] nums) {
int comprimentoMinimo = Integer.MAX_VALUE;
int somaAtual = 0;
int inicioJanela = 0;
for (int fimJanela = 0; fimJanela < nums.length; fimJanela++) {
somaAtual += nums[fimJanela];
while (somaAtual >= alvo) {
int comprimentoAtual = fimJanela - inicioJanela + 1;
comprimentoMinimo = Math.min(comprimentoMinimo, comprimentoAtual);
somaAtual -= nums[inicioJanela];
inicioJanela++;
}
}
return comprimentoMinimo == Integer.MAX_VALUE ? 0 : comprimentoMinimo;
}
O problema 59 (Matriz Espiral II) envolve preencher uma matriz quadrada em espiral. A lógica percorrre camadas concêntricas, atualizando constantemente os limites do preenchimento.
public int[][] gerarMatrizEspiral(int dimensao) {
int[][] matriz = new int[dimensao][dimensao];
int valor = 1;
int camada = 0;
while (valor <= dimensao * dimensao) {
// Preencher borda superior
for (int coluna = camada; coluna < dimensao - camada; coluna++) {
matriz[camada][coluna] = valor++;
}
// Preencher borda direita
for (int linha = camada + 1; linha < dimensao - camada; linha++) {
matriz[linha][dimensao - camada - 1] = valor++;
}
// Preencher borda inferior (se necessário)
if (dimensao - camada - 1 > camada) {
for (int coluna = dimensao - camada - 2; coluna >= camada; coluna--) {
matriz[dimensao - camada - 1][coluna] = valor++;
}
}
// Preencher borda esquerda (se necessário)
if (dimensao - camada - 1 > camada) {
for (int linha = dimensao - camada - 2; linha > camada; linha--) {
matriz[linha][camada] = valor++;
}
}
camada++;
}
return matriz;
}