LeetCode 665: неубывающий массив (C)

Question

Я отправляю решение для LeetCode «Неубывающий массив». Если вы хотите просмотреть, сделайте это. Спасибо!

Проблема

Учитывая массив numsс nцелыми числами, ваша задача - проверить, может ли он стать неубывающим, изменив не более 1 элемента.

Мы определяем, что массив не убывает, если nums[i] <= nums[i + 1]выполняется для каждого i (на основе 0), такого что ( 0 <= i <= n - 2).

Пример 1:

• Ввод: nums = [4,2,3]
• Выход: правда
• Объяснение: Вы можете изменить первые 4 на 1, чтобы получить неубывающий массив.

Пример 2:

• Ввод: nums = [4,2,1]
• Выход: ложь
• Объяснение: Вы не можете получить неубывающий массив, изменив не более одного элемента.

Ограничения:

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

Код

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

Упростите логику

Почему это решение выглядит сложнее, чем опубликованная вами версия C ++ ? Похоже, вы можете использовать ту же логику, что и в версии на C ++.

Не возвращать constзначения

Объявление возвращаемого значения constничего не делает, если вы не вернете указатель.

Избегайте ненужной обработки особых случаев

Вы выходите раньше, если размер массива меньше 3, но в этом нет необходимости: остальная часть кода уже правильно обрабатывает массивы размера 0, 1 и 2. Вы можете сохранить цикл, если скармливаете ему небольшой массив, но вы платите за эту проверку одним или двумя циклами каждый раз, когда функция вызывается с помощью nums_size > 2.

Упростите свой main()

Вы делаете много ненужного в main():

• Нет необходимости иметь константу для массива впереди, поскольку вы можете использовать ее, sizeofчтобы получить размер массива и разделить его на размер одного элемента, чтобы получить количество элементов.
• Указатель на массив объявлять не нужно, сам массив можно использовать как указатель.
• puts()похоже fputs(), но всегда пишет stdoutи добавляет за вас новую строку.
• return 0Не является необходимым main().

Таким образом, вы можете упростить его следующим образом:

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

Answer 2

Код изменяет массив . Это не хорошо.

Код делает слишком много . Можете, return falseкак только дойдете max_changesдо 2 (остальное рассматривать не нужно).

Больше функций, пожалуйста . Очень сложно уследить за принятием сложных решений. Рассматривать

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

Тогда бизнес-логика будет такой:

    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;

Конечно, первые два условия можно объединить violation >= size - 1. Конечно, увеличение nums[violation]может быть виртуальным, без изменения массива (если nums[violation - 1] > nums[violation + 1]можно сразу return false;).