Categorías
c++

Preordenar el recorrido del árbol binario (Revisión de la estructura de datos básica)

Dado un árbol binario, devuelva su recorrido anterior.

Ejemplo:

Entrada: [1,null,2,3] ​
1

2
/
3

Salida: [1,2,3]

Fuente: LeetCode
enlace: https://leetcode-cn.com/problems/binary-tree-preorder-traversal
Los derechos de autor pertenecen a Lingkou Network. Para reimpresiones comerciales, póngase en contacto con la autorización oficial. Para reimpresiones no comerciales, indique la fuente.

El recorrido se resuelve fácilmente mediante recursividad, pero la función original requiere que vector<int> se devuelva cada vez, por lo que se vuelve muy sencillo volver a definir una función para volver a repetir y llevar el valor a la función original. A continuación se muestra el código

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void _preorderTraversal(TreeNode* root,vector<int> *p)
    {
        if(root==NULL)
        {
            return ;
        }
        (*p).push_back(root->val);
        _preorderTraversal( root->left,p);
        _preorderTraversal(root->right,p);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>a;
        _preorderTraversal(root,&a);
        return a;
    }
};

.

Categorías
c++

Interfaz de tiempo unix

«Programación práctica del sistema con C++» notas de lectura once

POSIX time API time.h

La API de tiempo de POSIX se basa en la C estándar, pero todavía debe usarse en C++.

Tipo de API

Los tipos de datos de tres tiempos se definen en POSIX API time.h:

  • tm: una estructura que encapsula la fecha y la hora;
  • time_t: una unidad que representa segundos, normalmente un entero;
  • clock_t: tiempo de procesador utilizado por la aplicación

Tenga en cuenta que hay diferentes definiciones de tiempo:

  • Reloj del sistema: la fecha y hora mantenidas por el sistema operativo, que pueden modificarse en cualquier momento
  • Reloj constante: contador del tiempo de ejecución del programa
  • Reloj de alta resolución: Igual que el reloj constante, pero con mayor precisión, a menudo se utiliza como una prueba de tiempo de referencia

time() API

Se utiliza para devolver la hora del sistema.

#include <ctime>
#include <iostream>

int main()
{
    auto t = time(nullptr);
    std::cout << "time: " << t << 'n'; // 1594069715
    time(&t);
    std::cout << "time: " << t << 'n'; // 1594069715
}

ctime() typedef

Se utiliza para convertir punteros de tipo time_t en punteros de cadena reconocibles. El contenido de la dirección no necesita ser liberado, ni es seguro para subprocesos.

#include <ctime>
#include <iostream>

int main()
{
    auto t = time(nullptr);
    std::cout << "time: " << ctime(&t) << 'n'; // Mon Jul  6 14:18:20 2020

}

local() y gmtime()

Se utiliza para convertir la hora local y la hora de Greenwich de time_t datos de tipo y devolver una estructura de tipo tm. Lo mismo ocurre con la conversión de tipos de puntero.

función asctime()

Convierta la estructura tm en una cadena legible.

#include <ctime>
#include <iostream>

int main()
{
    auto t = time(nullptr);
    std::cout << "time: " << asctime(localtime(&t)) << 'n';
    // time: Mon Jul  6 14:30:03 2020
    std::cout << "time: " << asctime(gmtime(&t)) << 'n';
    // time: Mon Jul  6 21:30:03 2020
}

función strftime()

Teniendo en cuenta la seguridad del subproceso y el formato de salida personalizable, el método de conversión recomendado es la función strftime().

#include <ctime>
#include <iostream>

int main()
{
    auto t = time(nullptr);
    char buf[256] {};
    strftime(buf, sizeof(buf), "%m/%d/%Y", localtime(&t));
    std::cout << "time: " << buf << 'n'; // 07/06/2020
    strftime(buf, sizeof(buf), "%H:%M", localtime(&t));
    std::cout << "time: " << buf << 'n'; // 14:46
    strftime(buf, sizeof(buf), "%a %b %d %H:%M:%S %Y", localtime(&t));
    std::cout << "time: " << buf << 'n'; // Mon Jul 06 14:46:25 2020
}

función difftime()

Compare la diferencia entre dos datos de tipo time_t.

#include <ctime>
#include <iostream>
#include <unistd.h>

int main()
{
    auto t1 = time(nullptr);
    sleep(2);
    auto t2 = time(nullptr);
    std::cout << "diff: " << difftime(t2, t1) << 'n'; // 2
    std::cout << "diff: " << t2 - t1 << 'n'; // 2
}

difftime() es más versátil que el método de resta directa.

función mktime()

Convierta la estructura tm en el tipo de time_t, que es lo opuesto a las funciones localtime() y gmtime().

#include <ctime>
#include <iostream>

int main()
{
    auto t1 = time(nullptr);
    auto lt = localtime(&t1);
    auto t2 = mktime(lt);
    std::cout << "time: " << ctime(&t2) << 'n'; // Mon Jul  6 15:11:30 2020
}

función clock()

La función clock() devuelve el tipo de clock_t, que no se ve afectado por el cambio de hora del sistema y se utiliza para cronometrar la aplicación. POSIX proporciona la macro CLOCKS_PER_SEC convertir con tiempo físico.

#include <ctime>
#include <iostream>
#include <unistd.h>

int main()
{
    std::cout << "clock: " << clock() << 'n'; // 3883
    auto c1 = clock();
    sleep(2);
    auto c2 = clock();
    std::cout << "clock: " << 
        static_cast<double>(c2 - c1) / CLOCKS_PER_SEC << 'n';
    // 4.4e-05
}

Tenga en cuenta que el ejemplo anterior duerme durante dos segundos, y el tiempo sólo avanza 44us, porque sólo el tiempo de ejecución real del programa se cronometra por reloj (), y el tiempo de sueño no se cuenta. En el ejemplo siguiente se muestra además este punto.

#include <ctime>
#include <iostream>
#include <unistd.h>

int main()
{
    auto c1 = clock();
    auto t1 = time(nullptr);
    while(time(nullptr) - t1 <= 2);
    auto c2 = clock();
    std::cout << "clock: " << 
        static_cast<double>(c2 - c1) / CLOCKS_PER_SEC << 'n';
    // 2.60372
}

Explore las API de C++ Chrono

La mayor parte de la API de Chrono proporcionada por C++ es una encapsulación de la biblioteca time.h. Debería haber mucha riqueza en C++20. Este artículo todavía se basa en C++17.

SYSTEM_CLOCK() API

system_clock() es similar a time() y también se utiliza para obtener el tiempo del sistema. El valor devuelto se puede convertir en time_t.

#include <chrono>
#include <iostream>

int main()
{
    auto t = std::chrono::system_clock::now();
    std::cout << "time: " << 
        std::chrono::system_clock::to_time_t(t) << 'n';
    // 1594075202
}

API de time_point

El valor devuelto real de now() en el ejemplo anterior es time_point{}. En la biblioteca Chrono, time_point{} se puede aumentar, disminuir y comparar.

#include <chrono>
#include <iostream>

template <typename C, typename D>
std::ostream & operator <<(std::ostream &os, 
    const std::chrono::time_point<C, D> &obj)
{
    auto t = std::chrono::system_clock::to_time_t(obj);
    return os << ctime(&t);
}

int main()
{
    using namespace std::chrono;

    auto now1 = std::chrono::system_clock::now();
    auto now2 = std::chrono::system_clock::now();
    std::cout << "time: " << now1; // Mon Jul  6 15:58:49 2020
    now2 += 1h;
    std::cout << "time: " << now2; // Mon Jul  6 16:58:49 2020
    now1 -= 1h;
    std::cout << "time: " << now1; // Mon Jul  6 14:58:49 2020
    std::cout << std::boolalpha;
    std::cout << "compare: " << (now1 < now2) << 'n'; // true
    std::cout << "compare: " << (now1 > now2) << 'n'; // false
    std::cout << "compare: " << (now1 <= now2) << 'n'; // true
    std::cout << "compare: " << (now1 >= now2) << 'n'; // false
    std::cout << "compare: " << (now1 == now2) << 'n'; // false
    std::cout << "compare: " << (now1 != now2) << 'n'; // true
}

Debido a las diferentes resoluciones del sistema, los resultados en el ejemplo anterior pueden ser diferentes.

Duración

Duración{} es el período de tiempo implicado en el cálculo de time_point{}. C++ define los siguientes literales para describir el período de tiempo:

  • Hora: h
  • Minutos: min
  • Segundos: s
  • Milisegundos: ms
  • Microsegundos: nosotros
  • Nanosegundo: ns

std::chrono proporcionananosegundos/microsegundos/milisegundos/segundos/minutos/horasPara realizar la conversión.

#include <chrono>
#include <iostream>
#include <unistd.h>

int main()
{
    using namespace std::chrono;

    auto now1 = system_clock::now();
    sleep(2);
    auto now2 = system_clock::now();
    std::cout << "time: " << 
        duration_cast<seconds>(now2 - now1).count() << 'n';
    // 2
    std::cout << "time: " << 
        duration_cast<milliseconds>(now2 - now1).count() << 'n';
    // 2000
    std::cout << "time: " << 
        duration_cast<nanoseconds>(now2 - now1).count() << 'n';
    // 2000253400
}

Al igual que time_point{}, también se puede calcular la duarción.

#include <chrono>
#include <iostream>

int main()
{
    using namespace std::chrono;

    seconds t(42);
    t++;
    std::cout << "time: " << t.count() << 'n'; // 43
    t--;
    std::cout << "time: " << t.count() << 'n'; // 42
    t += 1s;
    std::cout << "time: " << t.count() << 'n'; // 43
    t -= 1s;
    std::cout << "time: " << t.count() << 'n'; // 42
    t %= 2s;
    std::cout << "time: " << t.count() << 'n'; // 0
}

También se puede comparar duration{}, lo mismo que time_point{}.
Duraiton{} ya puede realizar operaciones como redondeo y valor absoluto en C++17.

#include <chrono>
#include <iostream>

int main()
{
    using namespace std::chrono;

    auto s1 = -42001ms;
    std::cout << "floor: " << floor<seconds>(s1).count() << 'n'; // -43
    std::cout << "ceil: " << ceil<seconds>(s1).count() << 'n'; // -42
    std::cout << "round: " << round<seconds>(s1).count() << 'n'; // -42
    std::cout << "abs: " << abs(s1).count() << 'n'; // 42001
}

función steady_clock

steady_clock{} es similar a la función clock() y se utiliza para obtener el tiempo de ejecución del programa.

#include <chrono>
#include <iostream>
#include <unistd.h>

int main()
{
    using namespace std::chrono;

    auto now1 = steady_clock::now();
    sleep(2);
    auto now2 = steady_clock::now();
    std::cout << "time: " << 
        duration_cast<seconds>(now2 - now1).count() << 'n';
    // 2
    std::cout << "time: " << 
        duration_cast<milliseconds>(now2 - now1).count() << 'n';
    // 2000
    std::cout << "time: " << 
        duration_cast<nanoseconds>(now2 - now1).count() << 'n';
    // 2000143400
}

Tenga en cuenta que a diferencia de clock(), esta vez se incluye el tiempo sleep().

función high_resolution_clock

high_resolution_clock representa el tiempo de resolución más alto proporcionado por el sistema. De hecho, es lo mismo que steady_clock en la mayoría de los sistemas.

Un ejemplo de reloj del sistema

En el ejemplo siguiente se seguirá imprimiendo la hora actual del sistema y el intervalo de impresión se controla mediante el parámetro de entrada. La compilación requiere cmake, nada nuevo.

#include <chrono>
#include <iostream>
#include <gsl/gsl>
#include <unistd.h>

using namespace std::chrono;

template<typename C, typename D>
std::ostream & operator << (std::ostream &os,
    std::chrono::time_point<C,D> &obj)
{
    auto t = std::chrono::system_clock::to_time_t(obj);
    return os << ctime(&t);
}

int protected_main(int argc, char **argv)
{
    using namespace std::chrono;
    auto args = gsl::make_span(argv, argc);

    if (args.size() != 2) {
        std::cerr << "wrong number of argumentsn";
        ::exit(1);
    }

    gsl::cstring_span<> arg = gsl::ensure_z(args[1]);

    while(true) {
        auto now = std::chrono::system_clock::now();
        std::cout << "time: " << now;

        sleep(std::stoi(arg.data()));
    }
}

int main(int argc, char **argv)
{
    try {
        return protected_main(argc, argv);
    }
    catch (const std::exception &e) {
        std::cerr << "Caught unhandled exception:n";
        std::cerr << " - what(): " << e.what() << 'n';
    }
    catch (...) {
        std::cerr << "Caught unknown exceptionn";
    }

    return EXIT_FAILURE;
}

Un ejemplo de reloj de alta precisión

El ejemplo siguiente es un programa de prueba de sincronización para un ciclo determinado. Como el programa en pruebas, el cuerpo del bucle se da en forma de lambda. El programa del libro original está enargs.at(1)No se puede compilar, se cambió aArgs[1]

#include <chrono>
#include <iostream>
#include <gsl/gsl>

template<typename FUNC>
auto benchmark(FUNC func) {
    auto stime = std::chrono::high_resolution_clock::now();
    func();
    auto etime = std::chrono::high_resolution_clock::now();

    return etime - stime;
}

int protected_main(int argc, char **argv)
{
    using namespace std::chrono;

    auto args = gsl::make_span(argv, argc);

    if (args.size() != 2) {
        std::cerr << "wrong number of argumentsn";
        ::exit(1);
    }

    gsl::cstring_span<> arg = gsl::ensure_z(args[1]);

    auto d = benchmark([&arg]{
        for (uint64_t i = 0; i < std::stoi(arg.data()); i++);
    });

    std::cout << "time: " <<
        duration_cast<seconds>(d).count() << 'n';

    std::cout << "time: " <<
        duration_cast<milliseconds>(d).count() << 'n';

    std::cout << "time: " <<
        duration_cast<nanoseconds>(d).count() << 'n';
}

int main(int argc, char **argv)
{
    try {
        return protected_main(argc, argv);
    }
    catch (const std::exception &e) {
        std::cerr << "Caught unhandled exception:n";
        std::cerr << " - what(): " << e.what() << 'n';
    }
    catch (...) {
        std::cerr << "Caught unknown exceptionn";
    }

    return EXIT_FAILURE;
}

.