摘要本文系统性地汇总了 Python 中常用的算法涵盖数据结构、排序、搜索、图论、动态规划、字符串处理、数学算法等多个领域。每个算法都配有核心思想、Python 实现代码和应用场景说明旨在为开发者提供一个全面的算法参考手册。1. 数据结构基础算法1.1 数组与列表操作最大子数组和Kadane算法def max_subarray_sum(nums): max_current max_global nums[0] for i in range(1, len(nums)): max_current max(nums[i], max_current nums[i]) max_global max(max_global, max_current) return max_global 示例 nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(max_subarray_sum(nums)) # 输出: 6数组旋转def rotate_array(nums, k): n len(nums) k % n nums[:] nums[-k:] nums[:-k] 示例 arr [1, 2, 3, 4, 5, 6, 7] rotate_array(arr, 3) print(arr) # 输出: [5, 6, 7, 1, 2, 3, 4]1.2 链表算法反转链表class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_list(head): prev None current head while current: next_node current.next current.next prev prev current current next_node return prev检测链表环Floyd判圈算法def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False1.3 栈与队列括号匹配def is_valid_parentheses(s): stack [] mapping {): (, ]: [, }: {} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping: if not stack or stack[-1] ! mapping[char]: return False stack.pop() return not stack 示例 print(is_valid_parentheses(()[]{})) # True print(is_valid_parentheses(([)])) # False2. 排序算法2.1 比较排序快速排序def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) middle quick_sort(right)归并排序def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result2.2 非比较排序计数排序def counting_sort(arr): if not arr: return [] max_val max(arr) count [0] * (max_val 1) for num in arr: count[num] 1 result [] for i in range(len(count)): result.extend([i] * count[i]) return result3. 搜索算法3.1 二分查找def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -13.2 深度优先搜索DFSdef dfs(graph, start, visitedNone): if visited is None: visited set() visited.add(start) print(start, end ) for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) 示例图 graph { A: [B, C], B: [D, E], C: [F], D: [], E: [F], F: [] } dfs(graph, A) # 输出: A B D E F C3.3 广度优先搜索BFSfrom collections import deque def bfs(graph, start): visited set() queue deque([start]) visited.add(start) while queue: vertex queue.popleft() print(vertex, end ) for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) bfs(graph, A) # 输出: A B C D E F4. 图论算法4.1 最短路径Dijkstra算法import heapq def dijkstra(graph, start): distances {node: float(inf) for node in graph} distances[start] 0 pq [(0, start)] while pq: current_dist, current_node heapq.heappop(pq) if current_dist distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(pq, (distance, neighbor)) return distances/code/pre 4.2 最小生成树 Prim算法 def prim_mst(graph): import heapq mst [] visited set() start_node list(graph.keys())[0] visited.add(start_node) edges [(weight, start_node, to) for to, weight in graph[start_node].items()] heapq.heapify(edges) while edges: weight, frm, to heapq.heappop(edges) if to not in visited: visited.add(to) mst.append((frm, to, weight)) for next_to, next_weight in graph[to].items(): if next_to not in visited: heapq.heappush(edges, (next_weight, to, next_to)) return mst/code/pre 5. 动态规划 5.1 背包问题 0-1背包 def knapsack_01(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for w in range(1, capacity 1): if weights[i-1] w: dp[i][w] max(dp[i-1][w], values[i-1] dp[i-1][w-weights[i-1]]) else: dp[i][w] dp[i-1][w] return dp[n][capacity]/code/pre 5.2 最长公共子序列LCS def longest_common_subsequence(text1, text2): m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]/code/pre 6. 字符串算法 6.1 KMP模式匹配 def kmp_search(text, pattern): def build_lps(pattern): lps [0] * len(pattern) length 0 i 1 while i len(pattern): if pattern[i] pattern[length]: length 1 lps[i] length i 1 else: if length ! 0: length lps[length-1] else: lps[i] 0 i 1 return lps lps build_lps(pattern) i j 0 while i len(text): if pattern[j] text[i]: i 1 j 1 if j len(pattern): return i - j elif i len(text) and pattern[j] ! text[i]: if j ! 0: j lps[j-1] else: i 1 return -1/code/pre 6.2 字符串编辑距离 def edit_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]/code/pre 7. 数学算法 7.1 素数筛选 def sieve_of_eratosthenes(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False p 2 while p * p n: if is_prime[p]: for i in range(p * p, n 1, p): is_prime[i] False p 1 return [i for i in range(2, n 1) if is_prime[i]] 7.2 最大公约数欧几里得算法 def gcd(a, b): while b: a, b b, a % b return a def lcm(a, b): return abs(a * b) // gcd(a, b) 8. 贪心算法 8.1 活动选择问题 def activity_selection(start, finish): activities list(zip(start, finish)) activities.sort(keylambda x: x[1]) selected [activities[0]] last_finish activities[0][1] for i in range(1, len(activities)): if activities[i][0] last_finish: selected.append(activities[i]) last_finish activities[i][1] return selected/code/pre 9. 回溯算法 9.1 N皇后问题 def solve_n_queens(n): def is_safe(board, row, col): for i in range(row): if board[i] col or board[i] - i col - row or board[i] i col row: return False return True def backtrack(row, board, result): if row n: result.append(board[:]) return for col in range(n): if is_safe(board, row, col): board[row] col backtrack(row 1, board, result) board[row] -1 result [] board [-1] * n backtrack(0, board, result) return result/code/pre 10. 分治算法 10.1 最近点对问题 import math def closest_pair(points): def distance(p1, p2): return math.sqrt((p1[0]-p2[0])**2 (p1[1]-p2[1])**2) def brute_force(points): min_dist float(inf) pair None n len(points) for i in range(n): for j in range(i1, n): dist distance(points[i], points[j]) if dist min_dist: min_dist dist pair (points[i], points[j]) return min_dist, pair def closest_split_pair(px, py, delta): mid_x px[len(px)//2][0] sy [p for p in py if mid_x - delta p[0] mid_x delta] best delta best_pair None for i in range(len(sy)): for j in range(i1, min(i7, len(sy))): dist distance(sy[i], sy[j]) if dist best: best dist best_pair (sy[i], sy[j]) return best, best_pair def closest_pair_rec(px, py): if len(px) 3: return brute_force(px) mid len(px) // 2 qx px[:mid] rx px[mid:] qy [p for p in py if p[0] lt; px[mid][0]] ry [p for p in py if p[0] gt; px[mid][0]] d1, pair1 closest_pair_rec(qx, qy) d2, pair2 closest_pair_rec(rx, ry) delta min(d1, d2) d3, pair3 closest_split_pair(px, py, delta) if d3 lt; delta: return d3, pair3 elif d1 lt; d2: return d1, pair1 else: return d2, pair2 px sorted(points, keylambda p: p[0]) py sorted(points, keylambda p: p[1]) return closest_pair_rec(px, py)/code/pre 总结 本文汇总了 Python 中常用的十大类算法涵盖了从基础数据结构操作到高级图论和动态规划的完整知识体系。每个算法都提供了清晰的 Python 实现和简要说明可以作为算法学习和面试准备的参考资料。在实际应用中应根据具体问题选择合适的算法并考虑时间复杂度和空间复杂度的平衡。