LeetCode 665: Azalmayan Dizi (C)

Question

LeetCode'un "Azalmayan Dizisi" için bir çözüm yayınlıyorum. İncelemek isterseniz, lütfen yapın. Teşekkür ederim!

Sorun

Bir dizi Verilen numsile ntamsayılar, görev en 1 eleman olarak değiştirerek olmayan azalan haline gelebilir olmadığını kontrol etmektir.

nums[i] <= nums[i + 1]Her i (0 tabanlı) için ( 0 <= i <= n - 2) gibi tutarsa, azalmayan bir dizi tanımlarız .

Örnek 1:

• Giriş: nums = [4,2,3]
• Çıktı: doğru
• Açıklama: Azalan bir dizi elde etmek için ilk 4'ü 1'e değiştirebilirsiniz.

Örnek 2:

• Giriş: nums = [4,2,1]
• Çıktı: yanlış
• Açıklama: En fazla bir elemanı değiştirerek azalan bir dizi elde edemezsiniz.

Kısıtlamalar:

• 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

Mantığı basitleştirin

Bu çözüm neden yayınladığınız C ++ sürümünden daha karmaşık görünüyor ? Görünüşe göre C ++ sürümüyle tamamen aynı mantığı kullanabiliyorsunuz.

İade etmeyin constdeğerleri

Dönüş değerini bildirmek, constbir işaretçi döndürmediğiniz sürece hiçbir şey yapmaz.

Gereksiz özel durum işlemlerinden kaçının

Dizinin boyutu 3'ten küçükse erken çıkarsınız, ancak bu gereksizdir: kodun geri kalanı zaten boyut 0, 1 ve 2 dizilerini doğru şekilde işler. Küçük bir dizi beslerseniz bir döngüden tasarruf edebilirsiniz, ancak bu çeki, işlev ile her çağrıldığında bir veya iki döngü ile ödersiniz nums_size > 2.

Basitleştirin main()

Şunlarda birçok gereksiz şey yaparsınız main():

• Dizinin sizeofboyutunu elde etmek için kullanabileceğiniz ve öğe sayısını elde etmek için onu bir öğenin boyutuna bölebileceğinizden , dizi için önden bir sabite sahip olmanız gerekmez .
• Diziye bir gösterici bildirmeye gerek yoktur, dizinin kendisi bir işaretçi olarak kullanılabilir.
• puts()gibidir fputs(), ancak her zaman için yazar stdoutve sizin için yeni bir satır ekler.
• return 0Gerekli değildir main().

Yani aşağıdaki gibi basitleştirebilirsiniz:

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

Answer 2

Kod bir diziyi değiştirir . İyi değil.

Kod çok fazla . Şunları return falseen kısa sürede max_changesulaşır 2 (kalanını incelemeye gerek).

Daha fazla fonksiyon lütfen . Karmaşık karar vermeyi takip etmek çok zordur. Düşünmek

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

O zaman iş mantığı şöyle olur:

    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;

Tabii ki ilk iki koşul birleştirilebilir violation >= size - 1. Elbette nums[violation], diziyi değiştirmeden artması sanal nums[violation - 1] > nums[violation + 1]olabilir (eğer hemen yapabilirsek return false;).