LeetCode 665: Matriz no decreciente (C)

Question

Estoy publicando una solución para el "Array no decreciente" de LeetCode. Si desea revisarlo, hágalo. ¡Gracias!

Problema

Dada una matriz numscon nnúmeros enteros, su tarea es verificar si podría volverse no decreciente modificando como máximo 1 elemento.

Definimos que una matriz no es decreciente si se nums[i] <= nums[i + 1]cumple para cada i (basado en 0) tal que ( 0 <= i <= n - 2).

Ejemplo 1:

• Entrada: nums = [4,2,3]
• Salida: verdadero
• Explicación: podría modificar los primeros 4 a 1 para obtener una matriz no decreciente.

Ejemplo 2:

• Entrada: nums = [4,2,1]
• Salida: falso
• Explicación: No se puede obtener una matriz no decreciente modificando como máximo un elemento.

Limitaciones:

• 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

Simplifica la lógica

¿Por qué esta solución parece más complicada que la versión de C ++ que publicó ? Parece que puede usar exactamente la misma lógica que en la versión C ++.

No devuelva constvalores

Declarar el valor de retorno constno significa nada a menos que devuelva un puntero.

Evite el manejo innecesario de casos especiales

Salga temprano si el tamaño de la matriz es menor que 3, pero esto es innecesario: el resto del código ya maneja matrices de tamaño 0, 1 y 2 correctamente. Puede guardar un ciclo si lo alimenta con una matriz pequeña, pero paga por este cheque con uno o dos ciclos por cada vez que se llama a la función con nums_size > 2.

Simplifica tu main()

Haces muchas cosas innecesarias en main():

• No es necesario tener una constante para la matriz al principio, ya que puede usarla sizeofpara obtener el tamaño de la matriz y dividirla por el tamaño de un elemento para obtener la cantidad de elementos.
• No es necesario declarar un puntero a la matriz, la matriz en sí se puede utilizar como puntero.
• puts()es como fputs(), pero siempre escribe stdouty agrega una nueva línea para usted.
• No return 0es necesario en main().

Entonces puedes simplificarlo de la siguiente manera:

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

Answer 2

El código muta una matriz . No es bueno.

El código hace demasiado . Puede return falsetan pronto como max_changesllegue a 2 (no es necesario examinar el resto).

Más funciones por favor . Es muy difícil seguir la complicada toma de decisiones. 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;
}

Entonces la lógica empresarial sería:

    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;

Por supuesto, las dos primeras condiciones se pueden combinar en violation >= size - 1. Por supuesto, el aumento de nums[violation]puede ser virtual, sin mutar la matriz (si nums[violation - 1] > nums[violation + 1]es posible de inmediato return false;).