LeetCode 665: Array Tidak Menurun (C)

Question

Saya memposting solusi untuk LeetCode's "Non-menurun Array". Jika Anda ingin mengulas, harap lakukan. Terima kasih!

Masalah

Diberikan sebuah array numsdengan ninteger, tugas Anda adalah untuk memeriksa apakah itu bisa menjadi non-menurun dengan memodifikasi paling banyak 1 elemen.

Kami mendefinisikan sebuah array tidak menurun jika nums[i] <= nums[i + 1]ditahan untuk setiap i (berbasis 0) seperti itu ( 0 <= i <= n - 2).

Contoh 1:

• Masukan: nums = [4,2,3]
• Hasil: benar
• Penjelasan: Anda dapat mengubah 4 menjadi 1 pertama untuk mendapatkan larik yang tidak menurun.

Contoh 2:

• Masukan: nums = [4,2,1]
• Output: salah
• Penjelasan: Anda tidak bisa mendapatkan larik non-penurunan dengan memodifikasi paling banyak satu elemen.

Batasan:

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

Kode

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

Sederhanakan logikanya

Mengapa solusi ini terlihat lebih rumit daripada versi C ++ yang Anda posting ? Sepertinya Anda dapat menggunakan logika yang sama persis seperti di versi C ++.

Jangan mengembalikan constnilai

Mendeklarasikan nilai kembali menjadi consttidak melakukan apa-apa kecuali Anda mengembalikan pointer.

Hindari penanganan kasus khusus yang tidak perlu

Anda keluar lebih awal jika ukuran array kurang dari 3, tetapi ini tidak diperlukan: kode lainnya sudah menangani array dengan ukuran 0, 1 dan 2 dengan benar. Anda mungkin menyimpan satu siklus jika Anda memberinya larik kecil, tetapi Anda membayar cek ini dengan satu atau dua siklus untuk setiap kali fungsi dipanggil dengan nums_size > 2.

Sederhanakan Anda main()

Anda melakukan banyak hal yang tidak perlu di main():

• Tidak perlu memiliki konstanta untuk larik di depan, karena Anda bisa menggunakan sizeofuntuk mendapatkan ukuran larik, dan membaginya dengan ukuran satu elemen untuk mendapatkan jumlah elemen.
• Tidak perlu mendeklarasikan pointer ke array, array itu sendiri dapat digunakan sebagai pointer.
• puts()seperti fputs(), tetapi selalu menulis ke stdout, dan menambahkan baris baru untuk Anda.
• Tidak return 0perlu di main().

Jadi Anda bisa menyederhanakannya sebagai berikut:

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

Answer 2

Kode tersebut mengubah array . Itu tidak baik.

Kode terlalu banyak . Anda dapat return falsesegera max_changesmencapai 2 (tidak perlu memeriksa sisanya).

Lebih banyak fungsi . Sangat sulit untuk mengikuti pengambilan keputusan yang rumit. Mempertimbangkan

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

Maka logika bisnisnya adalah:

    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;

Tentu saja dua kondisi pertama bisa digabungkan menjadi violation >= size - 1. Tentu saja peningkatan nums[violation]dapat dilakukan secara virtual, tanpa mengubah array (jika nums[violation - 1] > nums[violation + 1]kami dapat segera return false;).