En el artículo anterior , hemos discutido que C++ , Java y Python son los tres lenguajes más comunes para la programación competitiva.
En este artículo, nos centraremos en los módulos de Python más importantes desde el punto de vista de la programación competitiva y la preparación de entrevistas.
list : array de tamaño dinámico que permite inserciones y eliminaciones sin importar el tamaño de la array. También tiene las ventajas de las arrays simples, como el acceso aleatorio y la compatibilidad con la memoria caché. Una lista también se puede utilizar como cola y pila.
deque : Dequeue admite inserciones y eliminaciones en ambos extremos en tiempo O(1). Dado que se implementa mediante una array, también permite el acceso aleatorio. Podemos usar dequeue para implementar Queue y Stack tanto. Los problemas de ejemplo en Deque son, visitar todas las bombas de gasolina y los máximos de todos los subarreglos de tamaño k .
Tenga en cuenta que no hay módulos para Queue y Stack en Python . Podemos implementarlos usando list o deque . Se prefiere una implementación deque, particularmente para la cola, porque la inserción/eliminación al principio de la lista es lenta.
Una cola es útil en situaciones en las que deseamos tener un orden FIFO de elementos. Los problemas de ejemplo son, generar números con un dígito dado , el primer carácter que no se repite en una secuencia , el recorrido de orden de nivel de un árbol y sus variaciones, BFS de un gráfico y sus variaciones. Consulte los problemas de práctica de la cola para obtener más práctica.
Una pila se usa en situaciones en las que deseamos tener un orden LIFO. Los problemas de ejemplo son el paréntesis equilibrado , el problema de stock span , el siguiente elemento mayor y el área más grande en un histograma . Consulte los problemas de práctica de Stack para obtener más práctica.
set y dict : Ambos implementan hashing. Usamos set cuando tenemos colección de llaves. Y usamos el diccionario cuando tenemos pares de valores clave. Útil cuando deseamos tener una búsqueda rápida, insertar y borrar (las tres operaciones son O(1)). Esta es una de las estructuras de datos más utilizadas en la industria y más subestimada en el mundo académico. Hay muchos problemas populares, contar elementos distintos , frecuencias de elementos de array , subarreglo con suma 0 y unión e intersección de dos arrays no ordenadas . Consulte Problemas de práctica de hash para obtener más práctica .
heapq : implementa Min Heap de forma predeterminada. También podemos crear un Min Heap . Se utiliza siempre que deseemos encontrar eficientemente el elemento mínimo o máximo. Se utiliza para implementar algoritmos populares como el algoritmo de Prim, la ruta más corta de Dijkstra , la codificación de Huffman , los elementos más grandes de K , la cantidad máxima de juguetes para comprar y fusionar arrays ordenadas de K , la mediana de un flujo . Consulte Problemas de práctica de montones para obtener más práctica.
sorted : Ordena una secuencia como una lista. Los problemas de ejemplo basados en la clasificación son Combinar intervalos superpuestos , Plataformas mínimas requeridas. K-ésimo elemento más pequeño , encuentre el triplete con la suma dada . Consulte Problemas de práctica de clasificación para obtener más información.
bisect : Utilizado para la búsqueda binaria. Los problemas de ejemplo basados en la búsqueda binaria son encontrar el índice de la primera ocurrencia, contar las ocurrencias, el elemento máximo , la mediana de las arrays ordenadas de dos en dos . Consulte Problemas de práctica de búsqueda binaria para obtener más información.
Nota: A diferencia de C++ STL y Java Collections . La biblioteca estándar de Python contiene la implementación de Self Balancing BST. En Python, podemos usar el módulo bisect para mantener un conjunto de datos ordenados. También podemos usar módulos PyPi como rbtree (implementación del árbol rojo y negro) y pyavl (implementación del árbol AVL).
Cubriremos bibliotecas de Python más importantes en la siguiente parte de este artículo.
Si es un principiante en Python, es posible que desee probar el Curso gratuito para principiantes de Python .