LeetCode 665: nie malejąca tablica

Question

Zamieszczam rozwiązanie dla „Nie-malejącej tablicy” LeetCode. Jeśli chcesz przejrzeć, zrób to. Dziękuję Ci!

Problem

Biorąc pod uwagę tablicę numsz nliczbami całkowitymi, Twoim zadaniem jest sprawdzenie, czy nie może stać się ona malejąca, modyfikując maksymalnie 1 element.

Definiujemy tablicę, która nie maleje, jeśli nums[i] <= nums[i + 1]jest zachowana dla każdego i (od 0), takiego jak ( 0 <= i <= n - 2).

Przykład 1:

• Dane wejściowe: nums = [4,2,3]
• Wyjście: prawda
• Objaśnienie: Można zmodyfikować pierwsze 4 do 1, aby uzyskać tablicę nie zmniejszającą się.

Przykład 2:

• Dane wejściowe: nums = [4,2,1]
• Wynik: fałsz
• Objaśnienie: Nie można uzyskać tablicy, która nie maleje, modyfikując najwyżej jeden element.

Ograniczenia:

• 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

Unikaj niepotrzebnej obsługi przypadków specjalnych

Kończysz wcześniej, jeśli rozmiar tablicy jest mniejszy niż 3, ale jest to niepotrzebne: reszta kodu już poprawnie obsługuje tablice o rozmiarze 0, 1 i 2. Możesz zapisać cykl, jeśli podasz mu małą tablicę, ale płacisz za to sprawdzenie jednym lub dwoma cyklami za każdym razem, gdy funkcja jest wywoływana z std::size(nums)> 2.

Używaj std::size_tdo indeksów

Zrobiłeś , ale ma inny rozmiar (prawdopodobne) i inny signedness niż wynik . Oznacza to, że kompilator powinien był ostrzegać przed porównaniem liczb całkowitych ze znakiem i bez znaku. Chociaż wszystko działa tutaj, ponieważ wiesz, że rozmiar tablicy wejściowej jest ograniczony, najlepiej jest użyć tego tutaj, aby uniknąć ostrzeżenia kompilatora. Wydajność prawdopodobnie nie będzie się różnić o jeden bit, ponieważ może być przechowywana przez cały czas w rejestrze procesora.indexstd::int_fast32_tstd::size(nums)std::size_tindex

Nie ma potrzeby używania w std::to_string()przypadku korzystania <<zstd::ostream

Podczas pisania do a std::ostream, operator<<spowoduje to już sformatowanie argumentu, więc nie ma potrzeby wywoływania std::to_string(). W rzeczywistości możesz nakazać strumieniowi sformatowanie booljako tekst:

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