LeetCode 665: Mảng không giảm

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ã

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

struct Solution {
    using ValueType = std::int_fast32_t;
    static const bool checkPossibility(
        std::vector<int>& nums
    ) {

        if (std::size(nums) < 3) {
            return true;
        }

        ValueType max_changes = 0;

        for (ValueType index = 1; max_changes < 2 && index < std::size(nums); ++index) {
            if (nums[index - 1] > nums[index]) {
                ++max_changes;

                if (index - 2 < 0 || nums[index - 2] <= nums[index]) {
                    nums[index - 1] = nums[index];

                } else {
                    nums[index] = nums[index - 1];
                }
            }
        }

        return max_changes < 2;
    }
};


int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::to_string(Solution().checkPossibility(nums) == false) << "\n";
    return 0;
}

Answer 1

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 cung cấp cho nó một mảng nhỏ, nhưng bạn trả tiền cho việc kiểm tra này bằng một hoặc hai chu kỳ cho mỗi lần hàm được gọi với std::size(nums)> 2.

Sử dụng std::size_tcho các chỉ số

Bạn đã thực hiện indexmột std::int_fast32_t, nhưng điều này có kích thước khác (có khả năng) và độ ký khác với kết quả của std::size(nums). Điều này có nghĩa là trình biên dịch nên cảnh báo bạn về sự so sánh giữa số nguyên có dấu và không có dấu. Trong khi mọi thứ diễn ra ở đây, vì bạn biết kích thước của mảng đầu vào bị hạn chế, tốt nhất nên sử dụng std::size_tở đây để tránh cảnh báo trình biên dịch. Hiệu suất có thể sẽ không khác một chút nào, vì indexcó thể được lưu giữ trong thanh ghi CPU mọi lúc.

Không cần sử dụng std::to_string()khi sử dụng <<trên mộtstd::ostream

Khi viết tới a std::ostream, operator<<sẽ khiến đối số đã được định dạng, vì vậy không cần gọi std::to_string(). Trên thực tế, bạn có thể yêu cầu luồng định dạng dưới dạng boolvăn bản:

int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::boolalpha << Solution().checkPossibility(nums) << "\n";
}