【使用 Python 实现算法】目录
最近加入了公司同事组织的刷题群，会定期参加 LeetCode 等平台的算法比赛。
作为一个资深 Pythonist，我一向是使用 Python 来实现各种算法题目的。Python 本身也提供了一些不错的语言特性、内置函数和标准库来更高效简洁的编写各类算法的代码实现。
本系列博客是我根据个人使用 Python 工作和刷题的经验总结的一些使用 Python 实现各类算法的一些技巧。
作为系列博客的第一篇文章，本期的主题是 Python 的语言特性。
解构赋值
交换两个变量的值是一个很常见的场景，在 C 和 C++语言中，我们需要使用一个临时变量。代码会比较冗长，并且会有微小的性能开销。
int tmp = x;int x = y;int y = x;
复制代码
利用 Python 的解构赋值特性，我们可以使用一个赋值语句交换两个变量的值。
在算法实现中，解构赋值的一个常见用法是一次初始化多个变量。
ans, total, n = 0, 0, len(lst)
复制代码
Python 的解构赋值同样可以用在 for 循环中。
points = [(1, 2), (2, 3), (3, 4)]for x, y in points: pass
复制代码
我们也可以使用一些更复杂的解构赋值语句。
(x, y), z = (1, 2), 3assert (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))
复制代码
生成器
定义一个生成器函数在很多情况下可以避免维护一个可变的列表（或其他容器），使得代码更简洁。
@dataclassclass 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 的内置类型和内置函数在算法实现中的巧妙作用。
评论