LeetCode 665: matrice non décroissante (C)

Question

Je poste une solution pour le "tableau non décroissant" de LeetCode. Si vous souhaitez examiner, veuillez le faire. Merci!

Problème

Étant donné un tableau numsavec des nentiers, votre tâche est de vérifier s'il pourrait devenir non décroissant en modifiant au plus 1 élément.

Nous définissons qu'un tableau est non décroissant s'il nums[i] <= nums[i + 1]est valable pour tout i (basé sur 0) tel que ( 0 <= i <= n - 2).

Exemple 1:

• Entrée: nums = [4,2,3]
• Sortie: vrai
• Explication: Vous pouvez modifier les 4 premiers en 1 pour obtenir un tableau non décroissant.

Exemple 2:

• Entrée: nums = [4,2,1]
• Sortie: faux
• Explication: Vous ne pouvez pas obtenir un tableau non décroissant en modifiant au plus un élément.

Contraintes:

• 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

Simplifiez la logique

Pourquoi cette solution semble-t-elle plus compliquée que la version C ++ que vous avez publiée ? Il semble que vous puissiez utiliser exactement la même logique que dans la version C ++.

Ne renvoie pas de constvaleurs

Déclarer la valeur de retour comme constétant ne fait rien, sauf si vous renvoyez un pointeur.

Évitez toute manipulation inutile de cas spéciaux

Vous quittez tôt si la taille du tableau est inférieure à 3, mais cela n'est pas nécessaire: le reste du code gère déjà correctement les tableaux de taille 0, 1 et 2. Vous pouvez enregistrer un cycle si vous lui alimentez un petit tableau, mais vous payez ce chèque avec un cycle ou deux à chaque fois que la fonction est appelée nums_size > 2.

Simplifiez votre main()

Vous faites beaucoup de choses inutiles dans main():

• Il n'est pas nécessaire d'avoir une constante pour le tableau à l'avant, car vous pouvez l'utiliser sizeofpour obtenir la taille du tableau et le diviser par la taille d'un élément pour obtenir le nombre d'éléments.
• Il n'est pas nécessaire de déclarer un pointeur vers le tableau, le tableau lui-même peut être utilisé comme pointeur.
• puts()est comme fputs(), mais écrit toujours stdoutet ajoute une nouvelle ligne pour vous.
• Le return 0n'est pas nécessaire dans main().

Vous pouvez donc le simplifier comme suit:

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

Answer 2

Le code mute un tableau . Ce n'est pas bon.

Le code en fait trop . Vous pouvez return falsedès que max_changesatteint 2 (pas besoin d'examiner le reste).

Plus de fonctions s'il vous plaît . Il est très difficile de suivre la prise de décision compliquée. Considérer

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

Ensuite, la logique métier serait:

    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;

Bien sûr, les deux premières conditions peuvent être combinées en violation >= size - 1. Bien sûr, l'augmentation de nums[violation]peut être virtuelle, sans muter le tableau (si nums[violation - 1] > nums[violation + 1]nous pouvons immédiatement return false;).