Algoritmos de Arrays: Exercícios e Soluções em Java

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;
}

Tags: java Arrays TwoPointers SlidingWindow Matrix

Publicado em 6-2 17:49 por Thomas