LeetCode 665: Array non decrescente

Question

Sto postando una soluzione per "Array non decrescente" di LeetCode. Se desideri rivedere, fallo. Grazie!

Problema

Dato un array numscon nnumeri interi, il tuo compito è controllare se potrebbe diventare non decrescente modificando al massimo 1 elemento.

Definiamo un array non decrescente se nums[i] <= nums[i + 1]vale per ogni i (a base 0) tale che ( 0 <= i <= n - 2).

Esempio 1:

• Input: nums = [4,2,3]
• Risultato: vero
• Spiegazione: È possibile modificare i primi 4 in 1 per ottenere un array non decrescente.

Esempio 2:

• Input: nums = [4,2,1]
• Risultato: falso
• Spiegazione: Non è possibile ottenere un array non decrescente modificando al massimo un elemento.

Vincoli:

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

Codice

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

Evita la gestione di casi speciali non necessari

Si esce anticipatamente se la dimensione dell'array è inferiore a 3, ma ciò non è necessario: il resto del codice gestisce già gli array di dimensione 0, 1 e 2 correttamente. Potresti salvare un ciclo se gli dai un piccolo array, ma paghi per questo controllo con uno o due cicli ogni volta che la funzione viene chiamata con std::size(nums)> 2.

Utilizzare std::size_tper gli indici

Hai fatto indexun std::int_fast32_t, ma questo ha una dimensione diversa (probabilmente) e una firma diversa rispetto al risultato di std::size(nums). Ciò significa che il compilatore avrebbe dovuto avvisarti di un confronto tra interi con segno e senza segno. Anche se qui le cose funzionano, poiché sai che la dimensione dell'array di input è vincolata, è meglio usarla std::size_tqui per evitare l'avviso del compilatore. È probabile che le prestazioni non differiscano di un bit, poiché indexpossono essere mantenute in un registro della CPU in ogni momento.

Non è necessario utilizzare std::to_string()quando si utilizza <<su un filestd::ostream

Quando si scrive in a std::ostream, operator<<l'argomento verrà già formattato, quindi non è necessario chiamare std::to_string(). In effetti, puoi dire allo stream di formattare un boolcome testo:

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