算法竞赛Python常用库简单总结和个人想法 |
您所在的位置：网站首页 › python书写大这个字 › 算法竞赛Python常用库简单总结和个人想法 |
算法竞赛Python常用库简单总结和个人想法
|
这还是我第一次写这种类型的文章，主要是备赛蓝桥杯这么多天了（大概从12月底，我阳过了之后），总结了一些小方法和技巧，但是也不想记录在笔记本上，索性发个文章。 首先就是Python常用库 根据我目前的刷题经验，Python的常用库主要有： math库，itertools库，datetime库 ,functools库，bisect库,heapq库，collections库，queue库 math库 常用的有这些 math.inf，可以认为是正无穷大，如果想要表示负无穷大，可以添加负号。此外还可以使用float("inf")来代替，一般用在最值上（例如解决RMQ问题时，线段树的结点都可赋值为inf（前提是该区间没有元素）） math.fabs()，绝对值 math.factorial() ，阶乘 math.gcd(a,b)，求两个数的最大公约数，非常重要。此外Python也支持math.lcm(a,b)，即两个数的最小公倍数，但是好像低版本不支持，所以不建议使用，可以直接手写 import math def lcm(a,b): return a*b//math.gcd(a,b)math.pow(x,y) 返回 x 的 y 次幂 math.sqrt(x) 根号x math.log(x[,base]) 返回以base为底,x的对数 itertools库 主要是用其中的排列组合的函数 permutations()permutations(p[, r])返回的是一个长度为 r 的所有可能排列，无重复元素 import itertools s=[1,2,3,4,5,6,7,8,9,10] for i in itertools.permutations(s,3): a=list(map(str,i)) b=" ".join(a) print(b) 这里要注意Python的排列函数它是以下标为关键字生成排列的，所以如果原本的序列是无序的，则生成的排列看起来也是无序的，这里建议先sort一下 combinations()combinations(p, r)返回的是一个长度为r的组合，它是有序的，无重复元素 即只会有123，但不会有132，321等等  datetime库 datetime库，这也是Python最厉害的库之一，相比C++来说，是Python很大的优势，（C++处理日期问题非常麻烦） 主要用以下两个类 datetime.dateime：日期和时间表示的类，功能覆盖date和time类。 datetime.timedelta： 与时间间隔有关的类。 用法：我们来看一道例题 回文日期  498这题如果用C++来写，非常的麻烦，要判断闰年，显然非常难。但是Python的datetime库非常好的解决了这个问题。 主要用到datetime里面的两个类，datetime类和timedelta类 AC代码如下： import datetime s=input() year=int(s[:4]) month=int(s[4:6]) day=int(s[6:]) dt=datetime.date(year,month,day) flag=1 while True: dt+=datetime.timedelta(days=1) s="{}{:0>2d}{:0>2d}".format(dt.year,dt.month,dt.day) if s[:]==s[::-1]: if flag: print(s) flag=False if s[0]==s[2]==s[5]==s[7] and s[1]==s[3]==s[4]==s[6]: print(s) breakfunctools库 这个库实际上用的也不是很多，主要是里面的cmp_to_key函数，众所周知，Python3移除了cmp函数，因此Python不能像C++那样通过写cmp函数来实现排序，但是Python提供了key和reverse，这个显得更加方便，因此functools的cmp_to_key函数实际上用的不是很多。 这个函数的功能主要是将cmp函数变成key。 bisect库 二分库，Python和C++一样，系统内置了一个二分查找库，且功能非常强大。 一般就会使用两个 bisect_left(nums, tgt, lo=0, hi=len(nums)) bisect_right(nums, tgt, lo=0, hi=len(nums)) bisect(nums, tgt, lo=0, hi=len(nums)) 这么看是三个，实际上是两个，因为后面两个是一样的，这个观察它的源码就知道，bisect = bisect_right 用最简单通俗易懂的说法就是bisect_left就是找第一个大于等于key的值，而bisect和bisect_right就是找第一个大于key的值 这里就用经典的LIS问题来看一下 即最长上升子序列问题，最长上升子序列的解法很多，其中最常用的就是动态规划法，但是这个算法的时间复杂度是O( n^{2})，很多时候会超时，另一种方法是贪心算法+二分查找优化，时间复杂度是O( nlogn ) 实现思想是通过遍历序列数组维护一个辅助数组，如果该序列数组的某个值比该辅助数组的最后一个元素大，则在辅助数组后面插入，否则由于辅助数组是递增的，所以可以找到第一个大于等于该数组元素的值的位置，然后替换 这里需要二分查找第一个大于等于key的值，所以需要bisect_left函数 import bisect n=int(input()) a=[0] xl=list(map(int,input().split())) a[0]=xl[0] cnt=0 for i in range(1,n): if xl[i]>a[cnt]: cnt+=1 a.append(xl[i]) else: p=bisect.bisect_left(a,xl[i]) a[p]=xl[i] print(cnt+1) #这里也给出动态规划的写法，因为有些题目如果要输出最长上升子序列，也只得考虑动态规划写法了 n=int(input()) dp=[1]*(n+1) xl=[0]+list(map(int,input().split())) for i in range(2,n+1): for j in range(i,-1,-1): if xl[j]0: heapq.heappop(pq) #出队（删除） end=time.time() print(end-start)测试一下  差距非常大，一个需要2s，一个只需要0.3秒，主要是Python的PriorityQueue类的主要作用可不是处理这些用的，因此里面还有一些复杂的其它操作，自然比较慢 所以这里建议大家使用heapq库代替PriorityQueue类 collections库 集合库，这个库里面有非常不错的集合 主要用的是deque，这个是双端队列，也就是说这个队列允许两头操作。也就是说它既可以实现栈，也可以实现队列。一般是用于替代Queue的，因为Queue的速度太慢了，而deque相对来说比较快 deque实现队列 from collections import deque n=int(input()) q=deque() for i in range(n): com=input().split() if com[0]=='1': addnum=int(com[1]) q.append(addnum) #入队 elif com[0]=='2': if q: #判空 print(q.popleft()) #出队 else: print('no') elif com[0]=='3': print(len(q)) #队列长度当然还有一些比如说 namedtuple，这个就是把元组进一步形象化了，众所周知，Python是没有C++的结构体的，但是很多我们需要结构体这种数据类型，此时可以考虑元组（前提是你不修改里面的值，否则还是用列表），这点在图的邻接表可以看出，Python的邻接表写起来非常轻松，正是因为元组，而具名元组的作用实际上就是原本要访问元组的值需要通过下标，这个可以通过一个名字，基本上就相当于你结构体访问结构体变量的方法，而且它可以修改元素的值，利用_replace from collections import namedtuple man=namedtuple("man",["name","age"]) people1=man("铁冰",20) print(people1.name) print(people1.age) people2=people1._replace(age=21) print(people2) 另外比如说 defaultdict默认值字典，实际上没啥用，主要跟一般的字典相比它在key不存在的时候会返回一个默认值，但没有啥用，字典的get方法很好的解决了这个问题 反正我刷了很多题目没有用过这2个 queue库（建议不用） 这个库是为了队列而写的，但是实际上普通的队列用deque代替，PriorityQueue用heaqp代替，所以我们可以完全不用，而且queue库不是用来做这些的，它很慢 还有就是Python的一些数据结构要会用 列表：list，相当于C++的vector（变长数组） 列表需要掌握： 基本方法：append(),从尾部添加元素，insort()，插入元素，pop(),删除元素(默认删除最后一个)，sort()方法（too import!,用的是一个Timsort，是目前世界上最厉害的排序算法了，且保证稳定，即相同元素的值不会发生交换）,count方法，等等 另外列表推导式 [0 for i in range(n+1)] 生成长度为n+1的列表 [ [0 for i in range(m+1)] for i in range(n+1)] 生成行数n+1,列数为m+1的二维列表 等价于写法 [0]*(n+1) [ [0]*(m+1) for i in range(n+1)] 字典，相当于哈希表map 基本方法 添加key，直接赋值即可 修改key，类似于数组的修改方法 这里要说明一般可以直接用get方法代替 dict2={} n=8 a=[12,23,32,14,12,32,13,12,32] for key in a: dict2[key]=dict2.get(key,0)+1 print(list(dict2.items())) #输出字典的key-value(元组形式） print(list(dict2.values())) #输出字典的values print(list(dict2.keys())) #输出字典的keys a=sorted(dict2.items(),key=lambda e:e[1]) #字典排序 print(a)还有就是set集合，主要用于去重，另外有一句话 set和dict都是用哈希表实现的，所以in操作的时间复杂度可以理解为O(1) set添加元素需要用add()方法 还有就是字符串，Python的字符串非常方便，取一部分元素，只需要切片 元组，不必多说，和列表基本上差不多，但是列表能修改，元组不能。 另外就是掌握sort()方法和sorted()函数 sort()方法是列表特有的 要相对一个元组或者字符串排序，需要sorted，但是返回的是一个列表 大概就这么多 哦，对了，还有一个就是递归的深度 Python很特殊，递归深度给的很小，需要我们手动设置一下递归深度 sys.setrecursionlimit(60000) |
【本文地址】