LeetCode 665: Matriz no decreciente

Question

Estoy publicando una solución para el "Array no decreciente" de LeetCode. Si desea revisarlo, hágalo. ¡Gracias!

Problema

Dada una matriz numscon nnúmeros enteros, su tarea es verificar si podría volverse no decreciente modificando como máximo 1 elemento.

Definimos que una matriz no es decreciente si se nums[i] <= nums[i + 1]cumple para cada i (basado en 0) tal que ( 0 <= i <= n - 2).

Ejemplo 1:

• Entrada: nums = [4,2,3]
• Salida: verdadero
• Explicación: podría modificar los primeros 4 a 1 para obtener una matriz no decreciente.

Ejemplo 2:

• Entrada: nums = [4,2,1]
• Salida: falso
• Explicación: No se puede obtener una matriz no decreciente modificando como máximo un elemento.

Limitaciones:

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

Código

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

Evite el manejo innecesario de casos especiales

Salga temprano si el tamaño de la matriz es menor que 3, pero esto es innecesario: el resto del código ya maneja matrices de tamaño 0, 1 y 2 correctamente. Puede guardar un ciclo si lo alimenta con una matriz pequeña, pero paga por este cheque con uno o dos ciclos por cada vez que se llama a la función con std::size(nums)> 2.

Usar std::size_tpara índices

Hiciste indexun std::int_fast32_t, pero este tiene un tamaño diferente (probable) y una firma diferente al resultado de std::size(nums). Esto significa que el compilador debería haberle advertido sobre una comparación entre enteros firmados y sin firmar. Si bien las cosas funcionan aquí, dado que sabe que el tamaño de la matriz de entrada está restringido, es mejor usarlo std::size_taquí para evitar la advertencia del compilador. Es probable que el rendimiento no difiera ni un bit, ya que indexse puede mantener en un registro de la CPU en todo momento.

No es necesario usarlo std::to_string()cuando se usa <<en unstd::ostream

Al escribir en a std::ostream, operator<<ya se formateará el argumento, por lo que no es necesario llamar std::to_string(). De hecho, puede decirle a la transmisión que formatee boolcomo texto:

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