LeetCode 665: Array non decrescente (C)

Question

Sto postando una soluzione per "Array non decrescente" di LeetCode. Se desideri rivedere, fallo. Grazie!

Problema

Dato un array numscon nnumeri interi, il tuo compito è controllare se potrebbe diventare non decrescente modificando al massimo 1 elemento.

Definiamo un array non decrescente se nums[i] <= nums[i + 1]vale per ogni i (a base 0) tale che ( 0 <= i <= n - 2).

Esempio 1:

• Input: nums = [4,2,3]
• Risultato: vero
• Spiegazione: È possibile modificare i primi 4 in 1 per ottenere un array non decrescente.

Esempio 2:

• Input: nums = [4,2,1]
• Risultato: falso
• Spiegazione: Non è possibile ottenere un array non decrescente modificando al massimo un elemento.

Vincoli:

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

Codice

// 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

Semplifica la logica

Perché questa soluzione sembra più complicata della versione C ++ che hai pubblicato ? Sembra che tu possa usare esattamente la stessa logica della versione C ++.

Non restituire constvalori

Dichiarare il valore restituito come essere constnon fa nulla a meno che tu non restituisca un puntatore.

Evita la gestione di casi speciali non necessari

Si esce anticipatamente se la dimensione dell'array è inferiore a 3, ma ciò non è necessario: il resto del codice gestisce già gli array di dimensione 0, 1 e 2 correttamente. Potresti salvare un ciclo se gli dai un piccolo array, ma paghi per questo controllo con uno o due cicli ogni volta che la funzione viene chiamata con nums_size > 2.

Semplifica il tuo main()

Fai molte cose inutili in main():

• Non è necessario avere una costante per l'array in primo piano, poiché è possibile utilizzare sizeofper ottenere la dimensione dell'array e dividerlo per la dimensione di un elemento per ottenere il numero di elementi.
• Non è necessario dichiarare un puntatore all'array, l'array stesso può essere utilizzato come puntatore.
• puts()è come fputs(), ma scrive sempre stdoute aggiunge una nuova riga per te.
• Non return 0è necessario in main().

Quindi puoi semplificarlo come segue:

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

Answer 2

Il codice muta un array . Non è buono.

Il codice fa troppo . Puoi return falsenon appena max_changesraggiungi 2 (non è necessario esaminare il resto).

Altre funzioni per favore . È molto difficile seguire il complicato processo decisionale. Tener conto di

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

Quindi la logica aziendale sarebbe:

    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;

Ovviamente le prime due condizioni possono essere combinate in violation >= size - 1. Ovviamente l'aumento di nums[violation]può essere virtuale, senza mutare l'array (se nums[violation - 1] > nums[violation + 1]possiamo farlo immediatamente return false;).