LeetCode 665: nie malejąca tablica (C)

Question

Zamieszczam rozwiązanie dla „Nie-malejącej tablicy” LeetCode. Jeśli chcesz przejrzeć, zrób to. Dziękuję Ci!

Problem

Biorąc pod uwagę tablicę numsz nliczbami całkowitymi, Twoim zadaniem jest sprawdzenie, czy nie może stać się ona malejąca, modyfikując maksymalnie 1 element.

Definiujemy tablicę, która nie maleje, jeśli nums[i] <= nums[i + 1]jest zachowana dla każdego i (od 0), takiego jak ( 0 <= i <= n - 2).

Przykład 1:

• Dane wejściowe: nums = [4,2,3]
• Wyjście: prawda
• Objaśnienie: Można zmodyfikować pierwsze 4 do 1, aby uzyskać tablicę nie zmniejszającą się.

Przykład 2:

• Dane wejściowe: nums = [4,2,1]
• Wynik: fałsz
• Objaśnienie: Nie można uzyskać tablicy, która nie maleje, modyfikując najwyżej jeden element.

Ograniczenia:

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

Kod

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

Uprość logikę

Dlaczego to rozwiązanie wygląda na bardziej skomplikowane niż opublikowana przez Ciebie wersja C ++ ? Wygląda na to, że możesz użyć dokładnie tej samej logiki, co w wersji C ++.

Nie zwracaj constwartości

Zadeklarowanie zwracanej wartości constnie oznacza nic, chyba że zwrócisz wskaźnik.

Unikaj niepotrzebnej obsługi przypadków specjalnych

Kończysz wcześniej, jeśli rozmiar tablicy jest mniejszy niż 3, ale jest to niepotrzebne: reszta kodu już poprawnie obsługuje tablice o rozmiarze 0, 1 i 2. Możesz zapisać cykl, jeśli podasz mu małą tablicę, ale płacisz za to sprawdzenie jednym lub dwoma cyklami za każdym razem, gdy funkcja jest wywoływana za pomocą nums_size > 2.

Uprość swój main()

Robisz wiele niepotrzebnych rzeczy w main():

• Nie ma potrzeby posiadania stałej dla tablicy z góry, ponieważ możesz użyć jej sizeofdo uzyskania rozmiaru tablicy i podzielić ją przez rozmiar jednego elementu, aby uzyskać liczbę elementów.
• Nie ma potrzeby deklarowania wskaźnika do tablicy, sama tablica może służyć jako wskaźnik.
• puts()jest jak fputs(), ale zawsze pisze do stdouti dodaje nowy wiersz.
• Nie return 0jest konieczne w main().

Możesz więc uprościć to w następujący sposób:

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

Answer 2

Kod modyfikuje tablicę . To nie jest dobre.

Kod robi za dużo . Możesz, return falsegdy tylko max_changesosiągnie 2 (nie ma potrzeby sprawdzania reszty).

Więcej funkcji proszę . Bardzo trudno jest śledzić skomplikowane podejmowanie decyzji. Rozważać

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

Wtedy logika biznesowa wyglądałaby tak:

    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;

Oczywiście dwa pierwsze warunki można połączyć w violation >= size - 1. Oczywiście zwiększenie wartości nums[violation]może być wirtualne, bez mutowania tablicy (jeśli nums[violation - 1] > nums[violation + 1]możemy od razu return false;).