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) for x in input().split()]# 构造输入列表的列表num_list = []for i in range(n):# python可以不用在意m的值，将所有数值接收进来然后使用len判断长度tmp_list = [int(x) for x in input().split()]num_list.append(tmp_list)

同理，若是用逗号(,)分隔的话，split函数中传入相同的值就行。

1.2 输出一行数字

由于python的print函数默认利用换行作为结束符，所以我们需要将它修改成我们需要的间隔，代码如下:

for i in range(10):print(i, end=\' \')

end是print函数中的一个参数，决定输出的结束字符，这里修改成空格代表输出一行数字，用空格间隔，其它字符可以自行修改。

2.空列表生成，字符串修改，列表遍历

2.1 代码编写过程中，有时候会需要一个带有长度的，有初始值的空列表，生成方式如下:

# 1. 用乘法生成一个初始值为False的长度为100的一维列表visited = [False] * 100# 2. 利用列表生成器生成一个n*m的二维的初始值为0的列表visited = [[0 for i in range(m)] for j in range(n)]

2.2 在python当中字符串是无法原地修改的，如果每次修改都生成一个新字符串，那么对修改次数很多且字符串很当的情况，开销是很大的。所以一般是把字符串转为列表进行修改最后再转回来。

string = \'I love to eat chicken\'# 将字符串转换成列表string_list = list(string)# .......对字符串列表进行修改# Code# 将字符串列表重新拼接成字符串#string = \'\'.join(string_list)

2.3 python中列表遍历有许多种不同的方式，最直接的办法是直接对列表进行迭代遍历，但是因为我们往往是基于索引对数组进行操作且需要修改数组的值，所以更推荐用以下代码中的第二三中办法:

num_list = [i for i in range(10)]# 1. 直接迭代列表for item in num_list:# Codepass# 2. 通过索引进行迭代for i in range(len(num_list)):print(num_list[i])# 3. 通过enumerate函数进行迭代for index, value in enumerate(num_list):# index为当前元素的索引，value为当前元素的值print(index, value)

3. collections库的使用

3.1 deque队列

deque 是python中的队列（FIFO先进先出），队列在进行队首弹出的时候会比list要快。

尤其在使用BFS（深度优先搜索）的时候，队列是必须要使用到的。部分deque使用代码如下:

from collections import deque# 初始化一个最大长度为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.2 Counter计数器

Counter

是一个计数器，可以对一个序列计数，计算序列中某个元素出现的数量。

以下是示例代码:

import collections# 一共有三种初始方法# 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)56c# 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})# 可以通过访问字典的访问方式访问Counter对象for letter in \'abcde\':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(\'aassdddffff\')for letter, count in c.most_common(2):print(\'%s: %d\' % (letter, count))# f: 4# d: 3# Counter对象可以进行加减交并，直接使用运算符 +、-、&、|# +会将两个字典中相同字符的出现次数相加，-会给出第一个Counter相对于第二个的差集。交集给出两个计数器当中都有的元素，且计数被赋值为较小的那个，并集为两个计数器的元素出现最多的那个。c1 = collections.Counter([\'a\', \'b\', \'c\', \'a\', \'b\', \'b\'])c2 = collections.Counter(\'alphabet\')print (\'C1:\', c1)print (\'C2:\', c2)print (\'\\nCombined counts:\')print (c1 + c2)print (\'\\nSubtraction:\')print (c1 - c2)print (\'\\nIntersection (taking positive minimums):\')print (c1 & c2)print (\'\\nUnion (taking maximums):\')print (c1 | c2)# 以下为输出：C1: Counter({\'b\': 3, \'a\'56c: 2, \'c\': 1})C2: Counter({\'a\': 2, \'l\': 1, \'p\': 1, \'h\': 1, \'b\': 1, \'e\': 1, \'t\': 1})Combined counts:Counter({\'a\': 4, \'b\': 4, \'c\': 1, \'l\': 1, \'p\': 1, \'h\': 1, \'e\': 1, \'t\': 1})Subtraction:Counter({\'b\': 2, \'c\': 1})Intersection (taking positive minimums):Counter({\'a\': 2, \'b\': 1})Union (taking maximums):Counter({\'b\': 3, \'a\': 2, \'c\': 1, \'l\': 1, \'p\': 1, \'h\': 1, \'e\': 1, \'t\': 1})

3.3 defaultdict——带有默认值的字典

一般情况下创建的字典dict是不含有默认值的，即若是字典中不包含a这个key，调用dct{a}的话就会报错。

在进行算法设计和数据结构设计的时候我们希望任意给定一个key都能从字典中取出值来，哪怕只是一个默认值，这个时候我们就需要用到

defaultdict

。

例如在用字典表示图中一个节点的相连节点的时候，我们希望将这个节点作为一个key，然后与它相连的节点组成一个列表作为它的value，这个时候我们就可以使用defaultdict(list)来创建一个默认值为列表的字典。

# list的默认值为空列表list_dict = collections.defaultdict(list)# int的默认值为0int_dict = collections.defaultdict(int)print(list_dict[\'a\'])print(int_dict[\'a\'])# 输出：[]# 输出：0

3.4 小结

4.1 对列表排序

对列表排序有两种方法，一种是使用列表内置的sort函数，sort函数直接在列表原地修改，无返回值，可以通过参数key自定义比较的key和比较函数。

第二种就是使用python的sorted函数，这个函数自由度比较高，可以自己设定比较函数和比较的key，返回一个新的列表。

如果需要自定义比较的函数，需要从库

functools

导入函数

cmp_to_key

函数，将比较函数转为key，使用代码如下:

def custom_sort(x,y):if x>y:# 返回-1代表需要排在前面return -1if x<y:# 返回1代表需要排在后面return 1return 0lst = [i for i in range(10, -1, -1)]print(lst)lst.sort()print(lst)print(sorted(lst, key=cmp_to_key(custom_sort)))# 输出如下：# [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]# [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

4.2 对字典/元组列表排序

若是需要对字典（将字典利用

item

函数转化成元组列表）或者元组列表这种每一个item有两个值的序列进行排序，这个时候就需要利用sorted函数中的key来决定取哪个值排序。代码如下:

# 利用字符串创建计数器字典d = dict(collections.Counter(\'Hello World\'))print(d)# 排序print(sorted(d.items(), key=lambda x: x[1], reverse=True))# 输出如下：# {\'H\': 1, \'e\': 1, \'l\': 3, \'o\': 2, \' \': 1, \'W\': 1, \'r\': 1, \'d\': 1}# [(\'l\', 3), (\'o\', 2), (\'H\', 1), (\'e\', 1), (\' \', 1), (\'W\', 1), (\'r\', 1), (\'d\', 1)]

5.排列组合

python内置的模块itertools中集成了一些与迭代有关的函数，其中就有排列组合函数。

5.1 排列

排列函数

permutations

接收一个列表，返回这个列表内所有元素的全排列列表。

from itertools import permutationsprint(list(permutations([1,2,3])))# 输出如下：# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

5.2 组合

组合函数

combinations

接收两个参数，第一个为一个需要进行组合的列表，第二个参数为一个正整数，代表从列表中抽取多少个元素进行组合，返回一个组合列表。

from itertools import co103dmbinationsprint(list(combinations([1,2,3],2)))# 输出如下：# [(1, 2), (1, 3), (2, 3)]

6.小技巧

6.1 在python中分了可变类型和不可变类型，当函数传参的时候：

• 若是不可变类型如字符串，则传递参数的时候会深拷贝一份，在新的数据上修改并不改变原数据
• 若是可变类型如列表，则传递参数的时候传递的是引用，属于浅拷贝，在函数中对新列表进行操作会影响到原来的列表。

若是确实需要传递可变类型进入函数，则可以在函数内部第一行进行一次深拷贝如：

def test(num_list:list):# 进行深拷贝num_list = num_list[:]

6.2 当删除列表中的元素的时候，列表后面的元素会自动往前移动，导致出错

例如，列表为

[1,2,3,4,5,6]

，想要删除列表中的偶数，如果直接找到一个偶数然后利用其索引删除，如下代码所示（错误示范），那么很抱歉，出问题了。

# 此处为错误示范！！！！！！！！lst = [1, 2, 3, 4, 5, 6]for i in range(len(lst)):if lst[i] % 2 == 0:lst.pop(i)print(lst)# 上面这段代码没有输出，因为报索引越界错误了。

下面的代码才是正确示范：

lst = [1, 2, 3, 4, 5, 6]lst = [i for i in lst if i % 2 != 0]print(lst)# 输出如下：# [1, 3, 5]

若是需要更复杂的筛选手段，可以在

if i%2 !=0

那里更改成一个函数判断，函数内部就实现筛选方法。

6.3 访问字典元素要使用get方法

前文说过，普通的dict字典是没有默认值的，所以这个时候如果直接利用中括号放置key来查找value的话是有可能会报错的。

那么为了避免这种情况，在利用字典的key来取value的时候，需要利用字典的

get

函数。

get

函数的第一个参数为key，第二个参数为可选（默认为None），当字典中找不到传入的key的时候，会返回第二个参数所赋的值。

7.小结

以上是本人在使用python刷题的时候作的一些总结，若有不到位的地方请指出。

本文旨在为自己做一个文档，同时也为大家提供一些便利。

关注我的公众号【程序小员】，收货一大波福利知识。

我是落阳，谢谢你的到访。