LeetCode 665: อาร์เรย์ที่ไม่ลดลง

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

รหัส

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

หลีกเลี่ยงการจัดการกรณีพิเศษที่ไม่จำเป็น

คุณออกก่อนเวลาหากขนาดของอาร์เรย์น้อยกว่า 3 แต่ไม่จำเป็น: ส่วนที่เหลือของโค้ดจัดการอาร์เรย์ขนาด 0, 1 และ 2 อย่างถูกต้องอยู่แล้ว คุณอาจบันทึกรอบถ้าคุณป้อนอาร์เรย์ขนาดเล็ก แต่คุณจ่ายสำหรับการตรวจสอบนี้ด้วยรอบหรือสองรอบสำหรับทุกครั้งที่มีการเรียกใช้ฟังก์ชันด้วยstd::size(nums)> 2

ใช้std::size_tสำหรับดัชนี

คุณทำแต่มีขนาดที่แตกต่างกัน (น่าจะ) และ signedness แตกต่างจากผลของ ซึ่งหมายความว่าคอมไพเลอร์ควรเตือนคุณเกี่ยวกับการเปรียบเทียบระหว่างจำนวนเต็มที่ลงชื่อและจำนวนเต็มไม่ได้ลงชื่อ ในขณะที่สิ่งต่างๆได้ผลที่นี่เนื่องจากคุณทราบว่าขนาดของอาร์เรย์อินพุตมีข้อ จำกัด คุณควรใช้ที่นี่เพื่อหลีกเลี่ยงคำเตือนของคอมไพเลอร์ ประสิทธิภาพไม่น่าจะแตกต่างกันเลยสักนิดเนื่องจากสามารถเก็บไว้ในทะเบียน CPU ได้ตลอดเวลาindexstd::int_fast32_tstd::size(nums)std::size_tindex

ไม่จำเป็นต้องใช้std::to_string()เมื่อใช้<<กับไฟล์std::ostream

เมื่อเขียนไปstd::ostream, แล้วจะทำให้เกิดการโต้แย้งการจัดรูปแบบจึงมีความจำเป็นที่จะต้องโทรไม่operator<< std::to_string()ในความเป็นจริงคุณสามารถบอกให้สตรีมจัดรูปแบบboolเป็นข้อความได้:

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