那时难决
0%

【使用Python实现算法】02 原生类型与内置函数

Posted on Edited on In

【使用 Python 实现算法】目录

本期话题是 Python 的原生类型和内置函数在算法实现中的一些技巧，首先从最常见的 Python 原生类型开始。

int

int类型有两个内置的方法bit_count与bit_length，分别用来获取整数二进制表达的1的个数和二进制位数，在很多场景下都很实用。

1
2
3
n = 9
assert n.bit_count() == 2
assert n.bit_length() == 4

float

float的as_integer_ratio方法可以获得浮点数的最简分数表达。

1
2
f = 6.125
assert f.as_integer_ratio() == (49, 8)

利用f-string可以轻松获得浮点数的指定小数位数的字符串表达。

1
assert f"{1/3:.4f}" == "0.3333"

list

list的pop方法接收整数参数 n， 返回并删除列表中的第 n 个元素（O(n)的时间复杂度，效率不高）。

1
2
3
arr = [1, 2, 3]
assert arr.pop(1) == 2
assert arr == [1, 3]

算法实现中经常需要用到栈结构，Python 的 list 类型原生拥有栈的所有功能，也可以简单的封装一下，定义自己的 Stack 类型。

1
2
3
4
class Stack(list):
    push = list.append
    top = lambda l: l[-1]
    empty = lambda l: not l

tuple

tuple类型在算法实现中的使用频率不是很高，不过list类型是不可哈希的（不能作为字典的键），这类场景下可以将list转换为tuple后进行使用。

dict

dict的fromkeys方法可以用于初始化拥有同一个默认值的字典。

1
2
3
4
5
6
counter = dict.fromkeys("abc", 0)

for ch in "abccaaa":
    counter[ch] += 1

assert counter == {"a": 4, "b": 1, "c": 2}

初始化dict的另一个常用方法是使用字典推导式。

1
2
counter = {ch: count for ch, count in [("a", 1), ("b", 2), ("c", 3)]}
assert counter == {"a": 1, "b": 2, "c": 3}

set

Python 的set类型原生支持使用常见的运算符进行集合运算。

1
2
3
4
5
6
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类型拥有大量的用途多样的内置方法，主要分为三个类型。

检查字符串类型

1
2
3
4
5
6
7
8
9
10
11
12
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 # 是否为大写字母

根据内容返回新的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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"

拆分为多个子串

1
2
3
4
5
str.split # 使用指定分隔符拆分字符串
str.splitline # 按换行符拆分字符串

str.partition # 使用指定分隔符将字符串拆分为三段
assert "A B C".partition(" ") == ("A", " ", "B C")

此外还有str.join方法，可以用指定分隔符将多个字符串合并为一个。

complex

Python 原生提供复数类型complex，并支持常见的算术运算。

1
2
3
4
5
c = complex(1, -1)
assert c.real == 1
assert c.imag == -1

assert complex(1, 1) * complex(1, -1) == 2

本期的第二部分的主题是 Python 的内置函数，并根据函数的参数类型和返回类型将内置函数分为对象类和容器（迭代器）类。

对象类

对象类的内置函数主要涉及具体类型的对象的处理。

abs

计算绝对值。

max, min

返回多个值（或一个可迭代对象）的最大值或最小值。

chr, ord

数字和 ASCII 字符的相互转换。

1
chr(ord("a") + 1) == "b"

divmod

同时获取整数除法运算的商和余数。

1
assert divmod(5, 2) == (2, 1)

hex

获取整数的十六进制表达。

1
assert hex(255) == "0xff"

pow

求幂。

1
assert pow(2, 3) == 8

round

浮点数取整（四舍六入五成双）。

1
2
3
4
assert round(1.2) == 1
assert round(1.6) == 2
assert round(1.5) == 2
assert round(2.5) == 2

容器、迭代器类

容器、迭代器类的内置函数用于处理和生成各类容器对象和迭代器对象。

all

所有元素为真值时返回True

1
2
assert all(x < 10 for x in [1, 2, 3])
assert not all(x < 10 for x in [1, 2, 3, 11])

any

任一元素为真值时返回True

1
2
assert any(x < 10 for x in [11, 9, 12])
assert not any(x < 10 for x in [11, 12, 13])

next

获取可迭代对象的下一个元素，常用于获取收个满足条件的元素(为防止不存在符合条件的元素，可以跟一个兜底的值)。

1
2
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

enumerate

遍历容器，返回一个迭代索引和值的生成器（一般用在 for 循环中）。

1
2
3
4
assert dict(enumerate("abc")) == {0: "a", 1: "b", 2: "c"}

for index, ch in enumerate("abc"):
    pass

map

将指定函数应用到容器的每一个值，返回一个生成器（而不是列表）。
一般使用列表推导式替代map函数，效率更高。

filter

使用指定函数测试容器的每一个值，过滤出函数值为真值的元素，返回一个生成器（而不是列表）。

range

获取可迭代的整数区间。

sum

获取容器或可迭代对象所有元素的和

sorted

对可迭代对象的值进行排序，返回一个列表，可指定排序方式，可返回倒序列表。

1
2
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对象迭代生成。

1
assert list(zip(range(4), "abcd")) == [(0, "a"), (1, "b"), (2, "c"), (3, "d")]

可以使用 zip 方法进行矩阵转置。

1
2
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 的原生类型和内置函数是很强大，值得深入研究一下。

扫码加入技术交流群🖱️
QR code