LeetCode 665: Mảng không giảm (C)

Question

Tôi đang đăng một giải pháp cho "Mảng không giảm" của LeetCode. Nếu bạn muốn xem lại, hãy làm. Cảm ơn bạn!

Vấn đề

Cho một mảng numsvới ncác số nguyên, nhiệm vụ của bạn là kiểm tra xem nó có thể không giảm hay không bằng cách sửa đổi nhiều nhất 1 phần tử.

Chúng tôi xác định một mảng là không giảm nếu nums[i] <= nums[i + 1]giữ cho mọi i (dựa trên 0) sao cho ( 0 <= i <= n - 2).

Ví dụ 1:

• Đầu vào: nums = [4,2,3]
• Đầu ra: true
• Giải thích: Bạn có thể sửa đổi 4 thành 1 đầu tiên để có được một mảng không giảm.

Ví dụ 2:

• Đầu vào: nums = [4,2,1]
• Đầu ra: false
• Giải thích: Bạn không thể nhận được một mảng không giảm bằng cách sửa đổi nhiều nhất một phần tử.

Ràng buộc:

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

Mã

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

Đơn giản hóa logic

Tại sao giải pháp này trông phức tạp hơn phiên bản C ++ mà bạn đã đăng ? Có vẻ như bạn có thể sử dụng logic chính xác như trong phiên bản C ++.

Không trả lại constgiá trị

Khai báo giá trị trả về constlà không có tác dụng gì trừ khi bạn trả về một con trỏ.

Tránh xử lý trường hợp đặc biệt không cần thiết

Bạn thoát sớm nếu kích thước của mảng nhỏ hơn 3, nhưng điều này là không cần thiết: phần còn lại của mã đã xử lý đúng các mảng có kích thước 0, 1 và 2. Bạn có thể lưu một chu kỳ nếu bạn cấp cho nó một mảng nhỏ, nhưng bạn phải trả cho việc kiểm tra này với một hoặc hai chu kỳ cho mỗi lần hàm được gọi với nums_size > 2.

Đơn giản hóa của bạn main()

Bạn làm nhiều việc không cần thiết trong main():

• Không cần phải có một hằng số cho mảng phía trước, vì bạn có thể sử dụng sizeofđể lấy kích thước của mảng và chia nó cho kích thước của một phần tử để có số phần tử.
• Không cần khai báo một con trỏ tới mảng, bản thân mảng có thể được sử dụng như một con trỏ.
• puts()giống như fputs(), nhưng luôn ghi vào stdoutvà thêm dòng mới cho bạn.
• Các return 0là không cần thiết trong main().

Vì vậy, bạn có thể đơn giản hóa nó như sau:

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

Answer 2

Mã thay đổi một mảng . Nó không tốt.

Mã làm quá nhiều . Bạn có thể return falsengay sau khi max_changesđạt đến 2 (không cần kiểm tra phần còn lại).

Nhiều chức năng hơn xin vui lòng . Rất khó để tuân theo việc ra quyết định phức tạp. Xem xét

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

Sau đó, logic kinh doanh sẽ là:

    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;

Tất nhiên hai điều kiện đầu tiên có thể được kết hợp thành violation >= size - 1. Tất nhiên tăng của nums[violation]có thể là ảo, mà không làm thay đổi mảng (nếu nums[violation - 1] > nums[violation + 1]chúng tôi có thể ngay lập tức return false;).