python算法常用技巧及内置库近年来，随着python的火爆程度越来越高，python逐渐成为了很多程序员的最爱。许多程序员已经开始使用python作为他们解决问题的第一语言。最近在用python刷题的时候，想找一些常用的python库API和刷题技巧。类似于C++的STL库文档，可惜没找到，所以决定结合自己刷题和上网搜索的经验做一个文档给自己和大家看。1.输入输出：1.1第一行给定两个值n和m，用空格隔开，第一个n决定接下来n行输入，m决定每行有多少个数，m个数都是间隔分离。解决方案：python的input函数接收的输入默认都是字符串，所以我们可以通过字符串切割、强制类型转换、列表生成器来完美解决输入问题。代码如下：#接收两个值，用n,m分别接收list中的两个值n,m=[int(x)forxininput().split()]#构造一个listinputlistsnum_list=[]foriinrange(n):#python可以接收所有的值而不考虑m的值，然后用len判断长度tmp_list=[int(x)forxininput(.split()]num_list.append(tmp_list)同理，如果用逗号（,）隔开，只要传入相同的值给split函数即可。1.2输出一行数字由于python的print函数默认使用换行符作为结束符，所以我们需要修改为我们需要的区间。代码如下：foriinrange(10):print(i,end='')endisprint函数中的一个参数决定了输出的结束字符。这里改成空格就是输出一行数字，用空格隔开，其他字符可以自己修改。2.空列表生成、字符串修改、列表遍历2.1在写代码的过程中，有时会需要一个有长度和初始值的空列表。生成方法如下：#1.通过乘法生成一个初始值为False的长度为100的一维列表visited=[False]*100#2.使用列表生成器生成一个n*m的二维-初始值为0的维列表visited=[[0foriinrange(m)]forjinrange(n)]2.2字符串不能在python中就地修改。如果每次修改都生成一个新的字符串，如果修改很多，字符串合适的话，开销会很大。.所以一般是把字符串转成列表进行修改，再转回来。string='Ilovetoeatchicken'#将字符串转换成列表string_list=list(string)#......修改字符串列表#代码#将字符串列表重新组合成字符串#string=''.join(string_list)2.3在python中遍历列表有很多不同的方法。最直接的方式就是直接遍历list，但是因为我们经常根据索引对数组进行操作，需要修改数组的值，所以下面的代码中更推荐使用第二种和第三种方式:num_list=[iforiinrange(10)]#1.直接遍历列表foriteminnum_list:#Codepass#2.遍历索引foriinrange(len(num_list)):print(num_list[i])#3.遍历枚举函数forindex,valueinenumerate(num_list):#index是当前元素的索引，value是当前元素的值print(index,value)3.集合的使用library3.1dequequeuedeque是python中的一个队列（FIFO先进先出），队列出队头时会比list快。特别是在使用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是一个计数器，可以对一个序列进行计数，统计一个元素在序列中出现的次数。以下是示例代码：importcollections#初始方法有3种#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})#你可以通过访问'abcde'中字母的字典来访问Counter对象：print('%s:%d'%(letter,c[letter]))#elements()方法可以返回一个包含所有Counter数据的Iterator的listc=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,计入c。most_common(2):print('%s:%d'%(letter,count))#f:4#d:3#计数器对象可以直接使用操作符+、-、&、|进行加减合并#+将添加相同字符在两个词典中出现的次数，-将给出第一个Counter相对于第二个减法交集给两个计数器中的元素分配给较小的一个计数，并集是两个计数器的元素出现次数最多的那个。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('\nSubtraction:')print(c1-c2)print('\nIntersection(takingpositiveminimum):')print(c1&c2)print('\nUnion(取最大值):')print(c1|c2)#下面是输出：C1:Counter({'b':3,'a':2,'c'：1}）C2：计数器（{'a'：2，'l'：1，'p'：1，'h'：1，'b'：1，'e'：1，'t':1})组合计数：Counter({'a':4,'b':4,'c':1,'l':1,'p':1,'h':1,'e':1,'t':1})Subtraction:Counter({'b':2,'c':1})Intersection(takingpositiveminimum):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默认值为空列表list_dict=collections.defaultdict(list)#int默认值为0int_dict=collections.defaultdict(int)print(list_dict['a'])print(int_dict['a'])#output:[]#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
