哪些Python模块可用于编程竞赛?

C++,Java和Python是竞争性编程的三种最常见的语言。在本文中,我们将从竞争性编程和面试准备的角度重点介绍最重要的Python模块。

list:动态大小的数组,允许在不关心数组大小的情况下进行插入和删除。它还具有普通数组的优点,例如随机访问和缓存友好性。list也可以用作队列和堆栈。

deque:Dequeue支持在O(1)时间内在两端进行插入和删除。由于它是使用数组实现的,因此它也允许随机访问。我们可以使用dequeue来实现队列和堆栈。关于Deque的示例问题是,访问所有的汽油泵和所有大小为k的子阵列的最大值。

请注意,Python中没有用于队列(Queue)和堆栈(Stack)的模块。我们可以使用列表(list)或双端队列(deque)来实现这些。首选双端队列(deque)实现,尤其是对于队列,因为在列表前面进行插入/删除很慢。

在我们希望具有FIFO项目顺序的情况下,队列(Queue)很有用。问题示例包括:用给定的数字生成数字,流中的第一个非重复字符,树及其变体的级序遍历,图的BFS及其变体。

setdict:它们都实现了哈希。当我们有键的集合时,我们使用set。当我们有键值对时,我们使用字典(dictionary)。当我们希望快速搜索、插入和删除时非常有用(这三个操作都是O(1))。这是业界使用最多的数据结构之一,也是学术界最低估的数据结构之一。常见的问题有:离散元素的计数、数组项的频率、零和子阵、两个未排序数组的并集、交集等。

heapq:默认情况下实现Min Heap。我们也可以创建最小堆。只要我们希望有效地找到最小或最大元素,就使用它。它用于实现流行的算法,例如Prim算法,Dijkstra最短路径,霍夫曼编码,K个最大元素,购买和合并K个排序数组的最大玩具,流的中位数。

sorted:对列表等序列进行排序。基于排序的示例问题包括:合并重叠间隔,所需的最小平台。第K个最小元素,求给定和的三元组。

bisect:用于二进制搜索。基于二进制搜索的示例问题有:查找第一次出现的索引、计数出现次数、峰值元素、两个排序数组的中值。

注意:与C++ STL和Java集合(Collections)不同。Python标准库包含自平衡BST的实现。在Python中,我们可以使用bisect模块来保留一组排序后的数据。我们还可以使用PyPi模块,例如rbtree(红黑树的实现)和pyavl(AVL树的实现)。

六一编程网

Next Post

哪些编码习惯可以改善编码竞赛的时间安排?

周六 8月 8 , 2020
离线或在线参与编码挑战和黑客马拉松是有趣和富有成效的。在这些竞赛中,你可以展示你的技能并因此获得奖励 […]