【使用 Python 實現算法】目錄
最近加入了公司同事組織的刷題群，會定期參加 LeetCode 等平台的算法比賽。
作為一個資深 Pythonist，我一向是使用 Python 來實現各種算法題目的。Python 本身也提供了一些不錯的語言特性、內置函數和標准庫來更高效簡潔的編寫各類算法的代碼實現。
本系列博客是我根據個人使用 Python 工作和刷題的經驗總結的一些使用 Python 實現各類算法的一些技巧。
作為系列博客的第一篇文章，本期的主題是 Python 的語言特性。
解構賦值
交換兩個變量的值是一個很常見的場景，在 C 和 C++語言中，我們需要使用一個臨時變量。代碼會比較冗長，並且會有微小的性能開銷。
int tmp = x;
int x = y;
int y = x;
利用 Python 的解構賦值特性，我們可以使用一個賦值語句交換兩個變量的值。
x, y = y, x
在算法實現中，解構賦值的一個常見用法是一次初始化多個變量。
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), 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 的內置類型和內置函數在算法實現中的巧妙作用。
