【使用Python实现算法】01 语言特性

【使用 Python 实现算法】目录

最近加入了公司同事组织的刷题群，会定期参加 LeetCode 等平台的算法比赛。

作为一个资深 Pythonist，我一向是使用 Python 来实现各种算法题目的。Python 本身也提供了一些不错的语言特性、内置函数和标准库来更高效简洁的编写各类算法的代码实现。

本系列博客是我根据个人使用 Python 工作和刷题的经验总结的一些使用 Python 实现各类算法的一些技巧。

作为系列博客的第一篇文章，本期的主题是 Python 的语言特性。

解构赋值

交换两个变量的值是一个很常见的场景，在 C 和 C++语言中，我们需要使用一个临时变量。代码会比较冗长，并且会有微小的性能开销。

1
2
3

int tmp = x;
int x = y;
int y = x;

利用 Python 的解构赋值特性，我们可以使用一个赋值语句交换两个变量的值。

1	x, y = y, x

在算法实现中，解构赋值的一个常见用法是一次初始化多个变量。

1	ans, total, n = 0, 0, len(lst)

Python 的解构赋值同样可以用在 for 循环中。

1
2
3

points = [(1, 2), (2, 3), (3, 4)]
for x, y in points:
    pass

我们也可以使用一些更复杂的解构赋值语句。

(x, y), z = (1, 2), 3
assert (x, y, z) == (1, 2, 3)

first, *rest = list(range(5))
assert (first, rest) == (0, [1, 2, 3, 4])

列表推导式

使用声明式的列表推导式语法替代命令式的 for 循环，代码的可读性更强，并且有一定的性能提升（Python 解释器对列表推导式有专门的优化）。

# find first num in list nums which test(a) is True

def first(nums: list[int], test: Callable[[int], bool]) -> int:
    for num in nums:
        if test(num):
            return num


def first(nums: list[int], test: Callable[[int], bool]) -> int:
    return next(num for num in nums if test(num))

生成器

定义一个生成器函数在很多情况下可以避免维护一个可变的列表（或其他容器），使得代码更简洁。

@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None

# 普通实现的先序遍历
def preorder(root: TreeNode | None) -> list[int]:
    ans = []

    def dfs(root: TreeNode | None) -> None:
        if not root:
            return
        ans.append(root.val)
        dfs(root.left)
        dfs(root.right)

    dfs(root)

    return ans

# 生成器版本的先序遍历
def preorder(root: TreeNode | None) -> list[int]:
    def dfs(root: TreeNode | None) -> Generator[int, None, None]:
        if not root:
            return
        yield root.val
        yield from dfs(root.left)
        yield from dfs(root.right)

    return list(dfs(root))

结构化模式匹配

结构化模式匹配是 Python 3.10 的新特性，利用好这个特性可以写出更优雅的代码。

# 快速排序的一个概念性实现
def quicksort(arr: list[int]) -> list[int]:
    match arr:
        case first,:
            return [first]
        case first, second:
            return [first, second] if first <= second else [second, first]
        case first, *rest:
            return (
                quicksort([num for num in rest if num <= first])
                + [first]
                + quicksort([num for num in rest if num > first])
            )

以上是一些我认为可以有效帮助到算法实现的 Python 语言特性，合理利用的话可以为各类算法编写出更高效简洁、可读性强的 Python 代码实现。

下一篇博客将介绍一些 Python 的内置类型和内置函数在算法实现中的巧妙作用。