LeetCode 665: Nicht abnehmendes Array (C)

Question

Ich veröffentliche eine Lösung für LeetCodes "Nicht abnehmendes Array". Wenn Sie eine Bewertung abgeben möchten, tun Sie dies bitte. Dankeschön!

Problem

Bei einem Array numsmit nganzen Zahlen müssen Sie überprüfen, ob es nicht abnehmen kann, indem Sie höchstens 1 Element ändern.

Wir definieren, dass ein Array nicht abnimmt, wenn es nums[i] <= nums[i + 1]für jedes i (0-basiert) gilt, so dass ( 0 <= i <= n - 2).

Beispiel 1:

• Eingabe: nums = [4,2,3]
• Ausgabe: wahr
• Erläuterung: Sie können die ersten 4 zu 1 ändern, um ein nicht abnehmendes Array zu erhalten.

Beispiel 2:

• Eingabe: nums = [4,2,1]
• Ausgabe: false
• Erläuterung: Sie können ein nicht abnehmendes Array nicht erhalten, indem Sie höchstens ein Element ändern.

Einschränkungen:

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

Code

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

Vereinfachen Sie die Logik

Warum sieht diese Lösung komplizierter aus als die von Ihnen veröffentlichte C ++ - Version ? Anscheinend können Sie genau die gleiche Logik wie in der C ++ - Version verwenden.

Geben Sie keine constWerte zurück

Wenn Sie den Rückgabewert als "deklarieren", constwird nichts getan, es sei denn, Sie geben einen Zeiger zurück.

Vermeiden Sie unnötige Sonderfälle

Sie beenden das Array vorzeitig, wenn die Größe des Arrays weniger als 3 beträgt. Dies ist jedoch nicht erforderlich: Der Rest des Codes behandelt Arrays der Größen 0, 1 und 2 bereits korrekt. Sie können einen Zyklus speichern, wenn Sie ihm ein kleines Array zuführen, aber Sie bezahlen diesen Scheck mit ein oder zwei Zyklen für jedes Mal, wenn die Funktion aufgerufen wird nums_size > 2.

Vereinfachen Sie Ihre main()

Sie machen viele unnötige Dinge in main():

• Es ist nicht erforderlich, eine Konstante für das Array im Voraus zu haben, da Sie sizeofdie Größe des Arrays ermitteln und durch die Größe eines Elements dividieren können, um die Anzahl der Elemente zu ermitteln.
• Es ist nicht erforderlich, einen Zeiger auf das Array zu deklarieren. Das Array selbst kann als Zeiger verwendet werden.
• puts()ist wie fputs(), schreibt aber immer an stdoutund fügt eine neue Zeile für Sie hinzu.
• Das return 0ist in nicht notwendig main().

Sie können es also wie folgt vereinfachen:

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

Answer 2

Der Code mutiert ein Array . Es ist nicht gut.

Der Code macht zu viel . Sie können return false, sobald max_changes2 erreicht ist (keine Notwendigkeit, den Rest zu untersuchen).

Weitere Funktionen bitte . Es ist sehr schwer, die komplizierten Entscheidungen zu verfolgen. Erwägen

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

Dann wäre die Geschäftslogik:

    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;

Natürlich können die ersten beiden Bedingungen kombiniert werden violation >= size - 1. Natürlich nums[violation]kann das Erhöhen von virtuell sein, ohne das Array zu mutieren (wenn nums[violation - 1] > nums[violation + 1]wir es sofort dürfen return false;).