Python 算法常用库函数

本文介绍一些常用的 py 库函数

内置函数

1.1 abs(x)

返回一个数字的绝对值。参数可以是整数、浮点数、复数等。如果参数是一个复数，则返回它的模。

1.2 all(iterable)

如果 iterable 的所有元素均为真值（或可迭代对象为空）则返回 True 。
示例代码:

nums = [1, 2, 3, 4, 5]
# 检查是否所有元素都是偶数
print(all(x % 2 == 0 for x in nums))  # False

1.3 any(iterable)

如果 iterable 的任一元素为真值则返回 True。 如果可迭代对象为空，返回 False。
例：

nums = [1, 2, 3, 4, 5]
# 检查列表中是否包含偶数
print(any(x % 2 == 0 for x in nums))  # True

1.4 bin(x)

将一个整数转换为带前缀 “0b” 的二进制数字符串。
例:

print(bin(5)) # 0b101
print(bin(-6)) # -0b110

1.5 chr(i) 和 ord(c)

这两个函数互为逆函数。
chr(i)返回 Unicode 码位为整数i 的字符的字符串格式。
ord(c)对表示单个 Unicode 字符的字符串，返回代表它 Unicode 码点的整数。

print(chr(97))  # 'a'
print(ord('a')) # 97

1.6 divmod(a, b)

接受两个数字作为参数并返回由当对其使用整数除法时的商和余数组成的数字对。 结果与 (a // b, a % b) 相同。

a, b = divmod(10, 3)  # a = 3, b = 1

1.7 enumerate(iterable, start=0)

传入一个可迭代对象返回一个元组，里面包含一个计数值（从 start 开始，默认为 0）和通过迭代 iterable 获得的值。

nums = [100, 200, 300, 400, 500]
# [(1, 100), (2, 200), (3, 300), (4, 400), (5, 500)]
print(list(enumerate(nums, 1)))

1.8 eval(expression)

用来执行一个字符串表达式，并返回表达式的值。

s = "1 + 2 * 3 + 8 // 4"
print(eval(s))  # 9

1.9 int(x, base=10)

将一个字符串或数字转换为整数。如果第二个参数 base 给出，则 x 必须是一个字符串，表示进制数（如 2 表示二进制，8 表示八进制，10 表示十进制，16 表示十六进制）。

print(int('5'))  # 5
print(int('1010', 2))  # 10

1.10 max(iterable, *[, key, default]) 和 min(iterable, *[, key, default])

大家都知道这两个函数的作用，需要注意的是，如果传入的可迭代对象为空，会抛出 ValueError 异常。可以通过 default 参数设置默认返回值。

nums = [1, 2, 3, 4, 5]
print(max(nums))  # 5
nums2 = []
print(max(nums2))  # ValueError: max() arg is an empty sequence
print(max(nums2, default=0))  # 0

1.11 pow(base, exp, mod=None)

返回base的 exp 次幂；如果 mod 存在，则返回结果对 mod 取模。

mod = 10**9 + 7
print(pow(2, 3))  # 8
print(pow(2, 100, mod))  # 703687441

在 3.8 版本 pow 函数支持求逆元

print(pow(2, -1, mod))  # 500000004
# 等价于
inv = lambda x: pow(x, mod - 2, mod)
print(inv(2))  # 500000004

1.12 round(number[, ndigits])

返回浮点数 number 的四舍五入值，如果给出 ndigits 参数，返回值将根据 ndigits 的值四舍五入到小数点后的位数。

print(round(3.1415926))  # 3
print(round(3.1415926, 2))  # 3.14

注意：round 函数的行为可能会有一些意外，例如 round(2.675, 2) 的结果是 2.67 而不是 2.68。

1.13 sorted(iterable, *, key=None, reverse=False)

返回一个排序后的列表。key 参数用于指定一个函数，用于从每个列表元素中提取用于比较的键。reverse 参数用于指定排序顺序。

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(sorted(nums))  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
print(sorted(nums, reverse=True))  # [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

1.14 str(x)

返回一个字符串对象。如果 x 不是字符串，则返回表示 x 的字符串。

print(str(123))  # '123'

1.15 sum(iterable, start=0)

返回一个迭代器的总和。如果提供 start 参数，则会将 start 添加到总和中。

nums = [1, 2, 3, 4, 5]
print(sum(nums))  # 15
print(sum(nums, 10))  # 25

1.16 zip(*iterables)

在多个迭代器上并行迭代，从每个迭代器返回一个数据项组成元组。

nums = [1, 2, 3]
letters = ['a', 'b', 'c']
print(list(zip(nums, letters)))  # [(1, 'a'), (2, 'b'), (3, 'c')]

一个很好用的技巧是 zip 可以把矩阵的行变成列，列变成行，类似矩阵转置操作。

g = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for row in zip(*g):
  print(row)
# (1, 4, 7)
# (2, 5, 8)
# (3, 6, 9)

2. collections 容器数据类型

2.1 deque

类似列表的容器，经常当作双端队列使用. append 和 pop 在其两端的速度都很快。
其中四个常用函数：
append(x)：在右侧添加一个元素 x。
appendleft(x)：在左侧添加一个元素 x。
pop()：移除并返回最右侧的元素.
popleft()：移除并返回最左侧的元素。

q = deque([1, 2, 3, 4])
q.append(5)
print(q)  # deque([1, 2, 3, 4])
q.appendleft(0)
print(q)  # deque([0, 1, 2, 3, 4])
print(q.pop())  # 4
print(q)  # deque([0, 1, 2, 3])
print(q.popleft()) # 0
print(q)  # deque([1, 2, 3])

2.2 defaultdict

字典的子类，通过调用用户指定的工厂函数，为键提供默认值。
可以当成带默认值的字典使用。可以通过传入 int、list、set 等函数作为参数。

d = defaultdict(int)
d['a'] = 1
print(d['a'])  # 1
print(d['b'])  # 0
d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['b'].append(3)
print(d)  # defaultdict(<class 'list'>, {'a': [1, 2], 'b': [3]})
for key, value in d.items():
  print(key, value)
# a [1, 2]
# b [3]

2.3 Counter

一个计数器工具, 提供快速和方便的计数方法。可以用于计数任何可哈希对象。元素存储为字典的键而它们的计数存储为字典的值。

# 它和defaultdict(int) 类似，但是它可以支持初始化时传入一个可迭代对象
cnt = Counter([1, 2, 3])
# 其他用法和 defaultdict(int) 类似

# 但是Counter有一个好用的方法是most_common(n)方法，返回一个列表，其中包含 n 个最常见的元素及其计数。
cnt = Counter([1, 2, 3, 1, 2, 1, 1, 2, 3, 3, 3, 3])
print(cnt.most_common(2))  # [(3, 5), (1, 4)]

3. heapq 堆队列算法

3.1 heapify(x)

将 list x 转换成堆，原地，线性时间内。

3.2 heappush(heap, item)

将 item 的值加入 heap 中，保持堆的不变性。

3.3 heappop(heap)

弹出并返回 heap 的最小的元素，保持堆的不变性。

3.4 heapreplace(heap, item)

弹出并返回 heap 中最小的一项，同时推入新的 item。 堆的大小不变。

3.5 heappushpop(heap, item)

将 item 放入堆中，然后弹出并返回 heap 的最小元素。

3.6 nlargest(n, iterable, key=None) 和 nsmallest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最大/最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数

注意 [heapify] 初始化生成的堆是最小堆，如果需要最大堆，可以将元素取负值。
涉及到堆的弹出操作，需要先判断堆是否为空。否则会抛出异常。
堆的组合操作 [heappushpop] 和 [heapreplace] 比两次操作组合起来更快。
[nlargest] 和 [nsmallest] 函数适用于 n 比较小的情况，n 比较大时，推荐使用 sorted 函数。

from heapq import *
h = [5, 3, 7, 4, 1]
heapify(h)
print(h)
print(heappop(h)) # 1
heappush(h, 2)
print(h) # [2, 3, 7, 4, 5]
# 先push再pop
print(heappushpop(h, 1)) # 1
print(h) # [2, 3, 7, 4, 5]
# 先pop再push
print(heapreplace(h, 1)) # 2
a = [1, 5, 4, 3, 7, 8, 2]
print(nlargest(3, a)) # [8, 7, 5]
print(nsmallest(3, a)) # [1, 2, 3]

4. bisect 二分查找算法

4.1 bisect_left(a, x, lo=0, hi=len(a))

找到第一个大于等于 x 的元素的位置，保证 a[:pos] 都小于 x。

# 返回在 a 中可以插入 x 的位置，使得 a 插入 x 之后仍然有序。
# 如果 a 中存在 x，则返回 x 左侧的位置。
from bisect import bisect_left
a = [1, 2, 2, 2, 3, 4, 7]
print(bisect_left(a, 2))  # 1
print(bisect_left(a, 5))  # 6

4.2 bisect_right(a, x, lo=0, hi=len(a))

找到第一个大于 x 的元素的位置，保证 a[:pos] 都小于等于 x。

# 返回在 a 中可以插入 x 的位置，使得 a 插入 x 之后仍然有序。
# 如果 a 中存在 x，则返回 x 右侧的位置。
from bisect import bisect_right
a = [1, 2, 2, 2, 3, 4, 7]
print(bisect_right(a, 2))  # 4
print(bisect_right(a, 5))  # 6

4.3 insort_left(a, x, lo=0, hi=len(a)) 和 insort_right(a, x, lo=0, hi=len(a))

insort_left 将 x 插入到列表 a 中，并保持 a 有序。如果 a 中存在 x，则插入在 x 左侧。
insort_right 将 x 插入到列表 a 中，并保持 a 有序。如果 a 中存在 x，则插入在 x 右侧。

注意：虽然 insort 相关函数可以二分查找并直接插入元素到指定位置。但是时间复杂度为 O(n)。个人感觉使用场景不多