本期话题是 Python 的原生类型和内置函数在算法实现中的一些技巧，首先从最常见的 Python 原生类型开始。
int类型有两个内置的方法bit_count与bit_length，分别用来获取整数二进制表达的1的个数和二进制位数，在很多场景下都很实用。
- n = 9
- assert n.bit_count() == 2
- assert n.bit_length() == 4
float的as_integer_ratio方法可以获得浮点数的最简分数表达。
- f = 6.125
- assert f.as_integer_ratio() == (49, 8)
利用f-string可以轻松获得浮点数的指定小数位数的字符串表达。
assert f"{1/3:.4f}" == "0.3333"
'运行list的pop方法接收整数参数 n， 返回并删除列表中的第 n 个元素（O(n)的时间复杂度，效率不高）。
- arr = [1, 2, 3]
- assert arr.pop(1) == 2
- assert arr == [1, 3]
算法实现中经常需要用到栈结构，Python 的 list 类型原生拥有栈的所有功能，也可以简单的封装一下，定义自己的 Stack 类型。
- class Stack(list):
- push = list.append
- top = lambda l: l[-1]
- empty = lambda l: not l
tuple类型在算法实现中的使用频率不是很高，不过list类型是不可哈希的（不能作为字典的键），这类场景下可以将list转换为tuple后进行使用。
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}
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} # 超集判断
有大量的算法题目涉及到字符串及其处理，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 # 左侧填0
- assert "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方法，可以用指定分隔符将多个字符串合并为一个。
Python 原生提供复数类型complex，并支持常见的算术运算。
- c = complex(1, -1)
- assert c.real == 1
- assert c.imag == -1
-
- assert complex(1, 1) * complex(1, -1) == 2
本期的第二部分的主题是 Python 的内置函数，并根据函数的参数类型和返回类型将内置函数分为对象类和容器（迭代器）类。
对象类的内置函数主要涉及具体类型的对象的处理。
计算绝对值。
返回多个值（或一个可迭代对象）的最大值或最小值。
数字和 ASCII 字符的相互转换。
chr(ord("a") + 1) == "b"
同时获取整数除法运算的商和余数。
assert divmod(5, 2) == (2, 1)
获取整数的十六进制表达。
assert hex(255) == "0xff"
求幂。
assert pow(2, 3) == 8
浮点数取整（四舍六入五成双）。
- assert round(1.2) == 1
- assert round(1.6) == 2
- assert round(1.5) == 2
- assert round(2.5) == 2
容器、迭代器类的内置函数用于处理和生成各类容器对象和迭代器对象。
所有元素为真值时返回True
- assert all(x < 10 for x in [1, 2, 3])
- assert not all(x < 10 for x in [1, 2, 3, 11])
任一元素为真值时返回True
- assert any(x < 10 for x in [11, 9, 12])
- assert not any(x < 10 for x in [11, 12, 13])
获取可迭代对象的下一个元素，常用于获取收个满足条件的元素(为防止不存在符合条件的元素，可以跟一个兜底的值)。
- assert next(x for x in range(1, 10) if x % 3 == 0) == 3
- assert next(itertools.chain((x for x in [1, 2, 4, 7] if x % 3 == 0), iter([-1]))) == -1
遍历容器，返回一个迭代索引和值的生成器（一般用在 for 循环中）。
- assert dict(enumerate("abc")) == {0: "a", 1: "b", 2: "c"}
-
- for index, ch in enumerate("abc"):
- pass
将指定函数应用到容器的每一个值，返回一个生成器（而不是列表）。一般使用列表推导式替代map函数，效率更高。
使用指定函数测试容器的每一个值，过滤出函数值为真值的元素，返回一个生成器（而不是列表）。
获取可迭代的整数区间。
获取容器或可迭代对象所有元素的和
对可迭代对象的值进行排序，返回一个列表，可指定排序方式，可返回倒序列表。
- 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]
传入多个可迭代对象，按顺序将每个参数的相同索引的元素组合为一个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 的原生类型和内置函数是很强大，值得深入研究一下。