关于python:python算法常用技巧与内置库

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})

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

个别状况下创立的字典 dict 是不含有默认值的，即若是字典中不蕴含 a 这个 key，调用 dct{a}的话就会报错。

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

例如在用字典示意图中一个节点的相连节点的时候，咱们心愿将这个节点作为一个 key，而后与它相连的节点组成一个列表作为它的 value，这个时候咱们就能够应用 defaultdict(list)来创立一个默认值为列表的字典。

# list 的默认值为空列表
list_dict = collections.defaultdict(list)
# int 的默认值为 0
int_dict = collections.defaultdict(int)

print(list_dict['a'])
print(int_dict['a'])

# 输入：[]
# 输入：0

3.4 小结

collection 中常被用来写算法和数据结构的就是这几个，其它比方排序字典和命名元组很少会用上。

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 -1
    if x<y:
        # 返回 1 代表须要排在前面
        return 1
    return 0


lst = [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 permutations
print(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 combinations
print(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 刷题的时候作的一些总结，若有不到位的中央请指出。

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

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

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