【自用】算法题

**算法题集**

###1. 最长公共子序列（LCS）

#### 题目描述：

给定两个字符串 `str1` 和 `str2`，找到它们的最长公共子序列。

#### 解决方案：

def lcs(str1, str2):
 m = len(str1)
 n = len(str2)

 # 创建一个2D 数组来存储每个子问题的结果 dp = [[0] * (n +1) for _ in range(m +1)]

 # 初始化第一行和第一列 for i in range(m +1):
 dp[i][0] =0 for j in range(n +1):
 dp[0][j] =0 # 填充2D 数组 for i in range(1, m +1):
 for j in range(1, n +1):
 if str1[i -1] == str2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 # 回溯找到 LCS lcs_str = []
 i, j = m, n while i >0 and j >0:
 if str1[i -1] == str2[j -1]:
 lcs_str.append(str1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 return ''.join(reversed(lcs_str))

# 测试用例str1 = "AGGTAB"
str2 = "GXTXAYB"
print("最长公共子序列:", lcs(str1, str2))

import networkx as nxdef mst(graph):
 # 使用 NetworkX 库创建一个有向图 G = nx.DiGraph()
 for u, v in graph:
 G.add_edge(u, v, weight=graph[(u, v)])

 # 使用 Prim 算法找到最小生成树 mst_tree = nx.minimum_spanning_tree(G)

 return mst_tree# 测试用例graph = {
 ('A', 'B'):1,
 ('A', 'C'):3,
 ('B', 'C'):2,
 ('B', 'D'):4,
 ('C', 'D'):5}
print("最小生成树:")
nx.draw(mst(graph), with_labels=True)

import heapqdef sp(graph, s, t):
 # 使用 Dijkstra 算法找到最短路径 distances = {node: float('inf') for node in graph}
 distances[s] =0 queue = [(0, s)]

 while queue:
 current_distance, current_node = heapq.heappop(queue)

 if current_distance > distances[current_node]:
 continue for neighbor, weight in graph[current_node].items():
 distance = current_distance + weight if distance < distances[neighbor]:
 distances[neighbor] = distance heapq.heappush(queue, (distance, neighbor))

 return distances[t]

# 测试用例graph = {
 'A': {'B':1, 'C':3},
 'B': {'C':2, 'D':4},
 'C': {'D':5}
}
print("最短路径:", sp(graph, 'A', 'D'))

import networkx as nxdef mf(graph, s, t):
 # 使用 Ford-Fulkerson 算法找到最大流 flow =0 while True:
 path = nx.shortest_path(graph, source=s, target=t)
 if not path:
 break capacity = float('inf')
 for i in range(len(path) -1):
 u, v = path[i], path[i +1]
 capacity = min(capacity, graph[u][v])

 flow += capacity for i in range(len(path) -1):
 u, v = path[i], path[i +1]
 graph[u][v] -= capacity if u != s:
 graph[v][u] += capacity return flow# 测试用例graph = {
 'A': {'B':3, 'C':2},
 'B': {'D':4},
 'C': {'D':5}
}
print("最大流:", mf(graph, 'A', 'D'))

import networkx as nxdef mm(graph):
 # 使用 Hopcroft-Karp 算法找到最大匹配 matching = {}
 for u in graph:
 for v in graph[u]:
 if v not in matching.values():
 matching[u] = v return len(matching)

# 测试用例graph = {
 'A': {'B', 'C'},
 'B': {'D'},
 'C': {'E'}
}
print("最大匹配:", mm(graph))