算法学习全攻略：从入门到精通

第一章：算法入门基础

1.1 什么是算法？

算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。简单来说，算法就是解决问题的步骤和方法。

算法的五大特性：

• 有穷性：算法必须在执行有限步骤后终止

• 确定性：算法的每一步必须有明确的定义

• 可行性：算法中的操作都是可以执行的基本操作

• 输入：算法有零个或多个输入

• 输出：算法有一个或多个输出

1.2 算法复杂度分析

时间复杂度

时间复杂度描述算法运行时间随输入规模增长的变化趋势。

常见时间复杂度：

1. 常数时间 O(1)：

python

def constant_time_operation(arr): return arr[0] if arr else None # 无论arr多大，操作次数固定

1. 对数时间 O(log n)：

python

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 -1

1. 线性时间 O(n)：

python

def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1

1. 线性对数时间 O(n log n)：

python

# 归并排序、快速排序的平均时间复杂度

1. 平方时间 O(n²)：

python

def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]

1. 指数时间 O(2ⁿ)：

python

def fibonacci_recursive(n): if n <= 1: return n return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

空间复杂度

空间复杂度描述算法在执行过程中所需的存储空间。

python

# O(1) 空间复杂度 def find_max(arr): max_val = arr[0] for num in arr: if num > max_val: max_val = num return max_val # O(n) 空间复杂度 def copy_array(arr): return arr.copy() # 需要额外的n个存储空间

1.3 递归与迭代

递归示例：

python

def factorial_recursive(n): """递归计算阶乘""" if n == 0 or n == 1: return 1 return n * factorial_recursive(n - 1) def factorial_iterative(n): """迭代计算阶乘""" result = 1 for i in range(2, n + 1): result *= i return result

递归三要素：

1. 基准情况（Base Case）

2. 递归调用自身

3. 向基准情况推进

第二章：基础数据结构

2.1 数组与链表

数组（Array）

python

class DynamicArray: def __init__(self, capacity=10): self.capacity = capacity self.size = 0 self.array = [None] * capacity def add(self, value): if self.size == self.capacity: self._resize() self.array[self.size] = value self.size += 1 def _resize(self): self.capacity *= 2 new_array = [None] * self.capacity for i in range(self.size): new_array[i] = self.array[i] self.array = new_array

链表（Linked List）

python

class ListNode: def __init__(self, val=0): self.val = val self.next = None class LinkedList: def __init__(self): self.head = None def add_at_head(self, val): new_node = ListNode(val) new_node.next = self.head self.head = new_node def reverse(self): prev = None current = self.head while current: next_node = current.next current.next = prev prev = current current = next_node self.head = prev

2.2 栈与队列

栈（Stack）

python

class Stack: def __init__(self): self.stack = [] def push(self, item): self.stack.append(item) def pop(self): if not self.is_empty(): return self.stack.pop() return None def peek(self): if not self.is_empty(): return self.stack[-1] return None def is_empty(self): return len(self.stack) == 0 def size(self): return len(self.stack) # 栈的应用：括号匹配 def is_valid_parentheses(s): stack = [] mapping = {')': '(', '}': '{', ']': '['} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping.keys(): if not stack or mapping[char] != stack.pop(): return False return not stack

队列（Queue）

python

from collections import deque class Queue: def __init__(self): self.queue = deque() def enqueue(self, item): self.queue.append(item) def dequeue(self): if not self.is_empty(): return self.queue.popleft() return None def front(self): if not self.is_empty(): return self.queue[0] return None def is_empty(self): return len(self.queue) == 0 def size(self): return len(self.queue)

2.3 哈希表

python

class HashTable: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(size)] def _hash(self, key): return hash(key) % self.size def insert(self, key, value): hash_key = self._hash(key) bucket = self.table[hash_key] for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) def get(self, key): hash_key = self._hash(key) bucket = self.table[hash_key] for k, v in bucket: if k == key: return v return None def delete(self, key): hash_key = self._hash(key) bucket = self.table[hash_key] for i, (k, v) in enumerate(bucket): if k == key: del bucket[i] return True return False

第三章：排序算法

3.1 比较排序算法

冒泡排序

python

def bubble_sort(arr): n = len(arr) for i in range(n): # 最后i个元素已经排好序 for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr

选择排序

python

def selection_sort(arr): n = len(arr) for i in range(n): # 找到未排序部分的最小值 min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

插入排序

python

def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 # 将key插入到已排序序列的正确位置 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr

归并排序

python

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

快速排序

python

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 quick_sort_inplace(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: # 分区操作 pi = partition(arr, low, high) # 递归排序 quick_sort_inplace(arr, low, pi-1) quick_sort_inplace(arr, pi+1, high) def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] return i + 1

3.2 非比较排序

计数排序

python

def counting_sort(arr): if not arr: return arr # 找到最大值和最小值 max_val = max(arr) min_val = min(arr) # 创建计数数组 count_size = max_val - min_val + 1 count = [0] * count_size # 计数 for num in arr: count[num - min_val] += 1 # 累加计数 for i in range(1, count_size): count[i] += count[i-1] # 构建输出数组 output = [0] * len(arr) for num in reversed(arr): idx = count[num - min_val] - 1 output[idx] = num count[num - min_val] -= 1 return output

桶排序

python

def bucket_sort(arr, bucket_size=5): if len(arr) == 0: return arr # 确定最小值和最大值 min_val = min(arr) max_val = max(arr) # 桶的数量 bucket_count = (max_val - min_val) // bucket_size + 1 buckets = [[] for _ in range(bucket_count)] # 将数据分配到桶中 for num in arr: idx = (num - min_val) // bucket_size buckets[idx].append(num) # 对每个桶排序并合并 result = [] for bucket in buckets: result.extend(sorted(bucket)) return result

第四章：查找算法

4.1 基本查找

顺序查找

python

def sequential_search(arr, target): for i, val in enumerate(arr): if val == target: return i return -1

二分查找

python

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 -1 # 二分查找变种：查找第一个等于目标值的位置 def binary_search_first(arr, target): left, right = 0, len(arr) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: result = mid right = mid - 1 # 继续在左半部分查找 elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return result

4.2 高级查找

二叉搜索树

python

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def insert(self, val): if not self.root: self.root = TreeNode(val) else: self._insert_recursive(self.root, val) def _insert_recursive(self, node, val): if val < node.val: if not node.left: node.left = TreeNode(val) else: self._insert_recursive(node.left, val) else: if not node.right: node.right = TreeNode(val) else: self._insert_recursive(node.right, val) def search(self, val): return self._search_recursive(self.root, val) def _search_recursive(self, node, val): if not node: return False if node.val == val: return True elif val < node.val: return self._search_recursive(node.left, val) else: return self._search_recursive(node.right, val)

第五章：图算法

5.1 图的表示

python

# 邻接矩阵表示 class GraphMatrix: def __init__(self, vertices): self.vertices = vertices self.matrix = [[0] * vertices for _ in range(vertices)] def add_edge(self, u, v, weight=1): self.matrix[u][v] = weight self.matrix[v][u] = weight # 无向图 # 邻接表表示 class GraphList: def __init__(self, vertices): self.vertices = vertices self.adj_list = [[] for _ in range(vertices)] def add_edge(self, u, v, weight=1): self.adj_list[u].append((v, weight)) self.adj_list[v].append((u, weight)) # 无向图

5.2 图的遍历

深度优先搜索（DFS）

python

def dfs_iterative(graph, start): visited = set() stack = [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex, end=' ') # 将相邻节点加入栈 for neighbor in graph[vertex]: if neighbor not in visited: stack.append(neighbor) def dfs_recursive(graph, vertex, visited=None): if visited is None: visited = set() visited.add(vertex) print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited)

广度优先搜索（BFS）

python

from collections import deque def bfs(graph, start): visited = set([start]) queue = deque([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)

5.3 最短路径算法

Dijkstra算法

python

import heapq def dijkstra(graph, start): # 初始化距离 distances = {vertex: float('inf') 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]: distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances

Floyd-Warshall算法

python

def floyd_warshall(graph): # 初始化距离矩阵 n = len(graph) dist = [[float('inf')] * n for _ in range(n)] # 对角线为0 for i in range(n): dist[i][i] = 0 # 初始化已知边 for u in range(n): for v, w in graph[u]: dist[u][v] = w # 动态规划 for k in range(n): for i in range(n): for j in range(n): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist

5.4 最小生成树

Prim算法

python

import heapq def prim(graph, start): mst = [] visited = set([start]) edges = [ (weight, start, to) for to, weight in graph[start] ] 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 to_next, weight_next in graph[to]: if to_next not in visited: heapq.heappush(edges, (weight_next, to, to_next)) return mst

Kruskal算法

python

class DisjointSet: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n 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: 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 return True return False def kruskal(graph, n): # 获取所有边 edges = [] for u in range(n): for v, weight in graph[u]: edges.append((weight, u, v)) # 按权重排序 edges.sort() # 初始化并查集 dsu = DisjointSet(n) mst = [] # 构建最小生成树 for weight, u, v in edges: if dsu.union(u, v): mst.append((u, v, weight)) if len(mst) == n - 1: break return mst

第六章：动态规划

6.1 动态规划基础

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

动态规划三要素：

1. 最优子结构

2. 重叠子问题

3. 状态转移方程

6.2 经典动态规划问题

斐波那契数列

python

# 递归版本（低效） def fib_recursive(n): if n <= 1: return n return fib_recursive(n-1) + fib_recursive(n-2) # 记忆化搜索 def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n] # 动态规划 def fib_dp(n): if n <= 1: return n dp = [0] * (n + 1) dp[0], dp[1] = 0, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] # 空间优化版 def fib_optimized(n): if n <= 1: return n prev, curr = 0, 1 for _ in range(2, n + 1): prev, curr = curr, prev + curr return curr

背包问题

python

# 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] # 空间优化版 def knapsack_01_optimized(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): # 逆序遍历避免重复使用物品 for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], values[i] + dp[w - weights[i]]) return dp[capacity]

最长公共子序列

python

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]) # 重建LCS lcs = [] i, j = m, n while i > 0 and j > 0: if text1[i-1] == text2[j-1]: lcs.append(text1[i-1]) i -= 1 j -= 1 elif dp[i-1][j] > dp[i][j-1]: i -= 1 else: j -= 1 return dp[m][n], ''.join(reversed(lcs))

编辑距离

python

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]

第七章：贪心算法

7.1 贪心算法基础

贪心算法在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法的特性：

• 贪心选择性质

• 最优子结构性质

7.2 经典贪心问题

找零问题

python

def coin_change_greedy(coins, amount): coins.sort(reverse=True) result = [] for coin in coins: while amount >= coin: amount -= coin result.append(coin) return result if amount == 0 else None

活动选择问题

python

def activity_selection(activities): # 活动格式：(开始时间, 结束时间) # 按结束时间排序 activities.sort(key=lambda x: x[1]) selected = [] last_end_time = 0 for start, end in activities: if start >= last_end_time: selected.append((start, end)) last_end_time = end return selected

霍夫曼编码

python

import heapq class HuffmanNode: def __init__(self, char, freq): self.char = char self.freq = freq self.left = None self.right = None def __lt__(self, other): return self.freq < other.freq def build_huffman_tree(freq_map): heap = [] for char, freq in freq_map.items(): heapq.heappush(heap, HuffmanNode(char, freq)) while len(heap) > 1: left = heapq.heappop(heap) right = heapq.heappop(heap) merged = HuffmanNode(None, left.freq + right.freq) merged.left = left merged.right = right heapq.heappush(heap, merged) return heap[0] def generate_huffman_codes(node, code='', codes={}): if node is None: return if node.char is not None: codes[node.char] = code generate_huffman_codes(node.left, code + '0', codes) generate_huffman_codes(node.right, code + '1', codes) return codes

第八章：字符串算法

8.1 字符串匹配

KMP算法

python

def build_kmp_table(pattern): table = [0] * len(pattern) j = 0 for i in range(1, len(pattern)): while j > 0 and pattern[i] != pattern[j]: j = table[j-1] if pattern[i] == pattern[j]: j += 1 table[i] = j return table def kmp_search(text, pattern): if not pattern: return 0 table = build_kmp_table(pattern) j = 0 for i in range(len(text)): while j > 0 and text[i] != pattern[j]: j = table[j-1] if text[i] == pattern[j]: j += 1 if j == len(pattern): return i - j + 1 return -1

Boyer-Moore算法

python

def build_bad_char_table(pattern): table = {} length = len(pattern) for i in range(length): table[pattern[i]] = i return table def boyer_moore_search(text, pattern): if not pattern: return 0 bad_char = build_bad_char_table(pattern) m, n = len(pattern), len(text) s = 0 # 文本中的偏移量 while s <= n - m: j = m - 1 while j >= 0 and pattern[j] == text[s + j]: j -= 1 if j < 0: return s else: bad_char_shift = j - bad_char.get(text[s + j], -1) s += max(1, bad_char_shift) return -1

8.2 字符串处理

最长回文子串

python

def longest_palindromic_substring(s): if not s: return "" n = len(s) start, max_length = 0, 1 # 初始化DP表 dp = [[False] * n for _ in range(n)] # 单个字符都是回文 for i in range(n): dp[i][i] = True # 两个字符的情况 for i in range(n - 1): if s[i] == s[i + 1]: dp[i][i + 1] = True start = i max_length = 2 # 长度大于2的情况 for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and dp[i + 1][j - 1]: dp[i][j] = True start = i max_length = length return s[start:start + max_length] # Manacher算法（更高效） def manacher(s): # 预处理字符串 t = '#'.join('^{}$'.format(s)) n = len(t) p = [0] * n center, right = 0, 0 for i in range(1, n - 1): mirror = 2 * center - i if i < right: p[i] = min(right - i, p[mirror]) # 尝试扩展回文 while t[i + p[i] + 1] == t[i - p[i] - 1]: p[i] += 1 # 如果回文扩展到了右边，调整中心和右边界 if i + p[i] > right: center = i right = i + p[i] # 找到最长回文 max_len, center_index = max((n, i) for i, n in enumerate(p)) start = (center_index - max_len) // 2 return s[start:start + max_len]

第九章：高级数据结构

9.1 堆与优先队列

python

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 insert(self, val): self.heap.append(val) self._heapify_up(len(self.heap) - 1) def _heapify_up(self, i): while i > 0 and self.heap[i] < self.heap[self.parent(i)]: self.heap[i], self.heap[self.parent(i)] = \ self.heap[self.parent(i)], self.heap[i] i = self.parent(i) def extract_min(self): if not self.heap: return None if len(self.heap) == 1: return self.heap.pop() root = self.heap[0] self.heap[0] = self.heap.pop() self._heapify_down(0) return root def _heapify_down(self, i): smallest = i left = self.left_child(i) right = self.right_child(i) if left < len(self.heap) and self.heap[left] < self.heap[smallest]: smallest = left if right < len(self.heap) and self.heap[right] < self.heap[smallest]: smallest = right if smallest != i: self.heap[i], self.heap[smallest] = \ self.heap[smallest], self.heap[i] self._heapify_down(smallest)

9.2 树状数组

python

class FenwickTree: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def update(self, i, delta): while i <= self.n: self.tree[i] += delta i += i & -i def query(self, i): """前i个元素的和""" result = 0 while i > 0: result += self.tree[i] i -= i & -i return result def range_query(self, l, r): """区间[l, r]的和""" return self.query(r) - self.query(l - 1)

9.3 线段树

python

class SegmentTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) self._build(arr, 0, 0, self.n - 1) def _build(self, arr, node, start, end): if start == end: self.tree[node] = arr[start] else: mid = (start + end) // 2 left_child = 2 * node + 1 right_child = 2 * node + 2 self._build(arr, left_child, start, mid) self._build(arr, right_child, mid + 1, end) self.tree[node] = self.tree[left_child] + self.tree[right_child] def update(self, idx, val, node=0, start=0, end=None): if end is None: end = self.n - 1 if start == end: self.tree[node] = val else: mid = (start + end) // 2 left_child = 2 * node + 1 right_child = 2 * node + 2 if start <= idx <= mid: self.update(idx, val, left_child, start, mid) else: self.update(idx, val, right_child, mid + 1, end) self.tree[node] = self.tree[left_child] + self.tree[right_child] def query(self, l, r, node=0, start=0, end=None): if end is None: end = self.n - 1 if r < start or end < l: return 0 if l <= start and end <= r: return self.tree[node] mid = (start + end) // 2 left_child = 2 * node + 1 right_child = 2 * node + 2 left_sum = self.query(l, r, left_child, start, mid) right_sum = self.query(l, r, right_child, mid + 1, end) return left_sum + right_sum

第十章：算法设计技巧

10.1 分治法

分治法将问题分解为若干个子问题，递归地解决这些子问题，然后合并子问题的解以得到原问题的解。

分治法三步骤：

1. 分解：将原问题分解为若干个规模较小的子问题

2. 解决：递归地解决各个子问题

3. 合并：将子问题的解合并成原问题的解

python

def divide_and_conquer(problem): # 基准情况 if problem is small_enough: return solve_directly(problem) # 分解问题 subproblems = divide(problem) # 递归解决子问题 sub_solutions = [] for sub in subproblems: sub_solutions.append(divide_and_conquer(sub)) # 合并解 return combine(sub_solutions)

10.2 回溯法

回溯法采用试错的思想，尝试分步去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答时，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。

python

def backtrack(candidate): if find_solution(candidate): output(candidate) return for next_candidate in list_of_candidates: if is_valid(next_candidate): # 尝试这个候选解 place(next_candidate) backtrack(next_candidate) # 回溯 remove(next_candidate)

N皇后问题

python

def solve_n_queens(n): def is_safe(board, row, col): # 检查同一列 for i in range(row): if board[i] == col: return False # 检查左上对角线 for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): if board[i] == j: return False # 检查右上对角线 for i, j in zip(range(row-1, -1, -1), range(col+1, n)): if board[i] == j: return False return True def backtrack(row): 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[row] = -1 result = [] board = [-1] * n backtrack(0) return result

10.3 分支限界法

分支限界法以广度优先或以最小耗费优先的方式搜索问题的解空间树。

python

def branch_and_bound(problem): # 初始化优先队列 queue = PriorityQueue() queue.put((0, initial_solution)) best_solution = None best_value = float('inf') while not queue.empty(): current_bound, current_solution = queue.get() # 如果当前解的下界已经比已知最优解差，剪枝 if current_bound >= best_value: continue # 如果当前解是完整解 if is_complete(current_solution): current_value = evaluate(current_solution) if current_value < best_value: best_value = current_value best_solution = current_solution else: # 分支：生成子问题 for child in generate_children(current_solution): child_bound = lower_bound(child) if child_bound < best_value: queue.put((child_bound, child)) return best_solution

第十一章：算法优化技巧

11.1 空间换时间

python

# 使用哈希表加速查找 def two_sum(nums, target): seen = {} for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return [] # 使用前缀和优化区间查询 class PrefixSum: def __init__(self, nums): self.prefix = [0] * (len(nums) + 1) for i in range(len(nums)): self.prefix[i+1] = self.prefix[i] + nums[i] def sum_range(self, left, right): return self.prefix[right+1] - self.prefix[left]

11.2 双指针技巧

python

# 快慢指针：检测环 def has_cycle(head): if not head: return False slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False # 左右指针：两数之和（有序数组） def two_sum_sorted(numbers, target): left, right = 0, len(numbers) - 1 while left < right: current_sum = numbers[left] + numbers[right] if current_sum == target: return [left + 1, right + 1] elif current_sum < target: left += 1 else: right -= 1 return []

11.3 滑动窗口

python

def sliding_window_maximum(nums, k): from collections import deque if not nums: return [] result = [] window = deque() for i in range(len(nums)): # 移除窗口外的元素 if window and window[0] < i - k + 1: window.popleft() # 移除比当前元素小的元素 while window and nums[window[-1]] < nums[i]: window.pop() window.append(i) # 当窗口形成时，记录最大值 if i >= k - 1: result.append(nums[window[0]]) return result def longest_substring_without_repeating(s): char_index = {} left = 0 max_length = 0 for right, char in enumerate(s): # 如果字符已经在窗口中，移动左指针 if char in char_index and char_index[char] >= left: left = char_index[char] + 1 char_index[char] = right max_length = max(max_length, right - left + 1) return max_length

第十二章：实际应用与面试技巧

12.1 常见算法面试题

链表相关

python

# 反转链表 def reverse_list(head): prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev # 检测链表环的入口 def detect_cycle(head): slow = fast = head # 找到相遇点 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: return None # 没有环 # 找到环的入口 ptr1 = head ptr2 = slow while ptr1 != ptr2: ptr1 = ptr1.next ptr2 = ptr2.next return ptr1

树相关

python

# 二叉树的最近公共祖先 def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left or right # 验证二叉搜索树 def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')): if not root: return True if root.val <= min_val or root.val >= max_val: return False return (is_valid_bst(root.left, min_val, root.val) and is_valid_bst(root.right, root.val, max_val))

12.2 算法学习建议

1. 理解优先于记忆：理解算法的思想比记住代码更重要

2. 循序渐进：从简单算法开始，逐步挑战复杂算法

3. 动手实践：多写代码，多做练习题

4. 分析复杂度：养成分析时间、空间复杂度的习惯

5. 复习巩固：定期复习已学算法

6. 参加竞赛：参加算法竞赛提升解题能力

12.3 面试准备策略

1. 系统学习：全面覆盖基础数据结构和算法

2. 专题训练：针对薄弱环节专项练习

3. 模拟面试：进行限时解题训练

4. 总结反思：记录错题和解题思路

5. 沟通能力：练习解释算法思路