LeetCode 665: Azalmayan Dizi

Question

LeetCode'un "Azalmayan Dizisi" için bir çözüm yayınlıyorum. İncelemek isterseniz, lütfen yapın. Teşekkür ederim!

Sorun

Bir dizi Verilen numsile ntamsayılar, görev en 1 eleman olarak değiştirerek olmayan azalan haline gelebilir olmadığını kontrol etmektir.

nums[i] <= nums[i + 1]Her i (0 tabanlı) için ( 0 <= i <= n - 2) gibi tutarsa, azalmayan bir dizi tanımlarız .

Örnek 1:

• Giriş: nums = [4,2,3]
• Çıktı: doğru
• Açıklama: Azalan bir dizi elde etmek için ilk 4'ü 1'e değiştirebilirsiniz.

Örnek 2:

• Giriş: nums = [4,2,1]
• Çıktı: yanlış
• Açıklama: En fazla bir elemanı değiştirerek azalan bir dizi elde edemezsiniz.

Kısıtlamalar:

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

Kod

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

Gereksiz özel durum işlemlerinden kaçının

Dizinin boyutu 3'ten küçükse erken çıkarsınız, ancak bu gereksizdir: kodun geri kalanı zaten boyut 0, 1 ve 2 dizilerini doğru şekilde işler. Küçük bir dizi beslerseniz bir döngüden tasarruf edebilirsiniz, ancak bu çeki, işlev std::size(nums)> 2 ile her çağrıldığında bir veya iki döngü ile ödersiniz .

std::size_tEndeksler için kullanın

Sen yapılmış indexbir std::int_fast32_t, ama bu farklı bir boyut (büyük olasılıkla) ve sonucu daha farklı signedness sahiptir std::size(nums). Bu, derleyicinin sizi işaretli ve işaretsiz tamsayılar arasında bir karşılaştırma konusunda uyarmış olması gerektiği anlamına gelir. Burada işler yolunda giderken, girdi dizisinin boyutunun kısıtlı olduğunu bildiğiniz std::size_tiçin, derleyici uyarısından kaçınmak için burada kullanmak en iyisidir . indexHer zaman bir CPU kaydında tutulabileceğinden , performans muhtemelen bir bit farklı olmayacaktır.

Kullanmaya gerek yoktur std::to_string()kullanırken <<a üzerindestd::ostream

Bir yazarken std::ostream, operator<<zaten bu yüzden çağrısına gerek yoktur, argüman biçimlendirilmiş neden olacaktır std::to_string(). Aslında, akışa a'yı boolmetin olarak biçimlendirmesini söyleyebilirsiniz :

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