¿Cuál es el tamaño de los componentes de la biblioteca de funciones del módulo de programación disponibles de Python que actualmente proporcionan tres partes?
C, Java y Python son los tres lenguajes más comunes para la programación competitiva. En este artículo, destacaremos los módulos de Python más importantes desde la perspectiva de la programación competitiva y la preparación de entrevistas.
lista: una matriz de tamaño dinámico que permite la inserción y eliminación sin importar el tamaño de la matriz. También tiene las ventajas de una matriz normal, como acceso aleatorio y compatibilidad con caché. Las listas también se pueden utilizar como colas y pilas.
deque: Dequeue admite la inserción y eliminación en ambos extremos en tiempo O(1). Dado que se implementa mediante una matriz, también permite el acceso aleatorio. Podemos usar dequeue para implementar colas y pilas. Un problema de ejemplo con Deque es acceder a todas las bombas de gasolina y al valor máximo de todos los subarreglos de tamaño k.
Tenga en cuenta que no hay módulos para Queue y Stack en Python. Podemos hacer esto usando listas o deques. Se prefiere una implementación deque, especialmente para colas, ya que insertar/eliminar al principio de la lista es lento.
La cola es útil en situaciones en las que queremos tener un orden FIFO de elementos. Los ejemplos de problemas incluyen: generar un número a partir de un número dado, primer carácter no repetido en una secuencia, recorrido de orden de nivel de un árbol y sus variantes, BFS de un gráfico y sus variantes.
set y dict: Ambos implementan hash. Usamos set cuando tenemos una colección de claves. Cuando tenemos pares clave-valor, usamos un diccionario. Muy útil cuando queremos buscar, insertar y eliminar rápidamente (las tres operaciones son O(1)). Esta es una de las estructuras de datos más utilizadas en la industria y una de las más subestimadas en el mundo académico. Los problemas comunes incluyen: recuento de elementos discretos, frecuencia de elementos de una matriz, subarreglos de suma cero, unión e intersección de dos arreglos sin clasificar, etc.
heapq: Implementa Min Heap de forma predeterminada. También podemos crear un montón mínimo. Lo usamos siempre que queremos encontrar el elemento mínimo o máximo de manera eficiente. Se utiliza para implementar algoritmos populares como el algoritmo de Prim, la ruta más corta de Dijkstra, la codificación de Huffman, K elementos máximos, la compra y fusión de juguetes máximos de K matrices ordenadas y la mediana de flujos.
ordenado: Ordena secuencias como listas. Ejemplos de problemas basados en clasificación incluyen: fusionar intervalos superpuestos, plataforma mínima requerida. El Késimo elemento más pequeño, encuentra el triple con la suma dada.
bisect: utilizado para búsqueda binaria. Ejemplos de problemas basados en la búsqueda binaria son: encontrar el índice de la primera aparición, contar apariciones, elemento pico, mediana de dos matrices ordenadas.
Nota: Diferente de las colecciones C STL y Java. La biblioteca estándar de Python contiene una implementación de BST autoequilibrado. En Python, podemos usar el módulo bisect para retener un conjunto de datos ordenados. También podemos utilizar módulos PyPi como rbtree (implementación de árboles rojo-negro) y pyavl (implementación de árboles AVL).