数据结构与算法竞赛培训课程从入门到精通系统学习编程核心思想与技巧深入剖析经典算法与数据结构应用通过大量实战训练提升竞赛解题能力与思维水平

引言

数据结构与算法是计算机科学的核心基础，也是各类编程竞赛中的关键考点。无论是ACM-ICPC、Codeforces、LeetCode等平台上的竞赛，还是各大公司的技术面试，扎实的数据结构与算法知识都是必不可少的。本文旨在提供一个从入门到精通的系统学习路径，帮助读者深入理解编程核心思想与技巧，掌握经典算法与数据结构的应用，并通过大量实战训练提升竞赛解题能力与思维水平。

入门基础

基本数据结构

数组与链表

数组是最基本的数据结构，它是一块连续的内存空间，通过索引可以在O(1)时间内访问元素。链表则是由节点组成，每个节点包含数据和指向下一个节点的指针，插入和删除操作的时间复杂度为O(1)，但访问元素需要O(n)时间。

数组示例代码：

# Python中的数组实现 arr = [1, 2, 3, 4, 5] # 访问元素 - O(1) print(arr[0]) # 输出: 1 # 修改元素 - O(1) arr[0] = 10 print(arr) # 输出: [10, 2, 3, 4, 5] # 在末尾添加元素 - 平均O(1) arr.append(6) print(arr) # 输出: [10, 2, 3, 4, 5, 6] # 在中间插入元素 - O(n) arr.insert(1, 20) print(arr) # 输出: [10, 20, 2, 3, 4, 5, 6]

链表示例代码：

# Python中的链表实现 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") # 使用链表 ll = LinkedList() ll.append(1) ll.append(2) ll.append(3) ll.print_list() # 输出: 1 -> 2 -> 3 -> None

栈与队列

栈是一种后进先出(LIFO)的数据结构，主要操作包括push(入栈)和pop(出栈)。队列是一种先进先出(FIFO)的数据结构，主要操作包括enqueue(入队)和dequeue(出队)。

栈示例代码：

# Python中的栈实现 class Stack: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() return None def peek(self): if not self.is_empty(): return self.items[-1] return None def size(self): return len(self.items) # 使用栈 s = Stack() s.push(1) s.push(2) s.push(3) print(s.pop()) # 输出: 3 print(s.pop()) # 输出: 2 print(s.peek()) # 输出: 1

队列示例代码：

# Python中的队列实现 from collections import deque class Queue: def __init__(self): self.items = deque() def is_empty(self): return len(self.items) == 0 def enqueue(self, item): self.items.append(item) def dequeue(self): if not self.is_empty(): return self.items.popleft() return None def front(self): if not self.is_empty(): return self.items[0] return None def size(self): return len(self.items) # 使用队列 q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.dequeue()) # 输出: 1 print(q.dequeue()) # 输出: 2 print(q.front()) # 输出: 3

基本算法

排序算法

排序是算法竞赛中的基础操作，常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

快速排序示例代码：

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) # 使用快速排序 arr = [3, 6, 8, 10, 1, 2, 1] sorted_arr = quick_sort(arr) print(sorted_arr) # 输出: [1, 1, 2, 3, 6, 8, 10]

归并排序示例代码：

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 result # 使用归并排序 arr = [12, 11, 13, 5, 6, 7] sorted_arr = merge_sort(arr) print(sorted_arr) # 输出: [5, 6, 7, 11, 12, 13]

搜索算法

搜索算法用于在数据结构中查找特定元素，常见的搜索算法包括线性搜索、二分搜索等。

二分搜索示例代码：

def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 未找到 # 使用二分搜索 arr = [1, 3, 5, 7, 9, 11, 13, 15] target = 7 result = binary_search(arr, target) print(f"元素 {target} 的索引是 {result}") # 输出: 元素 7 的索引是 3

进阶技巧

递归与分治

递归是一种解决问题的方法，它将问题分解为更小的子问题，直到子问题可以直接解决。分治策略则是将问题分解为独立的子问题，解决子问题后合并结果。

递归示例代码：

# 计算阶乘的递归实现 def factorial(n): if n == 0 or n == 1: return 1 return n * factorial(n - 1) # 使用阶乘函数 print(factorial(5)) # 输出: 120

分治示例代码：

# 使用分治策略找数组中的最大值 def find_max(arr, left, right): # 基本情况：只有一个元素 if left == right: return arr[left] # 分割数组 mid = (left + right) // 2 # 递归查找左右两半的最大值 left_max = find_max(arr, left, mid) right_max = find_max(arr, mid + 1, right) # 返回较大的值 return max(left_max, right_max) # 使用分治找最大值 arr = [3, 7, 2, 9, 5, 1, 8] max_val = find_max(arr, 0, len(arr) - 1) print(f"数组中的最大值是 {max_val}") # 输出: 数组中的最大值是 9

贪心算法

贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。贪心算法不一定能得到全局最优解，但在某些问题上是有效的。

活动选择问题示例代码：

def activity_selection(start, finish): n = len(start) # 按照结束时间排序 activities = sorted(zip(start, finish), key=lambda x: x[1]) selected = [0] # 选择第一个活动 for i in range(1, n): # 如果当前活动的开始时间大于等于上一个选中活动的结束时间 if activities[i][0] >= activities[selected[-1]][1]: selected.append(i) return selected # 使用贪心算法解决活动选择问题 start = [1, 3, 0, 5, 8, 5] finish = [2, 4, 6, 7, 9, 9] selected = activity_selection(start, finish) print("选中的活动索引:", selected) # 输出: 选中的活动索引: [0, 1, 3, 4]

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它通常用于优化问题，具有重叠子问题和最优子结构的特性。

斐波那契数列的动态规划实现：

def fibonacci(n): if n <= 1: return n # 创建一个数组来存储斐波那契数 fib = [0] * (n + 1) fib[0] = 0 fib[1] = 1 for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] return fib[n] # 使用动态规划计算斐波那契数 print(fibonacci(10)) # 输出: 55

背包问题示例代码：

def knapsack(weights, values, capacity): n = len(weights) # 创建一个二维数组来存储子问题的解 dp = [[0 for _ in range(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(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]) else: # 当前物品不能放入 dp[i][w] = dp[i - 1][w] return dp[n][capacity] # 使用动态规划解决背包问题 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 5 max_value = knapsack(weights, values, capacity) print(f"背包能装的最大价值是 {max_value}") # 输出: 背包能装的最大价值是 7

经典算法与数据结构剖析

图算法

图是由顶点和边组成的数据结构，可以用来表示各种关系。常见的图算法包括深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法等。

深度优先搜索(DFS)示例代码：

def dfs(graph, start, visited=None): 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) # 使用DFS遍历图 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print("DFS遍历结果:") dfs(graph, 'A') # 输出: A B D E F C

广度优先搜索(BFS)示例代码：

from 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': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print("BFS遍历结果:") bfs(graph, 'A') # 输出: A B C D E F

Dijkstra最短路径算法示例代码：

import heapq def dijkstra(graph, start): # 初始化距离字典，所有顶点的距离设为无穷大 distances = {vertex: float('infinity') for vertex in graph} distances[start] = 0 # 创建优先队列 priority_queue = [(0, start)] while priority_queue: current_distance, current_vertex = heapq.heappop(priority_queue) # 如果当前距离大于已知距离，跳过 if current_distance > distances[current_vertex]: continue # 检查所有邻居 for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight # 如果找到更短的路径，更新距离 if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances # 使用Dijkstra算法找最短路径 graph = { 'A': {'B': 5, 'C': 3}, 'B': {'A': 5, 'C': 2, 'D': 1}, 'C': {'A': 3, 'B': 2, 'D': 4, 'E': 6}, 'D': {'B': 1, 'C': 4, 'E': 8}, 'E': {'C': 6, 'D': 8} } start_vertex = 'A' distances = dijkstra(graph, start_vertex) print(f"从顶点 {start_vertex} 到各顶点的最短距离:") for vertex, distance in distances.items(): print(f"{vertex}: {distance}")

树结构

树是一种层次化的数据结构，由节点和边组成，没有环路。常见的树结构包括二叉树、二叉搜索树、AVL树、红黑树等。

二叉树示例代码：

class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = TreeNode(value) else: self._insert_recursive(self.root, value) def _insert_recursive(self, node, value): if value < node.value: if node.left is None: node.left = TreeNode(value) else: self._insert_recursive(node.left, value) else: if node.right is None: node.right = TreeNode(value) else: self._insert_recursive(node.right, value) def inorder_traversal(self): result = [] self._inorder_recursive(self.root, result) return result def _inorder_recursive(self, node, result): if node: self._inorder_recursive(node.left, result) result.append(node.value) self._inorder_recursive(node.right, result) # 使用二叉树 bt = BinaryTree() bt.insert(5) bt.insert(3) bt.insert(7) bt.insert(2) bt.insert(4) bt.insert(6) bt.insert(8) print("中序遍历结果:", bt.inorder_traversal()) # 输出: 中序遍历结果: [2, 3, 4, 5, 6, 7, 8]

二叉搜索树示例代码：

class BSTNode: def __init__(self, key): self.key = key self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def insert(self, key): if self.root is None: self.root = BSTNode(key) else: self._insert_recursive(self.root, key) def _insert_recursive(self, node, key): if key < node.key: if node.left is None: node.left = BSTNode(key) else: self._insert_recursive(node.left, key) elif key > node.key: if node.right is None: node.right = BSTNode(key) else: self._insert_recursive(node.right, key) # 如果key等于node.key，不插入（假设不允许重复） def search(self, key): return self._search_recursive(self.root, key) def _search_recursive(self, node, key): if node is None or node.key == key: return node if key < node.key: return self._search_recursive(node.left, key) return self._search_recursive(node.right, key) def delete(self, key): self.root = self._delete_recursive(self.root, key) def _delete_recursive(self, node, key): if node is None: return node if key < node.key: node.left = self._delete_recursive(node.left, key) elif key > node.key: node.right = self._delete_recursive(node.right, key) else: # 找到要删除的节点 # 情况1：节点只有一个子节点或没有子节点 if node.left is None: return node.right elif node.right is None: return node.left # 情况2：节点有两个子节点 # 找到右子树中的最小节点 temp = self._find_min(node.right) node.key = temp.key node.right = self._delete_recursive(node.right, temp.key) return node def _find_min(self, node): current = node while current.left is not None: current = current.left return current def inorder_traversal(self): result = [] self._inorder_recursive(self.root, result) return result def _inorder_recursive(self, node, result): if node: self._inorder_recursive(node.left, result) result.append(node.key) self._inorder_recursive(node.right, result) # 使用二叉搜索树 bst = BinarySearchTree() bst.insert(50) bst.insert(30) bst.insert(70) bst.insert(20) bst.insert(40) bst.insert(60) bst.insert(80) print("中序遍历结果:", bst.inorder_traversal()) # 输出: 中序遍历结果: [20, 30, 40, 50, 60, 70, 80] # 搜索节点 result = bst.search(40) if result: print(f"找到节点: {result.key}") # 输出: 找到节点: 40 else: print("未找到节点") # 删除节点 bst.delete(30) print("删除30后的中序遍历结果:", bst.inorder_traversal()) # 输出: 删除30后的中序遍历结果: [20, 40, 50, 60, 70, 80]

高级数据结构

堆

堆是一种特殊的树形数据结构，常用于实现优先队列。堆分为最大堆和最小堆，在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。

最小堆示例代码：

class MinHeap: def __init__(self): self.heap = [] def parent(self, i): return (i - 1) // 2 def left_child(self, i): return 2 * i + 1 def right_child(self, i): return 2 * i + 2 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] def insert(self, key): self.heap.append(key) self._heapify_up(len(self.heap) - 1) def _heapify_up(self, i): while i > 0 and self.heap[self.parent(i)] > self.heap[i]: self.swap(i, self.parent(i)) i = self.parent(i) def extract_min(self): if len(self.heap) == 0: return None min_val = self.heap[0] self.heap[0] = self.heap[-1] self.heap.pop() self._heapify_down(0) return min_val def _heapify_down(self, i): min_index = i left = self.left_child(i) right = self.right_child(i) if left < len(self.heap) and self.heap[left] < self.heap[min_index]: min_index = left if right < len(self.heap) and self.heap[right] < self.heap[min_index]: min_index = right if min_index != i: self.swap(i, min_index) self._heapify_down(min_index) def get_min(self): if len(self.heap) == 0: return None return self.heap[0] def size(self): return len(self.heap) # 使用最小堆 heap = MinHeap() heap.insert(5) heap.insert(3) heap.insert(7) heap.insert(1) heap.insert(8) print("最小值:", heap.get_min()) # 输出: 最小值: 1 print("提取最小值:", heap.extract_min()) # 输出: 提取最小值: 1 print("新的最小值:", heap.get_min()) # 输出: 新的最小值: 3

哈希表

哈希表是一种根据键(key)直接访问内存存储位置的数据结构，它通过一个哈希函数将键映射到表中的一个位置，以加快查找速度。

哈希表示例代码：

class HashTable: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(size)] # 使用链地址法处理冲突 def _hash_function(self, key): return hash(key) % self.size def insert(self, key, value): index = self._hash_function(key) bucket = self.table[index] # 检查键是否已存在 for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) # 更新值 return # 键不存在，添加新键值对 bucket.append((key, value)) def get(self, key): index = self._hash_function(key) bucket = self.table[index] for k, v in bucket: if k == key: return v return None # 键不存在 def remove(self, key): index = self._hash_function(key) bucket = self.table[index] for i, (k, v) in enumerate(bucket): if k == key: bucket.pop(i) return True return False # 键不存在 def __str__(self): result = [] for i, bucket in enumerate(self.table): if bucket: result.append(f"Bucket {i}: {bucket}") return "n".join(result) # 使用哈希表 ht = HashTable() ht.insert("apple", 5) ht.insert("banana", 7) ht.insert("orange", 3) ht.insert("grape", 8) print("哈希表内容:") print(ht) print() print("获取 'apple' 的值:", ht.get("apple")) # 输出: 获取 'apple' 的值: 5 print("获取 'pear' 的值:", ht.get("pear")) # 输出: 获取 'pear' 的值: None ht.remove("banana") print("删除 'banana' 后的哈希表内容:") print(ht)

并查集

并查集是一种用于处理元素分组的数据结构，支持两种操作：查找元素所属的组和合并两个组。

并查集示例代码：

class UnionFind: def __init__(self, size): self.parent = list(range(size)) # 每个元素的父节点初始化为自己 self.rank = [0] * size # 用于优化合并操作 def find(self, x): # 路径压缩 if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return # 已经在同一组 # 按秩合并 if self.rank[root_x] < self.rank[root_y]: self.parent[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: self.parent[root_y] = root_x self.rank[root_x] += 1 def connected(self, x, y): return self.find(x) == self.find(y) # 使用并查集 uf = UnionFind(10) uf.union(1, 2) uf.union(3, 4) uf.union(2, 3) print("1和4是否连接:", uf.connected(1, 4)) # 输出: 1和4是否连接: True print("1和5是否连接:", uf.connected(1, 5)) # 输出: 1和5是否连接: False

竞赛策略与思维训练

解题思路与方法

问题分析

在算法竞赛中，正确理解问题是解决问题的第一步。需要仔细阅读题目，明确输入输出格式、数据范围、时间限制和空间限制等关键信息。

算法选择

根据问题的特点选择合适的算法。例如，对于查找问题，可以考虑二分查找；对于最优化问题，可以考虑动态规划或贪心算法；对于图论问题，可以考虑DFS、BFS或最短路径算法等。

复杂度分析

分析算法的时间复杂度和空间复杂度，确保算法能在给定的时间和空间限制内运行。常见的时间复杂度包括O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2^n)等。

常见竞赛题型与解法

排序与查找

排序与查找是算法竞赛中的基础题型，常见的变种包括第K大元素、查找区间、合并区间等。

查找区间示例代码：

def search_range(nums, target): # 查找第一个大于等于target的位置 def find_first(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] >= target: right = mid - 1 else: left = mid + 1 return left # 查找第一个大于target的位置 def find_last(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] > target: right = mid - 1 else: left = mid + 1 return left first = find_first(nums, target) last = find_last(nums, target) - 1 if first <= last and last < len(nums) and nums[first] == target and nums[last] == target: return [first, last] else: return [-1, -1] # 使用查找区间函数 nums = [5, 7, 7, 8, 8, 10] target = 8 result = search_range(nums, target) print(f"目标值 {target} 的起始和结束位置是 {result}") # 输出: 目标值 8 的起始和结束位置是 [3, 4]

动态规划问题

动态规划是算法竞赛中的常见题型，包括背包问题、最长公共子序列、最长递增子序列、编辑距离等。

最长递增子序列示例代码：

def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) # dp[i]表示以nums[i]结尾的最长递增子序列的长度 for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # 使用最长递增子序列函数 nums = [10, 9, 2, 5, 3, 7, 101, 18] result = length_of_lis(nums) print(f"最长递增子序列的长度是 {result}") # 输出: 最长递增子序列的长度是 4

图论问题

图论问题包括最短路径、最小生成树、拓扑排序、强连通分量等。

拓扑排序示例代码：

from collections import deque def topological_sort(num_vertices, edges): # 创建邻接表和入度数组 adj_list = [[] for _ in range(num_vertices)] in_degree = [0] * num_vertices # 构建邻接表和入度数组 for u, v in edges: adj_list[u].append(v) in_degree[v] += 1 # 初始化队列，将所有入度为0的顶点加入队列 queue = deque() for i in range(num_vertices): if in_degree[i] == 0: queue.append(i) result = [] while queue: vertex = queue.popleft() result.append(vertex) # 更新相邻顶点的入度 for neighbor in adj_list[vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # 如果结果中顶点数不等于图中顶点数，说明有环 if len(result) != num_vertices: return None return result # 使用拓扑排序函数 num_vertices = 6 edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)] result = topological_sort(num_vertices, edges) print("拓扑排序结果:", result) # 输出: 拓扑排序结果: [5, 4, 2, 0, 3, 1]

竞赛技巧与注意事项

代码优化

在算法竞赛中，代码优化非常重要。常见的优化技巧包括：

使用适当的数据结构和算法
避免不必要的计算和内存分配
使用位运算代替算术运算
使用快速输入输出方法

快速输入输出示例代码：

import sys def fast_input(): return sys.stdin.readline() def fast_output(s): sys.stdout.write(str(s) + "n") # 使用快速输入输出 n = int(fast_input()) arr = list(map(int, fast_input().split())) fast_output(sum(arr))

调试技巧

调试是解决编程问题的重要环节。常见的调试技巧包括：

打印中间结果
使用断点调试
边界测试
对比正确答案

打印中间结果示例代码：

def debug_print(*args, **kwargs): print(*args, **kwargs, file=sys.stderr) # 使用调试打印 def binary_search_debug(arr, target): left, right = 0, len(arr) - 1 debug_print(f"开始二分查找，目标值: {target}") while left <= right: mid = (left + right) // 2 debug_print(f"当前范围: [{left}, {right}], 中间位置: {mid}, 中间值: {arr[mid]}") if arr[mid] == target: debug_print(f"找到目标值 {target} 在位置 {mid}") return mid elif arr[mid] < target: left = mid + 1 debug_print(f"目标值大于中间值，调整左边界为 {left}") else: right = mid - 1 debug_print(f"目标值小于中间值，调整右边界为 {right}") debug_print(f"未找到目标值 {target}") return -1 # 使用带调试的二分查找 arr = [1, 3, 5, 7, 9, 11, 13, 15] target = 7 result = binary_search_debug(arr, target)

实战训练

入门级题目

两数之和

问题描述： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

示例代码：

def two_sum(nums, target): # 创建一个字典来存储数字及其索引 num_dict = {} for i, num in enumerate(nums): complement = target - num if complement in num_dict: return [num_dict[complement], i] num_dict[num] = i return [] # 没有找到解 # 使用两数之和函数 nums = [2, 7, 11, 15] target = 9 result = two_sum(nums, target) print(f"两数之和的索引是 {result}") # 输出: 两数之和的索引是 [0, 1]

反转链表

问题描述： 反转一个单链表。

示例代码：

class ListNode: def __init__(self, val=0, next=None): 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 # 移动prev到当前节点 current = next_node # 移动current到下一个节点 return prev # 新的头节点是prev # 创建链表: 1 -> 2 -> 3 -> 4 -> 5 head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4) head.next.next.next.next = ListNode(5) # 反转链表 new_head = reverse_list(head) # 打印反转后的链表 current = new_head while current: print(current.val, end=" -> ") current = current.next print("None") # 输出: 5 -> 4 -> 3 -> 2 -> 1 -> None

进阶级题目

最长有效括号

问题描述： 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例代码：

def longest_valid_parentheses(s): stack = [-1] # 初始化栈，放入-1作为起始位置 max_length = 0 for i in range(len(s)): if s[i] == '(': stack.append(i) else: stack.pop() # 弹出栈顶元素 if not stack: stack.append(i) # 如果栈为空，将当前索引压入栈中 else: # 计算当前有效括号子串的长度 current_length = i - stack[-1] max_length = max(max_length, current_length) return max_length # 使用最长有效括号函数 s = "(()())" result = longest_valid_parentheses(s) print(f"最长有效括号子串的长度是 {result}") # 输出: 最长有效括号子串的长度是 6

最大子数组和

问题描述： 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例代码：

def max_subarray(nums): current_sum = max_sum = nums[0] for num in nums[1:]: # 要么将当前数字加到当前子数组中，要么开始一个新的子数组 current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum # 使用最大子数组和函数 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] result = max_subarray(nums) print(f"最大子数组和是 {result}") # 输出: 最大子数组和是 6

高级题目

编辑距离

问题描述： 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作次数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

示例代码：

def min_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 # 将word1的前i个字符转换为空字符串需要i次删除操作 for j in range(n + 1): dp[0][j] = j # 将空字符串转换为word2的前j个字符需要j次插入操作 # 填充dp数组 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: # 取插入、删除、替换三种操作的最小值，并加1 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 return dp[m][n] # 使用编辑距离函数 word1 = "horse" word2 = "ros" result = min_distance(word1, word2) print(f"将 '{word1}' 转换为 '{word2}' 的最小编辑距离是 {result}") # 输出: 将 'horse' 转换为 'ros' 的最小编辑距离是 3

最小路径和

问题描述： 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

示例代码：

def min_path_sum(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) # 创建一个二维数组来存储子问题的解 dp = [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] # 填充dp数组 for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] return dp[m - 1][n - 1] # 使用最小路径和函数 grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] result = min_path_sum(grid) print(f"最小路径和是 {result}") # 输出: 最小路径和是 7

竞赛模拟题

跳跃游戏 II

问题描述： 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例代码：

def jump(nums): if len(nums) <= 1: return 0 jumps = 0 current_end = 0 farthest = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == current_end: jumps += 1 current_end = farthest if current_end >= len(nums) - 1: break return jumps # 使用跳跃游戏函数 nums = [2, 3, 1, 1, 4] result = jump(nums) print(f"到达数组最后一个位置的最少跳跃次数是 {result}") # 输出: 到达数组最后一个位置的最少跳跃次数是 2

接雨水

问题描述： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例代码：

def trap(height): if not height: return 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] water = 0 while left < right: if left_max < right_max: left += 1 left_max = max(left_max, height[left]) water += left_max - height[left] else: right -= 1 right_max = max(right_max, height[right]) water += right_max - height[right] return water # 使用接雨水函数 height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] result = trap(height) print(f"能接的雨水量是 {result}") # 输出: 能接的雨水量是 6