LeetCode 665: Array Tidak Menurun

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

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

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 std::size(nums)> 2.

Gunakan std::size_tuntuk indeks

Anda membuat indexsebuah std::int_fast32_t, tapi ini memiliki ukuran yang berbeda (kemungkinan) dan signedness berbeda dari hasil std::size(nums). Ini berarti kompilator seharusnya memperingatkan Anda tentang perbandingan antara bilangan bulat bertanda dan tak bertanda. Sementara semuanya berhasil di sini, karena Anda tahu ukuran larik input dibatasi, sebaiknya gunakan di std::size_tsini untuk menghindari peringatan compiler. Performa sepertinya tidak akan berbeda sedikit pun, karena indexdapat disimpan dalam register CPU setiap saat.

Tidak perlu menggunakan std::to_string()saat menggunakan <<distd::ostream

Saat menulis ke std::ostream, operator<<sudah akan menyebabkan argumen diformat, jadi tidak perlu memanggil std::to_string(). Nyatanya, Anda dapat memberi tahu aliran untuk memformat boolsebagai teks:

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