561. Partição de Vetor para Soma Máxima

Este exercício exige agrupar elementos de um array para maximizar a soma dos menores valores de cada par. A estratégia mais eficiente consiste em ordenar os dados e somar os elementos localizados nas posições pares, garantindo que cada menor valor seja sempre acompanhado do seu próximo par mais próximo.

class Solucao {
public:
    int somaMaximaPares(std::vector<int>& vetor) {
        std::sort(vetor.begin(), vetor.end());
        int acumulador = 0;
        for (size_t k = 0; k < vetor.size(); k += 2) {
            acumulador += vetor[k];
        }
        return acumulador;
    }
};

566. Reorganização de Matrizes

O objetivo é transformar uma matriz bidimensional em outra de dimensões diferentes, mantendo a ordem original dos elementos. A técnica utiliza indexação linear, convertendo posições bidimensionais em um único índice sequencial e aplicando operações de divisão e módulo para mapear corretamente as novas coordenadas.

class Solucao {
public:
    std::vector<std::vector<int>> transformarMatriz(const std::vector<std::vector<int>>& origem, int r, int c) {
        int totalLinhas = origem.size();
        int totalCols = origem[0].size();
        if (totalLinhas * totalCols != r * c) {
            return origem;
        }

        std::vector<std::vector<int>> resultado(r, std::vector<int>(c));
        for (int posicao = 0; posicao < totalLinhas * totalCols; ++posicao) {
            resultado[posicao / c][posicao % c] = origem[posicao / totalCols][posicao % totalCols];
        }
        return resultado;
    }
};

572. Subárvore em Estruturas Binárias

A verificação de subárvore requer duas passagens recursivas. Primeiro, compara-se a esturtura completa a partir de um nó específico; segundo, percorre-se a árvore principle em busca de um ponto de partida que inicie uma correspondência válida com a árvore secundária.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solucao {
public:
    bool verificaEstrutura(TreeNode* noAtual, TreeNode* noComparacao) {
        if (!noAtual && !noComparacao) return true;
        if (!noAtual || !noComparacao || noAtual->val != noComparacao->val) return false;
        return verificaEstrutura(noAtual->left, noComparacao->left) &&
               verificaEstrutura(noAtual->right, noComparacao->right);
    }

    bool contemSubarvore(TreeNode* raiz, TreeNode* subRaiz) {
        if (!raiz) return false;
        if (verificaEstrutura(raiz, subRaiz)) return true;
        return contemSubarvore(raiz->left, subRaiz) || contemSubarvore(raiz->right, subRaiz);
    }
};

264. Sequência de Números Feios

Números que possuem apenas 2, 3 ou 5 como fatores primos podem ser gerados sequencialmente através de programação dinâmica. Utilizando três ponteiros independentes, cada um rastreado para um multiplicador específico, é possível construir a série em ordem crescente sem gerar duplicatas ou valores inválidos.

class Solucao {
public:
    int buscarNesimoFeio(int limite) {
        std::vector<int> sequencia(1, 1);
        int idx2 = 0, idx3 = 0, idx5 = 0;

        while (sequencia.size() < static_cast<size_t>(limite)) {
            int prox2 = sequencia[idx2] * 2;
            int prox3 = sequencia[idx3] * 3;
            int prox5 = sequencia[idx5] * 5;

            int menor = std::min({prox2, prox3, prox5});
            sequencia.push_back(menor);

            if (menor == prox2) ++idx2;
            if (menor == prox3) ++idx3;
            if (menor == prox5) ++idx5;
        }
        return sequencia.back();
    }
};

274. Índice H de Impacto Acadêmico

O cálculo do índice H determina o maior número h tal que um peqsuisador possui pelo menos h artigos com h ou mais citações cada. Ordenando os registros em ordem decrescente e iterando sequencialmente, basta verificar até que ponto a contagem de trabalhos supera o valor atual de h.

class Solucao {
public:
    int calcularIndiceH(std::vector<int>& citacoes) {
        std::sort(citacoes.rbegin(), citacoes.rend());
        int h = 0;
        for (int count : citacoes) {
            if (count > h) {
                ++h;
            } else {
                break;
            }
        }
        return h;
    }
};

127. Escada de Palavras

A transformação mínima entre duas palavras, alterando um caractere por vez, é classicamente modelada como um grafo não ponderado. A busca em largura (BFS) garante o caminho mais curto ao explorar níveis consecutivos de transformação, utilizando um conjunto de visitados para evitar ciclos e otimizar a exploração do espaço de estados.

class Solucao {
public:
    int tamanhoTransformacao(std::string inicio, std::string fim, std::vector<std::string>& dicionario) {
        std::unordered_set<std::string> palavrasPermitidas(dicionario.begin(), dicionario.end());
        if (!palavrasPermitidas.count(fim)) return 0;

        std::queue<std::pair<std::string, int>> fila;
        fila.push({inicio, 1});
        std::unordered_set<std::string> visitados;
        visitados.insert(inicio);

        while (!fila.empty()) {
            auto [palavraAtual, nivel] = fila.front();
            fila.pop();

            for (size_t pos = 0; pos < palavraAtual.length(); ++pos) {
                char original = palavraAtual[pos];
                for (char c = 'a'; c <= 'z'; ++c) {
                    palavraAtual[pos] = c;
                    if (palavraAtual == fim) return nivel + 1;
                    if (palavrasPermitidas.count(palavraAtual) && !visitados.count(palavraAtual)) {
                        visitados.insert(palavraAtual);
                        fila.push({palavraAtual, nivel + 1});
                    }
                    palavraAtual[pos] = original;
                }
            }
        }
        return 0;
    }
};