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 0main()

ดังนั้นคุณสามารถลดความซับซ้อนได้ดังนี้:

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;)