LeetCode 665: Matriz não decrescente (C)

Question

Estou postando uma solução para a "Matriz não decrescente" do LeetCode. Se você gostaria de revisar, por favor, faça. Obrigado!

Problema

Dado um array numscom ninteiros, sua tarefa é verificar se ele pode se tornar não decrescente modificando no máximo 1 elemento.

Definimos que um array é não decrescente se for nums[i] <= nums[i + 1]válido para cada i (baseado em 0) tal que ( 0 <= i <= n - 2).

Exemplo 1:

• Entrada: nums = [4,2,3]
• Resultado: verdadeiro
• Explicação: Você pode modificar os primeiros 4 para 1 para obter uma matriz não decrescente.

Exemplo 2:

• Entrada: nums = [4,2,1]
• Resultado: falso
• Explicação: Você não pode obter uma matriz não decrescente modificando no máximo um elemento.

Restrições:

• 1 <= n <= 10 ^ 4
• -10 ^ 5 <= nums[i] <= 10 ^ 5

Código

// Since the relevant headers are already included on the LeetCode platform,
// the headers can be removed;
#include <stdio.h>
#include <stdbool.h>

static const bool checkPossibility(
    int *nums,
    const int nums_size
) {

    if (nums_size < 3) {
        return true;
    }

    int max_changes = 0;

    for (int index = 1; index < nums_size - 1; ++index) {
        if (!(nums[index] >= nums[index - 1] && nums[index + 1] >= nums[index])) {
            if (nums[index + 1] >= nums[index - 1]) {
                ++max_changes;
                nums[index] = nums[index - 1];

            } else {
                if (nums[index] < nums[index - 1] && nums[index + 1] < nums[index]) {
                    return false;

                } else if (nums[index] <= nums[index + 1]) {
                    nums[index - 1] = nums[index];

                    if (!(index - 1) || nums[index - 2] <= nums[index - 1]) {
                        ++max_changes;

                    } else {
                        return false;
                    }

                } else {
                    nums[index + 1] = nums[index];
                    ++max_changes;
                }
            }
        }

    }


    return max_changes < 2;
}

int main() {

    static const int nums_size = 3;
    int nums_array[nums_size] = {4, 2, 1};
    int (*nums)[nums_size] = &nums_array;

    fputs(checkPossibility(*nums, nums_size) ? "true" : "false", stdout);

    return 0;
}

Answer 1

Simplifique a lógica

Por que esta solução parece mais complicada do que a versão C ++ que você postou ? Parece que você pode usar exatamente a mesma lógica da versão C ++.

Não retorna constvalores

Declarar o valor de retorno como constnão está fazendo nada a menos que você retorne um ponteiro.

Evite o manuseio desnecessário de casos especiais

Você sai mais cedo se o tamanho do array for menor que 3, mas isso é desnecessário: o resto do código já lida com arrays de tamanho 0, 1 e 2 corretamente. Você pode salvar um ciclo se alimentá-lo com um pequeno array, mas paga por esse cheque com um ou dois ciclos para cada vez que a função é chamada com nums_size > 2.

Simplifique o seu main()

Você faz muitas coisas desnecessárias em main():

• Não há necessidade de ter uma constante para o array na frente, pois você pode usar sizeofpara obter o tamanho do array e dividi-lo pelo tamanho de um elemento para obter o número de elementos.
• Não há necessidade de declarar um ponteiro para a matriz, a própria matriz pode ser usada como um ponteiro.
• puts()é semelhante fputs(), mas sempre escreve stdoute adiciona uma nova linha para você.
• O return 0não é necessário em main().

Portanto, você pode simplificar da seguinte forma:

int main() {
    int array[] = {4, 2, 1};
    puts(checkPossibility(array, sizeof array / sizeof *array) ? "true" : "false");
}

Answer 2

O código altera uma matriz . Isso não é bom.

O código faz muito . Você pode return falseassim que max_changeschegar a 2 (não há necessidade de examinar o resto).

Mais funções, por favor . É muito difícil acompanhar a complicada tomada de decisão. Considerar

int find_first_violation(int * nums, int size)
{
    int i = 0;
    for (; i < size; i++) {
        if (nums[i] < nums[i-1]) {
            break;
        }
    }
    return i;
}

Então, a lógica de negócios seria:

    int violation = find_first_violation(nums, size);

    if (violation == size) {
        // array is already non-decreasing
        return true;
    }
    if (violation == size - 1) {
        // easily fixable: increase nums[size - 1]
        return true;
    }

    // Now fix the violation
    // violation == 1 is fixable by decreasing nums[0]. No action needed.
    // Otherwise, we only care about the case where nums[violation] is too
    // small - less than two preceding numbers. It is only fixable by
    // increasing it, effectively setting it equal to nums[violation - 1].

    if ((violation > 1) && (nums[violation] < nums[violation - 2])) {
        nums[violation] = nums[violation - 1];
    }

    // Finally, the core argument to have more functions: there
    // must be no more violations.

    return find_first_violation(nums + violation, size - violation) == size - violation;

Claro que as duas primeiras condições podem ser combinadas em violation >= size - 1. É claro que o aumento de nums[violation]pode ser virtual, sem alterar o array (se nums[violation - 1] > nums[violation + 1]pudermos imediatamente return false;).