LeetCode 665: matrice non décroissante

Question

Je poste une solution pour le "tableau non décroissant" de LeetCode. Si vous souhaitez examiner, veuillez le faire. Merci!

Problème

Étant donné un tableau numsavec des nentiers, votre tâche est de vérifier s'il pourrait devenir non décroissant en modifiant au plus 1 élément.

Nous définissons qu'un tableau est non décroissant s'il nums[i] <= nums[i + 1]est valable pour tout i (basé sur 0) tel que ( 0 <= i <= n - 2).

Exemple 1:

• Entrée: nums = [4,2,3]
• Sortie: vrai
• Explication: Vous pouvez modifier les 4 premiers en 1 pour obtenir un tableau non décroissant.

Exemple 2:

• Entrée: nums = [4,2,1]
• Sortie: faux
• Explication: Vous ne pouvez pas obtenir un tableau non décroissant en modifiant au plus un élément.

Contraintes:

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

Code

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

Évitez toute manipulation inutile de cas spéciaux

Vous quittez tôt si la taille du tableau est inférieure à 3, mais cela n'est pas nécessaire: le reste du code gère déjà correctement les tableaux de taille 0, 1 et 2. Vous pouvez enregistrer un cycle si vous lui alimentez un petit tableau, mais vous payez ce chèque avec un cycle ou deux pour chaque fois que la fonction est appelée avec std::size(nums)> 2.

Utiliser std::size_tpour les indices

Vous avez créé indexun std::int_fast32_t, mais celui-ci a une taille (probablement) différente et une signature différente de celle du résultat std::size(nums). Cela signifie que le compilateur devrait vous avoir averti d'une comparaison entre les entiers signés et non signés. Pendant que les choses fonctionnent ici, puisque vous savez que la taille du tableau d'entrée est limitée, il est préférable de l'utiliser std::size_tici pour éviter l'avertissement du compilateur. Les performances ne différeront probablement pas d'un bit, car elles indexpeuvent être conservées dans un registre CPU à tout moment.

Il n'est pas nécessaire d'utiliser std::to_string()lors de l'utilisation <<sur unstd::ostream

Lors de l'écriture dans a std::ostream, operator<<cela entraînera déjà le formatage de l'argument, il n'est donc pas nécessaire d'appeler std::to_string(). En fait, vous pouvez indiquer au flux de formater un boolsous forme de texte:

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