详解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:
	# Code
	pass

# 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)
# 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'] = 0
print(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': 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})

详解python算法常用技巧与内置库

扫一扫手机访问