【使用 Python 实现算法】目录
本期话题是 Python 的原生类型和内置函数在算法实现中的一些技巧，首先从最常见的 Python 原生类型开始。
int
int类型有两个内置的方法bit_count与bit_length，分别用来获取整数二进制表达的1的个数和二进制位数，在很多场景下都很实用。
n = 9assert n.bit_count() == 2assert n.bit_length() == 4
复制代码
float
float的as_integer_ratio方法可以获得浮点数的最简分数表达。
f = 6.125assert f.as_integer_ratio() == (49, 8)
复制代码
利用f-string可以轻松获得浮点数的指定小数位数的字符串表达。
assert f"{1/3:.4f}" == "0.3333"
复制代码
list
list的pop方法接收整数参数 n， 返回并删除列表中的第 n 个元素（O(n)的时间复杂度，效率不高）。
arr = [1, 2, 3]assert arr.pop(1) == 2assert arr == [1, 3]
复制代码
算法实现中经常需要用到栈结构，Python 的 list 类型原生拥有栈的所有功能，也可以简单的封装一下，定义自己的 Stack 类型。
class Stack(list): push = list.append top = lambda l: l[-1] empty = lambda l: not l
复制代码
tuple
tuple类型在算法实现中的使用频率不是很高，不过list类型是不可哈希的（不能作为字典的键），这类场景下可以将list转换为tuple后进行使用。
dict
dict的fromkeys方法可以用于初始化拥有同一个默认值的字典。
counter = dict.fromkeys("abc", 0)
for ch in "abccaaa": counter[ch] += 1
assert counter == {"a": 4, "b": 1, "c": 2}
复制代码
初始化dict的另一个常用方法是使用字典推导式。
counter = {ch: count for ch, count in [("a", 1), ("b", 2), ("c", 3)]}assert counter == {"a": 1, "b": 2, "c": 3}
复制代码
set
Python 的set类型原生支持使用常见的运算符进行集合运算。
a, b = set([1, 2, 3]), set([2, 3, 4])assert a & b == {2, 3} # 交集assert a | b == {1, 2, 3, 4} # 并集assert a - b == {1} # 差集assert {2, 3} < a # 子集判断assert a > {1} # 超集判断
复制代码
str
有大量的算法题目涉及到字符串及其处理，Python 的str类型拥有大量的用途多样的内置方法，主要分为三个类型。
检查字符串类型
str.isalnum # 是否为字母或数字str.isalpha # 是否为字母str.isascii # 是否属于ASCII字符集str.isdecimal # 是否为十进制值数字str.isdigit # 是否为数字，支持其他Unicode数字，例如"①"str.isidentifier # 是否为Python关键字str.islower # 是否为小写字母str.isnumeric # 是否为数字，包括一些Unicode数字，例如"½"str.isprintable # 是否为可打印字符str.isspace # 是否为空格str.istitle # 是否为标题（一个大写字母后面跟0个及以上的小写字母）str.isupper # 是否为大写字母
复制代码
根据内容返回新的字符串
str.translate # 使用一个映射关系转换字符串assert "acbbc".translate(str.maketrans("abc", "xyz")) == "xzyyz"
str.replace # 替换子串str.upper # 转大写str.lower # 转小写
str.zfill # 左侧填0assert "abc".zfill(5) == "00abc"
str.capitalize # 首字母大写，其他字母小写assert "aBC cAA".capitalize() == "Abc caa"
str.titie # 每个单词首字母大写，其他字母小写assert "aBC cAA".title() == "Abc Caa"
str.swapcase # 大写变小写，小写变大写assert "aBC cAb".swapcase() == "Abc CaB"
复制代码
拆分为多个子串
str.split # 使用指定分隔符拆分字符串str.splitline # 按换行符拆分字符串
str.partition # 使用指定分隔符将字符串拆分为三段assert "A B C".partition(" ") == ("A", " ", "B C")
复制代码
此外还有str.join方法，可以用指定分隔符将多个字符串合并为一个。
complex
Python 原生提供复数类型complex，并支持常见的算术运算。
c = complex(1, -1)assert c.real == 1assert c.imag == -1
assert complex(1, 1) * complex(1, -1) == 2
复制代码
本期的第二部分的主题是 Python 的内置函数，并根据函数的参数类型和返回类型将内置函数分为对象类和容器（迭代器）类。
对象类
对象类的内置函数主要涉及具体类型的对象的处理。
abs
计算绝对值。
max, min
返回多个值（或一个可迭代对象）的最大值或最小值。
chr, ord
数字和 ASCII 字符的相互转换。
divmod
同时获取整数除法运算的商和余数。
assert divmod(5, 2) == (2, 1)
复制代码
hex
获取整数的十六进制表达。
assert hex(255) == "0xff"
复制代码
pow
求幂。
round
浮点数取整（四舍六入五成双）。
assert round(1.2) == 1assert round(1.6) == 2assert round(1.5) == 2assert round(2.5) == 2
复制代码
容器、迭代器类
容器、迭代器类的内置函数用于处理和生成各类容器对象和迭代器对象。
all
所有元素为真值时返回True
assert all(x < 10 for x in [1, 2, 3])assert not all(x < 10 for x in [1, 2, 3, 11])
复制代码
any
任一元素为真值时返回True
assert any(x < 10 for x in [11, 9, 12])assert not any(x < 10 for x in [11, 12, 13])
复制代码
next
获取可迭代对象的下一个元素，常用于获取收个满足条件的元素(为防止不存在符合条件的元素，可以跟一个兜底的值)。
assert next(x for x in range(1, 10) if x % 3 == 0) == 3assert next(itertools.chain((x for x in [1, 2, 4, 7] if x % 3 == 0), iter([-1]))) == -1
复制代码
enumerate
遍历容器，返回一个迭代索引和值的生成器（一般用在 for 循环中）。
assert dict(enumerate("abc")) == {0: "a", 1: "b", 2: "c"}
for index, ch in enumerate("abc"): pass
复制代码
map
将指定函数应用到容器的每一个值，返回一个生成器（而不是列表）。一般使用列表推导式替代map函数，效率更高。
filter
使用指定函数测试容器的每一个值，过滤出函数值为真值的元素，返回一个生成器（而不是列表）。
range
获取可迭代的整数区间。
sum
获取容器或可迭代对象所有元素的和
sorted
对可迭代对象的值进行排序，返回一个列表，可指定排序方式，可返回倒序列表。
assert sorted(range(10), key=lambda x: x % 3) == [0, 3, 6, 9, 1, 4, 7, 2, 5, 8]assert sorted([1, 3, 5, 2, 4], reverse=True) == [5, 4, 3, 2, 1]
复制代码
zip
传入多个可迭代对象，按顺序将每个参数的相同索引的元素组合为一个tuple对象迭代生成。
assert list(zip(range(4), "abcd")) == [(0, "a"), (1, "b"), (2, "c"), (3, "d")]
复制代码
可以使用 zip 方法进行矩阵转置。
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]assert [list(row) for row in zip(*matrix)] == [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
复制代码
总结
Python 的原生类型和内置函数是很强大，值得深入研究一下。
评论