python算法常用技巧及内置库近年来，随着python越来越流行，python逐渐成为了很多程序员的最爱。许多程序员已经开始使用python作为他们解决问题的第一语言。最近在用python刷题的时候，想找一些常用的python库API和刷题技巧。类似于C++的STL库文档，可惜没找到，所以决定结合自己刷题和上网搜索的经验做一个文档给自己和大家看。1.输入输出：1.1第一行给定两个值n和m，用空格隔开，第一个n决定接下来n行输入，m决定每行有多少个数，m个数都是间隔分离。解决方案：python的input函数接收的输入默认都是字符串，所以我们可以通过字符串切割、强制类型转换、列表生成器来完美解决输入问题。代码如下：#接收两个值，用n,m分别接收列表中的两个值n,m=[int(x)forxininput().split()]#构造一个输入列表listsnum_list=[]foriinrange(n):#python可以忽略m的值，接收所有的值并用len判断长度，)来分开，只要传入相同的值给split函数即可。1.2输出一行数字由于python的print函数默认使用换行符作为结束符，所以我们需要修改为我们需要的区间。代码如下：foriinrange(10):print(i,end='')end是print函数中的一个参数，决定了输出的结束符，这里改成空格表示输出一行数字，空格分隔，其他字符可自行修改。2.空列表生成、字符串修改、列表遍历2.1在写代码的过程中，有时会需要一个有长度和初始值的空列表。生成方法如下：#1。通过乘法生成一个初始值为False的一维列表，长度为100visited=[False]*100#2。使用列表生成器生成一个初始值为0的二维n*m列表如果每次修改都生成一个新的字符串，对于修改次数多且字符串合适的情况，开销会非常大。所以一般是把字符串转成列表进行修改，再转回来。string='Ilovetoeatchen'#将字符串转换成列表string_list=list(string)#......修改字符串列表#代码#将字符串列表重新组合成字符串#string=''。join(string_list)2.3在python中有许多不同的遍历列表的方法。最直接的方式就是直接遍历列表，但是由于我们经常根据索引对数组进行操作，需要修改数组的值，所以更推荐使用下面代码中的第二种和第三种方法：num_list=[iforiinrange(10)]#1。直接迭代iteminnum_list的列表：#Codepass#2。遍历索引foriinrange(len(num_list)):print(num_list[i])#3。遍历枚举函数forindex,valueinenumerate(num_list):#index为当前元素的索引，value为当前元素的值print(index,value)3.集合库的使用3.1deque队列deque是一个队列在python中（FIFO先进先出），弹出队头时队列会比列表快。特别是在使用BFS（深度优先搜索）的时候，必须要用到队列。deque部分使用代码如下：fromcollectionsimportdeque#初始化一个最大长度为3的队列d=deque([1,2,3],maxlen=3)#因为初始化的队列最大长度为3，加入元素会把队头的元素挤出来d.append(4)#初始化一个无限长的队列d=deque()#添加元素到队尾d.append(1)d.append(2)d.append(3)#将队头的元素弹出并返回print(d.popleft())#将队尾的元素弹出并返回值print(d.pop())#插入队列头部的元素d.appendleft(0)3.2CounterCounterCounter是一个计数器，可以用来对一个序列进行Count，统计一个元素在一个序列中出现的次数。以下是示例代码：importcollections#初始方法#1共有三个。传入一个序列print(collections.Counter(['a','b','c','a','b','b']))#2。传入字典print(collections.Counter({'a':2,'b':3,'c':1}))#3。直接用=传参print(collections.Counter(a=2,b=3,c=1))#也可以不带参数构造，使用update函数更新c=collections.Counter()print('Initial:',c)#Initial:Counter()c.update('abcdaab')print('Sequence:',c)#Sequence:Counter({'a':3,'b':2,'c':1,'d':1})c.update({'a':1,'d':5})print('Dict:',c)#Dict:Counter({'d':6,'a':4,'b':2,'c':1})#通过访问字典forletterin'abcde'可以访问Counter对象:print('%s:%d'%(letter,c[letter]))#elements()方法可以返回一个包含所有Counter数据的列表迭代器c=collections.Counter('extremely')c['z']=0print(list(c.elements()))#['e','e','e','m','l','r','t','y','x']#most_common()返回前n个最多的数据c=collections.Counter('aassddddffff')forletter,countinc.most_common(2):print('%s:%d'%(letter,count))#f:4#d:3#计数器对象可以进行加减合并，直接用运算符+、-、&、|#+将组合两个在字典中添加相同字符的出现ary,-将给出第一个计数器相对于第二个计数器的差值。Intersection给出了两个计数器的元素，计数分配给较小的那个，union是两个计数器中元素最多的那个。c1=collections.Counter(['a','b','c','a','b','b'])c2=collections.Counter('alphabet')print('C1:',c1)print('C2:',c2)print('\nCombinedcounts:')print(c1+c2)print('\n减法:')print(c1-c2)print('\nIntersection(takingpositiveminimums):')print(c1&c2)print('\nUnion(takingmaximums):')print(c1|c2)#下面是输出：C1:Counter({'b':3,'a':2,'c':1})C2:Counter({'a':2,'l':1,'p':1,'h':1,'b':1,'e':1,'t':1})Combinedcounts:Counter({'a':4,'b':4,'c':1,'l':1,'p':1,'h':1,'e':1,'t':1})减法：Counter({'b':2,'c':1})Intersection(取正最小值):Counter({'a':2,'b':1})Union(取最大值):Counter({'b':3,'a':2,'c':1,'l':1,'p':1,'h':1,'e':1,'t':1})3.3defaultdict——有默认值的字典正常情况下创建的字典dict是不包含默认值的，即字典中不包含keya，调用dct{a}会报错。在设计算法和数据结构时，我们希望任何给定的键都能从字典中得到一个值，即使它只是一个默认值。这时候我们就需要用到defaultdict了。例如，当用字典来表示图中某个节点的连接节点时，我们希望以这个节点作为键，然后形成一个与它连接的节点列表作为它的值。这时候我们可以使用defaultdict(list)来创建一个默认值为list的字典。#list的默认值是一个空列表[]#Output:03.4小结这些是经常用来写集合中的算法和数据结构的。其他如排序字典和命名元组很少使用。4.排序4.1对列表进行排序有两种方法可以对列表进行排序。一种是使用列表内置的排序功能。排序函数直接在列表中修改，没有返回值。可以通过参数key自定义比较的key和比较函数。第二种是利用python的sorted函数。该功能具有较高的自由度。可以自己设置比较函数和比较键，返回一个新的列表。如果需要自定义比较函数，需要从库functools中导入函数cmp_to_key函数，将比较函数转换为key。代码如下：defcustom_sort(x,y):ifx>y:#return-1表示需要在前面return-1ifx
