数据结构和算法
数据结构
1. 栈（Stack）
栈是一种后进先出（LIFO, Last In First Out）的数据结构。在 Python 中，可以使用列表（list）实现栈。
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)
# 使用示例
s = Stack()
s.push(1)
s.push(2)
print(s.pop()) # 输出 2
print(s.peek()) # 输出 1
2. 队列（Queue）
队列是一种先进先出（FIFO, First In First Out）的数据结构。在 Python 中，可以使用 collections.deque 实现队列。
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 is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# 使用示例
q = Queue()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue()) # 输出 1
print(q.dequeue()) # 输出 2
3. 链表（Linked List）
链表是一种线性数据结构，其中每个元素都是一个节点，节点包含数据和指向下一个节点的引用。以下是单链表的 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.print_list() # 输出 1 -> 2 -> None
4. 二叉树（Binary Tree）
二叉树是一种每个节点最多有两个子节点的数据结构，通常用于实现搜索树。以下是二叉树的基本 Python 实现：
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = TreeNode(root)
def inorder_traversal(self, start, traversal):
if start:
traversal = self.inorder_traversal(start.left, traversal)
traversal += (str(start.data) + " ")
traversal = self.inorder_traversal(start.right, traversal)
return traversal
# 使用示例
bt = BinaryTree(1)
bt.root.left = TreeNode(2)
bt.root.right = TreeNode(3)
bt.root.left.left = TreeNode(4)
bt.root.left.right = TreeNode(5)
print(bt.inorder_traversal(bt.root, "")) # 输出 4 2 5 1 3
5. 图（Graph）
图是一种由顶点和边组成的复杂数据结构，适用于表示网络关系。图可以用邻接表或邻接矩阵来表示。以下是使用字典实现的图结构：
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
print(vertex, end=" ")
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# 使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
g.bfs(2) # 输出 2 0 3 1
算法
一、 排序算法
1.1 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它重复遍历列表，将相邻的元素两两比较并交换顺序，直到整个列表有序。最坏情况下是 O(n^2)
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]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)
1.2 快速排序（Quick Sort）
快速排序是一种基于分治思想的高效排序算法。它选择一个“基准”，将列表分为两个子列表，然后递归地排序两个子列表。时间复杂度: 最坏情况下是 O(n^2)，但平均情况下是 O(n \log n)。
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 = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
1.3 归并排序（Merge Sort）
归并排序也是基于分治法的排序算法。它将数组分成两半，分别排序，然后合并两个有序数组。时间复杂度: O(n \log n)。
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 = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)
1.4 选择排序（Selection Sor
选择排序每次从未排序部分选择最小的元素，并将其放到已排序部分的末尾。时间复杂度: 最坏情况下是 O(n^2)。
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]
# 使用示例
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:", arr)
1.5 插入排序（Insertion Sort）
插入排序是一种类似于我们打扑克牌时整理手牌的排序方法。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 时间复杂度: 最坏情况下是 O(n^2)。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# 使用示例
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("排序后的数组:", arr)
二、查找算法
2.1 线性查找（Linear Search）
线性查找是最简单的查找算法，它逐一检查列表中的每个元素，直到找到目标值。
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = [64, 34, 25, 12, 22, 11, 90]
x = 22
result = linear_search(arr, x)
print("Element found at index:", result)
2.2 二分查找（Binary Search）
二分查找是一种高效的查找算法，适用于已排序的列表。它通过反复将搜索范围减半来快速查找目标值。
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
arr = [11, 12, 22, 25, 34, 64, 90]
x = 22
result = binary_search(arr, x)
print("Element found at index:", result)
2.3 哈希查找（Hash Search）
哈希查找利用哈希表的特点来实现快速查找。哈希表根据键直接访问数据，通常查找时间为常数级别。时间复杂度: 平均情况下是 O(1)，但最坏情况下可能退化为 O(n)（当所有元素的哈希值都冲突时）。
def hash_search(arr, target):
hash_table = {}
for i in range(len(arr)):
hash_table[arr[i]] = i
return hash_table.get(target, -1)
# 使用示例
arr = [1, 3, 5, 7, 9]
target = 7
result = hash_search(arr, target)
print("元素 {} 在数组中的索引为: {}".format(target, result)) # 输出 3
2.4 深度优先搜索（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)
# 使用示例
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A') # 输出 A B D E F C
BFS实现：
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=" ")
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
# 使用示例
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A') # 输出 A B C D E F
三、递归算法
3.1 斐波那契数列（Fibonacci Sequence
递归算法通常用于解决分解为更小相同子问题的情况。斐波那契数列就是一个经典例子
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
n = 10
print("Fibonacci sequence:")
for i in range(n):
print(fibonacci(i), end=" ")
3.2 阶乘（Factorial）¶
阶乘是另一个递归算法的例子，用于计算一个正整数的阶乘
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-1)
n = 5
print("Factorial of", n, "is", factorial(n))
四、 数组和字符串操作
4.1 数组中的重复元素
在面试中，寻找数组中的重复元素是一个常见的题目。这里我们会介绍几种不同的实现方式，适用于不同的场景。
方法1：使用集合（Set）
通过使用集合可以有效地检测数组中的重复元素。集合的特性是其元素不能重复，因此我们可以在遍历数组时检查元素是否已经存在于集合中，如果存在则表示该元素是重复的。
def find_duplicates(arr):
seen = set()
duplicates = set()
for num in arr:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return list(duplicates)
# 使用示例
arr = [1, 3, 4, 2, 5, 3, 2, 7, 8, 2]
result = find_duplicates(arr)
print("数组中的重复元素:", result) # 输出 [2, 3]
时间复杂度: (O(n))，因为我们只遍历了一次数组。
空间复杂度: (O(n))，需要额外的空间来存储集合中的元素。
方法2：使用字典（Dictionary）
我们可以使用字典来记录每个元素出现的次数。然后，遍历字典，找出所有出现次数大于1的元素。
def find_duplicates(arr):
count = {}
duplicates = []
for num in arr:
if num in count:
count[num] += 1
else:
count[num] = 1
for num, freq in count.items():
if freq > 1:
duplicates.append(num)
return duplicates
# 使用示例
arr = [1, 3, 4, 2, 5, 3, 2, 7, 8, 2]
result = find_duplicates(arr)
print("数组中的重复元素:", result) # 输出 [3, 2]
时间复杂度: (O(n))，因为我们两次遍历了数组。
空间复杂度: (O(n))，需要额外的空间来存储字典。
方法3：使用排序
通过先对数组进行排序，然后查找相邻元素是否相等，如果相等则说明有重复。
def find_duplicates(arr):
arr.sort()
duplicates = []
for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
duplicates.append(arr[i])
return list(set(duplicates))
# 使用示例
arr = [1, 3, 4, 2, 5, 3, 2, 7, 8, 2]
result = find_duplicates(arr)
print("数组中的重复元素:", result) # 输出 [2, 3]
时间复杂度: (O(n \log n))，因为排序的时间复杂度为 (O(n \log n))。
空间复杂度: (O(1))（如果排序算法是原地排序的话），但会修改原数组。
方法4：修改原数组的方式（适用于特定条件）
这种方法假设数组中的元素值范围是有限的，比如从 1 到 n，我们可以通过将元素放置在其对应的索引位置上来检测重复。
def find_duplicates(arr):
duplicates = []
for i in range(len(arr)):
while arr[i] != arr[arr[i] - 1]:
arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1]
for i in range(len(arr)):
if arr[i] != i + 1:
duplicates.append(arr[i])
return list(set(duplicates))
# 使用示例
arr = [3, 4, 2, 7, 8, 2, 3, 1]
result = find_duplicates(arr)
print("数组中的重复元素:", result) # 输出 [2, 3]
时间复杂度: (O(n))，每个元素最多交换两次位置。
空间复杂度: (O(1))，没有使用额外的空间，但会修改原数组。
4.2 最大子数组和（Kadane's Algorithm）
Kadane’s Algorithm 是一种用于解决「最大子数组和」问题的高效算法。它的核心思想是通过动态规划的方法，在一次遍历中找到全局最大子数组和。
Kadane’s Algorithm 原理
1. 初始化两个变量：
• max_current：记录当前的子数组和的最大值。
• max_global：记录全局的最大子数组和。
2. 遍历数组，对于数组中的每个元素 num：
• 更新 max_current 为当前元素 num 和 max_current + num 之间的最大值。这一步是为了判断当前元素是否应该作为新子数组的开始。
• 如果 max_current 大于 max_global，则更新 max_global。
3. 最后，max_global 就是所求的最大子数组和。
def max_subarray_sum(arr):
if len(arr) == 0:
return 0 # 如果数组为空，返回 0
max_current = max_global = arr[0]
for num in arr[1:]:
max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current
return max_global
# 使用示例
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr)
print("最大子数组和为:", result) # 输出 6
解释：
在 arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 这个示例中，Kadane’s Algorithm 识别出的最大子数组是 [4, -1, 2, 1]，其和为 6。
详细步骤
1. 初始化：
• max_current = -2（数组第一个元素）
• max_global = -2
2. 遍历数组：
• 处理 1：max_current = max(1, -2 + 1) = 1，更新 max_global = 1
• 处理 -3：max_current = max(-3, 1 - 3) = -2，max_global 不变
• 处理 4：max_current = max(4, -2 + 4) = 4，更新 max_global = 4
• 处理 -1：max_current = max(-1, 4 - 1) = 3，max_global 不变
• 处理 2：max_current = max(2, 3 + 2) = 5，更新 max_global = 5
• 处理 1：max_current = max(1, 5 + 1) = 6，更新 max_global = 6
• 处理 -5：max_current = max(-5, 6 - 5) = 1，max_global 不变
• 处理 4：max_current = max(4, 1 + 4) = 5，max_global 不变
3. 结束：
• 最后，max_global = 6，即最大子数组和为 6。
时间复杂度
Kadane’s Algorithm 的时间复杂度为 O(n)，因为它只需遍历数组一次。
空间复杂度
算法的空间复杂度为 O(1)，因为它只使用了常数级别的额外空间。
这使得 Kadane’s Algorithm 在处理大型数据集时非常高效。
4.3 字符串翻转和回文
在 Python 中，字符串翻转和判断回文字符串是非常基础且常见的操作。下面分别介绍这两个功能的实现。
1. 字符串翻转
字符串翻转可以通过多种方式实现，最简单的一种方法是使用 Python 的切片语法。
实现方式 1：切片语法
def reverse_string(s):
return s[::-1]
# 使用示例
s = "hello"
reversed_s = reverse_string(s)
print("翻转后的字符串:", reversed_s) # 输出: "olleh"
实现方式 2：使用 reversed() 和 join()
def reverse_string(s):
return ''.join(reversed(s))
# 使用示例
s = "world"
reversed_s = reverse_string(s)
print("翻转后的字符串:", reversed_s) # 输出: "dlrow"
2. 判断回文字符串
回文字符串是指正着读和反着读都一样的字符串。要判断一个字符串是否为回文，可以将其翻转后与原字符串进行比较。
实现方式 1：结合翻转和比较
def is_palindrome(s):
return s == s[::-1]
# 使用示例
s = "racecar"
is_palindrome_flag = is_palindrome(s)
print(f"字符串 '{s}' 是回文: {is_palindrome_flag}") # 输出: True
s = "hello"
is_palindrome_flag = is_palindrome(s)
print(f"字符串 '{s}' 是回文: {is_palindrome_flag}") # 输出: False
实现方式 2：双指针法
双指针法不需要创建新的字符串，因此在空间上更为高效。
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# 使用示例
s = "madam"
is_palindrome_flag = is_palindrome(s)
print(f"字符串 '{s}' 是回文: {is_palindrome_flag}") # 输出: True
s = "python"
is_palindrome_flag = is_palindrome(s)
print(f"字符串 '{s}' 是回文: {is_palindrome_flag}") # 输出: False
总结
- 字符串翻转：可以通过切片或内置函数实现。
- 判断回文：通过字符串翻转后比较，或使用双指针法高效地判断字符串是否为回文。
这两个功能在处理字符串操作、算法题目、甚至数据清洗时都非常有用。
4.4 字符串匹配算法
在Python中，字符串匹配算法主要用于在一个大的文本中查找某个模式字符串。常见的字符串匹配算法包括暴力匹配算法、Knuth-Morris-Pratt (KMP) 算法、Rabin-Karp 算法和Boyer-Moore算法。以下是这些算法的Python实现：
1. 暴力匹配算法 (Brute Force)
暴力匹配算法通过在目标字符串中逐个字符比较，找到匹配的子字符串。
def brute_force(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
return i # 匹配成功，返回起始索引
return -1 # 匹配失败
# 示例
text = "hello world"
pattern = "world"
print(brute_force(text, pattern)) # 输出 6
2. Knuth-Morris-Pratt (KMP) 算法
KMP算法通过预处理模式串构建部分匹配表（前缀函数），减少字符比较次数，从而提升匹配效率。
def kmp(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
n = len(text)
m = len(pattern)
lps = build_lps(pattern)
i = j = 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j # 匹配成功，返回起始索引
elif i < n and text[i] != pattern[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1 # 匹配失败
# 示例
text = "abxabcabcaby"
pattern = "abcaby"
print(kmp(text, pattern)) # 输出 6
3. Rabin-Karp 算法
Rabin-Karp算法使用哈希函数将模式和目标字符串的子串转换为整数，然后进行比较，以实现快速匹配。
def rabin_karp(text, pattern):
d = 256 # 字符集的数量
q = 101 # 一个大质数
n = len(text)
m = len(pattern)
p = 0 # 模式的哈希值
t = 0 # 窗口的哈希值
h = 1
for i in range(m - 1):
h = (h * d) % q
for i in range(m):
p = (d * p + ord(pattern[i])) % q
t = (d * t + ord(text[i])) % q
for i in range(n - m + 1):
if p == t:
if text[i:i + m] == pattern:
return i # 匹配成功，返回起始索引
if i < n - m:
t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
if t < 0:
t = t + q
return -1 # 匹配失败
# 示例
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
print(rabin_karp(text, pattern)) # 输出 0
4. Boyer-Moore 算法
Boyer-Moore算法通过预处理模式串的跳转表来减少不必要的比较，从而加速匹配。
def boyer_moore(text, pattern):
def build_last(pattern):
last = {}
for i in range(len(pattern)):
last[pattern[i]] = i
return last
n = len(text)
m = len(pattern)
last = build_last(pattern)
i = m - 1 # 指向text中的字符
j = m - 1 # 指向pattern中的字符
while i < n:
if text[i] == pattern[j]:
if j == 0:
return i # 匹配成功，返回起始索引
else:
i -= 1
j -= 1
else:
i += m - min(j, 1 + last.get(text[i], -1))
j = m - 1
return -1 # 匹配失败
# 示例
text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
print(boyer_moore(text, pattern)) # 输出 17
以上是四种常见的字符串匹配算法的Python实现，可以根据具体需求选择合适的算法。
五、链表
5.1 链表反转
在Python中，链表反转是一个常见的面试题目，通常需要反转单链表。下面是链表反转的详细实现。
单链表节点定义
首先，我们需要定义链表节点的类：
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
反转链表的迭代法实现
迭代法通过逐个节点地调整指针方向来反转链表。时间复杂度为O(n)，空间复杂度为O(1)。
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
# 示例
def print_list(head):
current = head
while current:
print(current.value, end=" -> ")
current = current.next
print("None")
# 创建链表 1 -> 2 -> 3 -> 4 -> 5 -> None
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("原始链表:")
print_list(head)
# 反转链表
reversed_head = reverse_list(head)
print("反转后的链表:")
print_list(reversed_head)
反转链表的递归法实现
递归法是通过递归地反转每个子链表，直到最后一个节点，然后再逐层返回调整指针。时间复杂度为O(n)，空间复杂度为O(n)（由于递归调用栈）。
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head # 反转当前节点
head.next = None # 将当前节点的next置为空
return new_head
# 示例
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("原始链表:")
print_list(head)
# 反转链表
reversed_head_recursive = reverse_list_recursive(head)
print("反转后的链表（递归法）:")
print_list(reversed_head_recursive)
代码解释
- ListNode: 定义了链表节点的结构，每个节点包含一个值和一个指向下一个节点的指针。
- reverse_list: 通过迭代方式反转链表。
- reverse_list_recursive: 通过递归方式反转链表。
- print_list: 用于打印链表内容，方便查看结果。
测试输出
原始链表:
1 -> 2 -> 3 -> 4 -> 5 -> None
反转后的链表:
5 -> 4 -> 3 -> 2 -> 1 -> None
反转后的链表（递归法）:
5 -> 4 -> 3 -> 2 -> 1 -> None
这些方法可以轻松处理链表的反转操作，适用于不同的编程场景。
5.2 环形链表检测
在Python中，环形链表的检测是一个经典的问题，通常使用快慢指针（Floyd’s Cycle Detection Algorithm）来解决。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。以下是该算法的实现：
单链表节点定义
首先，我们定义链表节点的类：
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
环形链表检测
使用快慢指针的方法来检测链表中是否存在环。当快指针和慢指针相遇时，说明链表中有环。
def has_cycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while fast and fast.next:
if slow == fast:
return True # 检测到环
slow = slow.next
fast = fast.next.next
return False # 没有环
# 示例
# 创建链表 1 -> 2 -> 3 -> 4 -> 5 -> None
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# 创建一个环，5 -> 3
head.next.next.next.next.next = head.next.next
# 检测是否有环
print(has_cycle(head)) # 输出 True
# 无环链表测试
head_no_cycle = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(has_cycle(head_no_cycle)) # 输出 False
代码解释
- has_cycle: 使用快慢指针检测链表是否有环。
- slow: 每次移动一个节点。
- fast: 每次移动两个节点。
- 当
slow与fast相遇时，链表存在环。 - 如果
fast到达链表的末端，则链表没有环。
测试输出
True # 表示链表有环
False # 表示链表没有环
这个方法非常高效，可以在链表中快速检测是否存在环。
5.3 合并两个有序链表
合并两个有序链表是一个经典的算法问题，通常使用迭代或递归的方法来实现。在Python中，可以通过比较两个链表的节点值，将较小的节点依次连接到新链表中，最终合并成一个有序链表。
单链表节点定义
首先，我们定义链表节点的类：
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
方法一：迭代法实现合并有序链表
通过使用一个虚拟头节点（dummy node）来简化操作，将两个链表的节点依次比较并连接到新链表中。
def merge_two_lists(l1, l2):
dummy = ListNode() # 创建一个虚拟头节点
current = dummy
while l1 and l2:
if l1.value < l2.value:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# 连接剩余的链表
current.next = l1 if l1 else l2
return dummy.next
# 示例
# 创建链表1: 1 -> 3 -> 5
l1 = ListNode(1, ListNode(3, ListNode(5)))
# 创建链表2: 2 -> 4 -> 6
l2 = ListNode(2, ListNode(4, ListNode(6)))
# 合并两个有序链表
merged_list = merge_two_lists(l1, l2)
# 打印结果
def print_list(head):
current = head
while current:
print(current.value, end=" -> ")
current = current.next
print("None")
print("合并后的链表:")
print_list(merged_list)
方法二：递归法实现合并有序链表
递归法是通过递归地比较两个链表的节点值，依次连接较小的节点到结果链表中。
def merge_two_lists_recursive(l1, l2):
if not l1:
return l2
if not l2:
return l1
if l1.value < l2.value:
l1.next = merge_two_lists_recursive(l1.next, l2)
return l1
else:
l2.next = merge_two_lists_recursive(l1, l2.next)
return l2
# 示例
# 使用上面相同的链表
merged_list_recursive = merge_two_lists_recursive(l1, l2)
print("合并后的链表（递归法）:")
print_list(merged_list_recursive)
代码解释
- merge_two_lists: 迭代法合并两个有序链表，通过一个虚拟头节点
dummy来逐个比较并连接链表中的节点。 - merge_two_lists_recursive: 递归法合并两个有序链表，通过递归地比较和连接节点。
- print_list: 打印链表内容，方便查看结果。
测试输出
合并后的链表:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
合并后的链表（递归法）:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
这两种方法都可以有效地合并两个有序链表，选择迭代还是递归方法取决于个人喜好或具体场景的需求。
六、 树和图
6.1 二叉树遍历
二叉树遍历是树操作中非常重要的部分。二叉树的遍历方式主要分为以下几种：
- 前序遍历（Preorder Traversal）
- 中序遍历（Inorder Traversal）
- 后序遍历（Postorder Traversal）
- 层序遍历（Level Order Traversal）
下面是这些遍历方式的Python实现。
二叉树节点定义
首先，我们定义二叉树的节点类：
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
1. 前序遍历（Preorder Traversal）
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
递归实现
def preorder_traversal(root):
if root is None:
return []
return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right)
# 示例
# 构建二叉树
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print("前序遍历:", preorder_traversal(root)) # 输出 [1, 2, 4, 5, 3]
迭代实现
def preorder_traversal_iterative(root):
if root is None:
return []
stack, output = [root], []
while stack:
node = stack.pop()
if node:
output.append(node.value)
stack.append(node.right)
stack.append(node.left)
return output
print("前序遍历（迭代）:", preorder_traversal_iterative(root)) # 输出 [1, 2, 4, 5, 3]
2. 中序遍历（Inorder Traversal）
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
递归实现
def inorder_traversal(root):
if root is None:
return []
return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)
print("中序遍历:", inorder_traversal(root)) # 输出 [4, 2, 5, 1, 3]
迭代实现
def inorder_traversal_iterative(root):
stack, output = [], []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
output.append(current.value)
current = current.right
return output
print("中序遍历（迭代）:", inorder_traversal_iterative(root)) # 输出 [4, 2, 5, 1, 3]
3. 后序遍历（Postorder Traversal）
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
递归实现
def postorder_traversal(root):
if root is None:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]
print("后序遍历:", postorder_traversal(root)) # 输出 [4, 5, 2, 3, 1]
迭代实现
def postorder_traversal_iterative(root):
if root is None:
return []
stack, output = [root], []
while stack:
node = stack.pop()
if node:
output.append(node.value)
stack.append(node.left)
stack.append(node.right)
return output[::-1] # 逆序输出
print("后序遍历（迭代）:", postorder_traversal_iterative(root)) # 输出 [4, 5, 2, 3, 1]
4. 层序遍历（Level Order Traversal）
层序遍历是按层从上到下，从左到右遍历二叉树。
迭代实现
from collections import deque
def level_order_traversal(root):
if root is None:
return []
queue = deque([root])
output = []
while queue:
node = queue.popleft()
output.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return output
print("层序遍历:", level_order_traversal(root)) # 输出 [1, 2, 3, 4, 5]
代码解释
- TreeNode: 定义了二叉树的节点，每个节点包含一个值和指向左、右子节点的指针。
- preorder_traversal: 前序遍历二叉树的递归与迭代实现。
- inorder_traversal: 中序遍历二叉树的递归与迭代实现。
- postorder_traversal: 后序遍历二叉树的递归与迭代实现。
- level_order_traversal: 层序遍历二叉树的迭代实现。
测试输出
前序遍历: [1, 2, 4, 5, 3]
前序遍历（迭代）: [1, 2, 4, 5, 3]
中序遍历: [4, 2, 5, 1, 3]
中序遍历（迭代）: [4, 2, 5, 1, 3]
后序遍历: [4, 5, 2, 3, 1]
后序遍历（迭代）: [4, 5, 2, 3, 1]
层序遍历: [1, 2, 3, 4, 5]
这些遍历方式适用于不同的树操作场景，可以根据需求选择合适的遍历方法。
6.2 二叉搜索树（BST）
二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：
- 每个节点的左子树中的所有节点值都小于该节点的值。
- 每个节点的右子树中的所有节点值都大于该节点的值。
- 每个节点的左右子树也是二叉搜索树。
BST 可以用于高效的查找、插入和删除操作。下面是二叉搜索树的实现，包括插入、查找和删除等基本操作。
二叉搜索树节点定义
首先，定义二叉搜索树的节点类：
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
二叉搜索树的插入操作
插入操作将一个新的值插入到BST中，插入的过程保持BST的性质。
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
# 示例：构建二叉搜索树
root = None
values = [5, 3, 7, 2, 4, 6, 8]
for value in values:
root = insert(root, value)
# BST 应该如下:
# 5
# / \
# 3 7
# / \ / \
# 2 4 6 8
二叉搜索树的查找操作
查找操作用于确定BST中是否包含某个值。
def search(root, value):
if root is None or root.value == value:
return root
if value < root.value:
return search(root.left, value)
else:
return search(root.right, value)
# 查找值为4的节点
node = search(root, 4)
print("找到节点:", node.value if node else "未找到")
二叉搜索树的删除操作
删除操作需要分情况处理： 1. 删除的节点是叶子节点：直接删除。 2. 删除的节点有一个子节点：用子节点替换该节点。 3. 删除的节点有两个子节点：找到右子树的最小节点（或左子树的最大节点），替换删除节点，并删除该最小节点。
def delete(root, value):
if root is None:
return root
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
min_larger_node = get_min(root.right)
root.value = min_larger_node.value
root.right = delete(root.right, min_larger_node.value)
return root
def get_min(node):
current = node
while current.left is not None:
current = current.left
return current
# 删除节点 3
root = delete(root, 3)
# 删除节点后，BST 应该如下:
# 5
# / \
# 4 7
# / / \
# 2 6 8
打印二叉搜索树
为了直观地查看BST的结构，可以使用中序遍历（Inorder Traversal）来打印树的节点。中序遍历会按从小到大的顺序输出BST的所有节点。
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.value, end=" ")
inorder_traversal(root.right)
print("中序遍历BST:")
inorder_traversal(root) # 输出: 2 4 5 6 7 8
代码解释
- TreeNode: 定义了二叉搜索树的节点，每个节点包含一个值和指向左、右子节点的指针。
- insert: 插入新节点，保持BST的性质。
- search: 查找某个值是否存在于BST中。
- delete: 删除节点并保持BST的性质。
- get_min: 获取子树中的最小节点，用于删除操作。
- inorder_traversal: 中序遍历BST，按从小到大的顺序打印节点值。
测试输出
找到节点: 4
中序遍历BST:
2 4 5 6 7 8
通过这些操作，你可以在Python中实现一个完整的二叉搜索树，能够进行插入、查找和删除等操作，并保持树的有序性。
6.3 最近公共祖先（LCA）
最近公共祖先（Lowest Common Ancestor，LCA）是二叉树中两个节点的最低（最深）公共祖先。这个问题在树的处理过程中非常常见，通常可以通过递归方法来解决。
方法概述
给定一个二叉树和两个节点 p 和 q，我们需要找到它们的最近公共祖先。LCA 满足以下条件：
- 节点 p 和 q 分别位于LCA的左右子树中，或者其中一个节点就是LCA本身。
二叉树节点定义
首先，定义二叉树的节点类：
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
递归方法实现最近公共祖先
递归地遍历树，通过比较当前节点与目标节点 p 和 q 的关系，逐步找到它们的最近公共祖先。
def lowest_common_ancestor(root, p, q):
if root is None 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 if left else right
# 示例
# 构建二叉树
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
# 查找节点 5 和 1 的最近公共祖先
p = root.left # 节点 5
q = root.right # 节点 1
lca = lowest_common_ancestor(root, p, q)
print("最近公共祖先:", lca.value) # 输出 3
# 查找节点 5 和 4 的最近公共祖先
p = root.left # 节点 5
q = root.left.right.right # 节点 4
lca = lowest_common_ancestor(root, p, q)
print("最近公共祖先:", lca.value) # 输出 5
代码解释
- lowest_common_ancestor:
- 如果当前节点为
None或者是p或q，则返回当前节点。 - 递归地在左子树和右子树中查找
p和q。 - 如果在左右子树中分别找到了
p和q，则当前节点就是它们的最近公共祖先。 - 如果在一侧找到了两个节点的公共祖先，则返回该侧的结果。
测试输出
最近公共祖先: 3
最近公共祖先: 5
进一步解释
- 在树的递归中，当找到
p或q时，立即返回该节点。 - 如果
p和q分别位于某个节点的左右子树中，则该节点就是LCA。 - 这种方法适用于一般的二叉树，并且具有较好的时间复杂度，为 O(n)，其中 n 是树的节点数。
6.4 图的遍历
图的遍历主要包括两种经典方法：深度优先搜索（DFS）和广度优先搜索（BFS）。这两种方法可以应用于各种类型的图，包括有向图和无向图。
1. 图的表示
在图的遍历中，通常使用邻接表（Adjacency List）来表示图。以下是图的邻接表表示方法及基本结构：
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
2. 深度优先搜索（DFS）
DFS是一种递归的图遍历方法，它尽可能深地搜索图的分支。DFS可以用递归或栈来实现。
递归实现
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# 示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("DFS递归遍历: ")
dfs_recursive(g.graph, 2)
迭代实现
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
stack.extend(reversed(graph[node]))
# 示例
print("\nDFS迭代遍历: ")
dfs_iterative(g.graph, 2)
3. 广度优先搜索（BFS）
BFS是一种层次遍历方法，它从根节点开始，逐层向外扩展。BFS通常使用队列来实现。
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(graph[node])
# 示例
print("\nBFS遍历: ")
bfs(g.graph, 2)
代码解释
- Graph: 图的类，使用邻接表表示图的结构。
- add_edge: 添加图的边。
- dfs_recursive: 递归实现的深度优先搜索。
- dfs_iterative: 迭代实现的深度优先搜索。
- bfs: 广度优先搜索。
示例输出
DFS递归遍历:
2 0 1 3
DFS迭代遍历:
2 0 1 3
BFS遍历:
2 0 3 1
进一步解释
- DFS适用于需要探索所有路径的场景，比如迷宫求解或连通性检查。
- BFS适用于找到最短路径等需要逐层扩展的场景，比如最短路径算法。
通过这些实现，你可以在Python中有效地进行图的遍历操作。
6.5 最短路径算法
最短路径算法用于在图中找到从一个起点到终点的最短路径。常见的最短路径算法有以下几种：
- Dijkstra算法：适用于无负权边的图。
- Bellman-Ford算法：适用于含负权边的图，可以检测负权环。
- Floyd-Warshall算法：用于计算所有节点对之间的最短路径。
1. Dijkstra算法
Dijkstra算法用于计算单源最短路径，适用于无负权边的图。
import heapq
def dijkstra(graph, start):
# 初始化最短路径字典，所有距离设为正无穷
distances = {node: float('inf') for node in graph}
distances[start] = 0 # 起点距离为0
priority_queue = [(0, start)] # (距离, 节点)
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 示例图的邻接表表示
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
# 计算从节点 'A' 出发到其他所有节点的最短路径
print("Dijkstra算法的最短路径: ")
distances = dijkstra(graph, 'A')
print(distances)
2. Bellman-Ford算法
Bellman-Ford算法适用于带有负权边的图，可以检测负权环。
def bellman_ford(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node]:
if distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
# 检测负权环
for node in graph:
for neighbor, weight in graph[node]:
if distances[node] + weight < distances[neighbor]:
raise ValueError("图中存在负权环")
return distances
# 示例图的邻接表表示
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)],
}
# 计算从节点 'A' 出发到其他所有节点的最短路径
print("Bellman-Ford算法的最短路径: ")
distances = bellman_ford(graph, 'A')
print(distances)
3. Floyd-Warshall算法
Floyd-Warshall算法用于计算所有节点对之间的最短路径。
def floyd_warshall(graph):
nodes = list(graph.keys())
distances = {node: {node2: float('inf') for node2 in nodes} for node in nodes}
for node in nodes:
distances[node][node] = 0
for node in graph:
for neighbor, weight in graph[node]:
distances[node][neighbor] = weight
for k in nodes:
for i in nodes:
for j in nodes:
if distances[i][j] > distances[i][k] + distances[k][j]:
distances[i][j] = distances[i][k] + distances[k][j]
return distances
# 示例图的邻接表表示
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
# 计算所有节点对之间的最短路径
print("Floyd-Warshall算法的最短路径: ")
distances = floyd_warshall(graph)
for i in distances:
print(f"从 {i} 出发的最短路径: {distances[i]}")
代码解释
- Dijkstra算法：
- 使用优先队列（最小堆）来选择当前最近的未处理节点。
-
更新从起点到其他节点的最短路径。
-
Bellman-Ford算法：
-
通过逐边松弛法更新路径，适用于检测负权环的图。
-
Floyd-Warshall算法：
- 使用动态规划的思想，通过不断更新所有节点对之间的最短路径来计算最终结果。
示例输出
Dijkstra算法的最短路径:
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
Bellman-Ford算法的最短路径:
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
Floyd-Warshall算法的最短路径:
从 A 出发的最短路径: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
从 B 出发的最短路径: {'A': inf, 'B': 0, 'C': 2, 'D': 3}
从 C 出发的最短路径: {'A': inf, 'B': inf, 'C': 0, 'D': 1}
从 D 出发的最短路径: {'A': inf, 'B': inf, 'C': inf, 'D': 0}
通过这些实现，你可以在Python中有效地进行图的最短路径计算，并应用于各种场景，如路径规划和网络流分析等。
七、 动态规划（Dynamic Programming）
动态规划（Dynamic Programming, DP）是解决很多优化问题的强大工具，但理解起来可能有点复杂。为了让它更容易理解，我将通过以下几个步骤来详细讲解。
1. 什么是动态规划？
动态规划是一种将复杂问题分解成更小的子问题，然后逐步解决这些子问题，最终解决整个问题的方法。它的核心思想是避免重复计算，通过存储和复用已经计算过的结果来提高效率。
2. 动态规划适用的两大条件
-
重叠子问题：问题可以分解成多个相同的子问题，这些子问题的结果可以被多次利用。
-
最优子结构：问题的最优解可以通过子问题的最优解组合而成。
3. 动态规划的实现步骤
动态规划一般分为以下几个步骤：
-
定义状态：确定用什么变量表示问题的某一状态，通常用一个或多个数组（表格）来存储这些状态。
-
状态转移方程：找出状态之间的关系，也就是如何从已知的状态得到当前的状态。这个关系就是状态转移方程。
-
初始化状态：设定初始状态，也就是问题最基础的情况。
-
计算最终结果：通过状态转移方程，从初始状态逐步计算出最终结果。
4. 经典案例讲解
案例一：斐波那契数列
问题：给定一个整数 n，求斐波那契数列的第 n 项。斐波那契数列的定义如下：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （n ≥ 2）
递归的斐波那契实现
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(10)) # 输出55
这个递归方法非常直观，但它的时间复杂度是指数级的 O(2^n)，因为很多子问题会被重复计算。
动态规划的斐波那契实现
def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_dp(10)) # 输出55
在这个版本中，我们使用一个数组 dp 来存储每个子问题的结果，避免了重复计算，将时间复杂度降低为 O(n)。
案例二：0/1 背包问题
问题：给定一个背包，它能容纳的最大重量为 W。还有 n 个物品，每个物品都有一个重量 w[i] 和价值 v[i]。你可以选择将这些物品中的一些装入背包，如何使得背包中的物品价值最大化？
动态规划的解决方案
- 定义状态：
-
用
dp[i][w]表示前i个物品在背包容量为w时的最大价值。 -
状态转移方程：
- 如果不选择第
i个物品：dp[i][w] = dp[i-1][w] - 如果选择第
i个物品：dp[i][w] = dp[i-1][w-w[i]] + v[i] -
最终：
dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i]) -
初始化：
dp[0][...] = 0（没有物品时的最大价值为 0）-
dp[...][0] = 0（背包容量为 0 时的最大价值为 0） -
计算最终结果：
- 最终的最大价值是
dp[n][W]。
def knapsack(w, v, W):
n = len(w)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(W + 1):
if j >= w[i - 1]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][W]
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
W = 5
print(knapsack(w, v, W)) # 输出7
5. 动态规划常见问题总结
- 理解状态转移方程：这是动态规划的核心，必须清楚每一步是如何通过前一步得到的。
- 空间优化：有些时候可以对状态转移方程进行优化，减少空间复杂度，比如使用滚动数组。
- 识别动态规划问题：通常需要优化的问题，有最优子结构和重叠子问题的特性，都可以考虑用动态规划来解决。
6. 最长公共子序列（LCS）
最长公共子序列（Longest Common Subsequence, LCS）问题是经典的动态规划问题。LCS指的是两个序列中最长的公共子序列，即在保持顺序不变的前提下，这两个序列中都出现过的最长的子序列。
1. 问题描述
给定两个字符串 X 和 Y，找出它们的最长公共子序列。
例如：
- 输入：X = "ABCBDAB" 和 Y = "BDCAB"
- 输出："BDAB" 或 "BCAB"（长度为 4）
2. 动态规划解法
状态定义
- 定义
dp[i][j]表示字符串X的前i个字符和字符串Y的前j个字符的最长公共子序列的长度。
状态转移方程
- 如果
X[i-1] == Y[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。 - 如果
X[i-1] != Y[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始化
dp[0][j] = 0表示X为空串时 LCS 长度为 0。dp[i][0] = 0表示Y为空串时 LCS 长度为 0。
3. 实现代码
def lcs(X, Y):
m = len(X)
n = len(Y)
# 创建一个 (m+1) x (n+1) 的二维数组来存储结果
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 填充 dp 表
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[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_string = []
i, j = m, n
while i > 0 and j > 0:
if X[i - 1] == Y[j - 1]:
lcs_string.append(X[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_string))
# 示例使用
X = "ABCBDAB"
Y = "BDCAB"
length, lcs_string = lcs(X, Y)
print(f"LCS长度: {length}")
print(f"LCS字符串: {lcs_string}")
4. 示例输出
LCS长度: 4
LCS字符串: BCAB
5. 代码解释
- dp数组：
dp[i][j]存储X的前i个字符和Y的前j个字符的 LCS 长度。 - 状态转移：根据
X[i-1]和Y[j-1]是否相等来更新dp数组。 - 构造LCS字符串：通过反向遍历
dp数组来重建 LCS。
6. 复杂度分析
- 时间复杂度：
O(m * n)，其中m和n分别是X和Y的长度。 - 空间复杂度：
O(m * n)，用于存储dp数组。
这个方法既能求出 LCS 的长度，也能找到对应的最长公共子序列。
7. 最长递增子序列（LIS）
最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题。给定一个序列，找到一个最长的子序列，使得这个子序列中的元素是严格递增的。
1. 问题描述
给定一个整数序列，找到其中最长的严格递增的子序列。例如：
- 输入：[10, 9, 2, 5, 3, 7, 101, 18]
- 输出：[2, 3, 7, 101]，长度为 4。
2. 动态规划解法
状态定义
- 定义
dp[i]表示以nums[i]结尾的最长递增子序列的长度。
状态转移方程
- 对于每个
j，如果nums[i] > nums[j]，则dp[i] = max(dp[i], dp[j] + 1)。
初始化
dp[i] = 1，每个元素都可以单独成为一个长度为 1 的子序列。
3. 实现代码
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
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]
print(f"LIS长度: {length_of_lis(nums)}")
4. 示例输出
LIS长度: 4
5. 代码解释
- dp数组：
dp[i]存储以nums[i]结尾的最长递增子序列的长度。 - 状态转移：对于每个
i，检查所有j < i的情况，如果nums[i] > nums[j]，更新dp[i]。 - 返回值：
max(dp)是整个序列的最长递增子序列的长度。
6. 复杂度分析
- 时间复杂度：
O(n^2)，因为每个元素都要与之前的元素进行比较。 - 空间复杂度：
O(n)，用于存储dp数组。
7. 二分法优化
通过使用二分查找，我们可以将时间复杂度优化为 O(n log n)。这里的思路是用一个数组 lis 来记录当前找到的最长递增子序列，如果新元素比 lis 中的最后一个元素大，就把它加到 lis 的末尾；否则用二分查找找到 lis 中第一个大于等于它的元素并替换掉，这样确保 lis 中的元素始终是递增的。
import bisect
def length_of_lis(nums):
lis = []
for num in nums:
pos = bisect.bisect_left(lis, num)
if pos < len(lis):
lis[pos] = num
else:
lis.append(num)
return len(lis)
# 示例使用
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS长度: {length_of_lis(nums)}")
8. 二分法优化的输出
LIS长度: 4
9. 复杂度分析
- 时间复杂度：
O(n log n)，因为每次插入元素时使用了二分查找。 - 空间复杂度：
O(n)，用于存储lis列表。
通过以上方法，你可以有效地计算一个序列中的最长递增子序列。
8. 硬币找零问题
硬币找零问题是一个经典的动态规划问题。给定不同面值的硬币和一个总金额，计算凑成该金额所需的最少硬币数。
1. 问题描述
给定金额 amount 和一些硬币面值 coins，求出凑成该金额的最少硬币数。如果无法凑成，则返回 -1。
2. 动态规划解法
状态定义
- 定义
dp[i]表示凑成金额i所需的最少硬币数。
状态转移方程
- 对于每个硬币面值
coin，如果i >= coin，则dp[i] = min(dp[i], dp[i - coin] + 1)。
初始化
dp[0] = 0表示金额为 0 时不需要任何硬币。- 其他
dp[i]初始化为一个较大的数（如amount + 1），表示尚未计算出的最少硬币数。
3. 实现代码
def coin_change(coins, amount):
# 初始化dp数组，dp[i] 表示凑成金额i所需的最少硬币数
dp = [amount + 1] * (amount + 1)
dp[0] = 0
# 计算每个金额的最少硬币数
for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
# 如果 dp[amount] 仍然为初始化的值，说明无法凑成该金额
return dp[amount] if dp[amount] != amount + 1 else -1
# 示例使用
coins = [1, 2, 5]
amount = 11
print(f"凑成金额 {amount} 所需的最少硬币数: {coin_change(coins, amount)}")
4. 示例输出
凑成金额 11 所需的最少硬币数: 3
5. 代码解释
- dp数组：
dp[i]表示凑成金额i所需的最少硬币数。 - 状态转移：遍历所有硬币，更新
dp[i]为最小值。 - 返回值：如果
dp[amount]未被更新，说明无法凑成该金额，否则返回dp[amount]。
6. 复杂度分析
- 时间复杂度：
O(n * m)，其中n是金额amount，m是硬币种类数。 - 空间复杂度：
O(n)，用于存储dp数组。
7. 扩展：获取具体的硬币组合
如果不仅要知道最少硬币数，还要知道具体的硬币组合，可以通过额外的数组 track 来记录使用的硬币。
def coin_change(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
track = [-1] * (amount + 1) # 记录每个金额选择的最后一个硬币
for i in range(1, amount + 1):
for coin in coins:
if i >= coin and dp[i] > dp[i - coin] + 1:
dp[i] = dp[i - coin] + 1
track[i] = coin
if dp[amount] == amount + 1:
return -1, []
# 反向推导具体的硬币组合
combination = []
curr = amount
while curr > 0:
combination.append(track[curr])
curr -= track[curr]
return dp[amount], combination
# 示例使用
coins = [1, 2, 5]
amount = 11
min_coins, combination = coin_change(coins, amount)
print(f"凑成金额 {amount} 所需的最少硬币数: {min_coins}")
print(f"使用的硬币组合: {combination}")
8. 扩展示例输出
凑成金额 11 所需的最少硬币数: 3
使用的硬币组合: [5, 5, 1]
这个扩展版本不仅告诉你最少需要多少个硬币，还给出了一个具体的硬币组合，帮助你更好地理解硬币找零问题。
八、贪心算法（Greedy Algorithms）
贪心算法（Greedy Algorithm）是一种算法设计思想，它通过在每一步选择中都采取当前状态下的最优选择（局部最优解），最终试图得到全局最优解。虽然贪心算法并不总能得到全局最优解，但在很多问题中，它可以提供一个有效的解决方案，尤其是在某些优化问题中。
1. 贪心算法的基本思想
贪心算法的基本思想是在解决问题的过程中，总是做出在当前看来是最好的选择，即局部最优解，希望通过这些局部最优解最终能得到全局最优解。
2. 贪心算法的适用场景
贪心算法通常适用于以下场景： - 问题具有贪心选择性质：每个子问题的最优解能直接或间接地导出整体问题的最优解。 - 问题具有最优子结构性质：整体问题的最优解包含其子问题的最优解。
3. 典型问题
3.1. 零钱找零问题（Coin Change Problem）
在零钱找零问题中，假设你有无限多的面值为 1, 5, 10, 25 的硬币，问如何用最少的硬币数量凑成一个特定的金额。例如，用最少的硬币凑成金额 41。
贪心算法思路： - 每次都尽量选择当前面值最大的硬币，直到金额为零。
Python 实现：
def greedy_coin_change(coins, amount):
coins.sort(reverse=True) # 将硬币面值降序排列
count = 0
for coin in coins:
if amount >= coin:
count += amount // coin
amount %= coin
return count
# 示例使用
coins = [25, 10, 5, 1]
amount = 41
print(f"凑成金额 {amount} 所需的最少硬币数: {greedy_coin_change(coins, amount)}")
输出：
凑成金额 41 所需的最少硬币数: 4
注意：贪心算法在解决零钱找零问题时，必须满足硬币面值是特定情况（如 1, 5, 10, 25 ），才可以保证最优解。在某些硬币组合下，贪心算法可能无法找到最优解。
3.2. 活动选择问题（Activity Selection Problem）
在活动选择问题中，给定一组活动，每个活动有一个开始时间和结束时间，问最多能安排多少个不重叠的活动。
贪心算法思路： - 每次选择结束时间最早的活动，这样可以留出最多的时间给后续的活动。
Python 实现：
def activity_selection(activities):
# 按照结束时间排序
activities.sort(key=lambda x: x[1])
selected_activities = []
last_end_time = 0
for activity in activities:
if activity[0] >= last_end_time:
selected_activities.append(activity)
last_end_time = activity[1]
return selected_activities
# 示例使用
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
selected = activity_selection(activities)
print(f"选择的活动: {selected}")
输出：
选择的活动: [(1, 4), (5, 7), (8, 11), (12, 14)]
4. 贪心算法的优缺点
优点：
- 算法简单，容易实现。
- 对于特定类型的问题，能提供高效的解决方案。
缺点：
- 并不总是能保证得到全局最优解。
- 适用性较窄，只能应用于特定类型的问题。
5. 总结
贪心算法是一种基于选择当前最优解的策略，用于解决一系列优化问题。尽管贪心算法并不适用于所有问题，但在适合的场景下，它能为我们提供简单且高效的解决方案。在使用贪心算法时，需确保问题满足贪心选择性质和最优子结构性质，以确保算法能够找到全局最优解。
九、位操作
位操作（Bitwise Operations）是直接在二进制位上进行的操作，通常用于底层编程和高效计算。在Python中，常见的位操作包括按位与、按位或、按位异或、按位取反、左移和右移等。
1. 常见的位操作
1.1. 按位与（&）
按位与操作会将两个数字的每个位进行比较，如果对应位都为 1，则结果为 1，否则为 0。
示例：
a = 5 # 二进制: 0101
b = 3 # 二进制: 0011
result = a & b # 二进制: 0001
print(f"{a} & {b} = {result}") # 输出: 5 & 3 = 1
1.2. 按位或（|）
按位或操作会将两个数字的每个位进行比较，如果对应位有一个为 1，则结果为 1，否则为 0。
示例：
a = 5 # 二进制: 0101
b = 3 # 二进制: 0011
result = a | b # 二进制: 0111
print(f"{a} | {b} = {result}") # 输出: 5 | 3 = 7
1.3. 按位异或（^）
按位异或操作会将两个数字的每个位进行比较，如果对应位不同，则结果为 1，否则为 0。
示例：
a = 5 # 二进制: 0101
b = 3 # 二进制: 0011
result = a ^ b # 二进制: 0110
print(f"{a} ^ {b} = {result}") # 输出: 5 ^ 3 = 6
1.4. 按位取反（~）
按位取反操作会将数字的每个位进行反转，即 1 变 0，0 变 1。在Python中，按位取反也会改变数字的符号。
示例：
a = 5 # 二进制: 0101
result = ~a # 二进制: -0110 (补码表示)
print(f"~{a} = {result}") # 输出: ~5 = -6
1.5. 左移（<<）
左移操作会将数字的二进制表示向左移动指定的位数，右侧补 0。左移相当于乘以 2 的若干次方。
示例：
a = 5 # 二进制: 0101
result = a << 2 # 二进制: 10100
print(f"{a} << 2 = {result}") # 输出: 5 << 2 = 20
1.6. 右移（>>）
右移操作会将数字的二进制表示向右移动指定的位数，左侧补 0。右移相当于除以 2 的若干次方。
示例：
a = 20 # 二进制: 10100
result = a >> 2 # 二进制: 0101
print(f"{a} >> 2 = {result}") # 输出: 20 >> 2 = 5
2. 位操作的应用
2.1. 判断奇偶性
通过检查数字的最低位是否为 1，可以判断一个数字是奇数还是偶数。
def is_odd(n):
return n & 1 == 1
# 示例
n = 10
print(f"{n} 是奇数吗？ {is_odd(n)}") # 输出: 10 是奇数吗？ False
2.2. 交换两个数
在不使用额外空间的情况下，可以通过按位异或交换两个数的值。
a = 5
b = 3
a = a ^ b
b = a ^ b
a = a ^ b
print(f"交换后: a = {a}, b = {b}") # 输出: 交换后: a = 3, b = 5
2.3. 清零最低位的 1
清除一个数字二进制表示中最低位的 1。
n = 12 # 二进制: 1100
result = n & (n - 1) # 清除最低位的1 -> 二进制: 1000
print(f"{n} 清除最低位的1后的结果: {result}") # 输出: 12 清除最低位的1后的结果: 8
2.4. 计算二进制中 1 的个数（汉明重量）
计算一个整数的二进制表示中 1 的个数。
def count_ones(n):
count = 0
while n:
n = n & (n - 1) # 每次清除最低位的1
count += 1
return count
# 示例
n = 13 # 二进制: 1101
print(f"{n} 的二进制中有 {count_ones(n)} 个1") # 输出: 13 的二进制中有 3 个1
3. 总结
位操作在计算机科学中有广泛的应用，尤其是在需要高效计算或处理底层数据时。掌握这些位操作可以帮助你编写更高效的代码，并更好地理解计算机如何处理二进制数据。
十、 哈希表与集合
10.1 两数之和
题目描述:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数，并返回它们的数组下标。
def two_sum(nums, target):
# 创建一个哈希表，用于存储已经遍历过的元素及其对应的索引
hash_map = {}
# 遍历数组
for i, num in enumerate(nums):
# 计算当前数字与目标值的差值
complement = target - num
# 检查差值是否在哈希表中
if complement in hash_map:
return [hash_map[complement], i]
# 如果不在哈希表中，则将当前数字和索引存入哈希表
hash_map[num] = i
return None # 如果没有找到，则返回 None
# 示例使用
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"两数之和的下标为: {result}") # 输出: [0, 1]
代码解释
- 哈希表：hash_map 用于存储数组中的元素值及其对应的索引。在遍历数组的过程中，查找目标值 target 减去当前元素的差值是否已经存在于哈希表中，这一步操作的时间复杂度为 O(1)。
- 时间复杂度：使用哈希表后，整体时间复杂度为 O(n)，其中 n 是数组的长度。
- 空间复杂度：由于需要额外的哈希表来存储元素和索引，空间复杂度为 O(n)。
示例输出
两数之和的下标为: [0, 1]
该代码返回的是数组中两个数的下标，它们的和等于目标值 target。在示例中，数组 [2, 7, 11, 15] 中的两个数 2 和 7 的和等于 9，它们的下标分别为 0 和 1。
10.2 有效的括号
问题描述：
给定一个只包含 (, ), {, }, [ 和 ] 的字符串，判断字符串中的括号是否成对出现且顺序正确。
1. 问题分析
要判断括号是否有效，需要满足以下条件： 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。
我们可以使用栈（stack）来解决这个问题。遍历字符串中的每个字符：
- 如果是左括号（(, {, [），将其压入栈中。
- 如果是右括号（), }, ]），检查栈顶元素是否是对应的左括号。如果是，则将栈顶元素弹出。如果不是，说明括号顺序不正确，返回 False。
最后，如果栈为空，说明所有括号都正确闭合，返回 True；否则，返回 False。
2. Python 实现
def is_valid(s):
# 创建一个栈用于存储左括号
stack = []
# 创建一个字典，用于存储括号的对应关系
bracket_map = {')': '(', '}': '{', ']': '['}
# 遍历字符串中的每个字符
for char in s:
if char in bracket_map:
# 如果当前字符是右括号，检查栈顶是否是对应的左括号
top_element = stack.pop() if stack else '#'
if bracket_map[char] != top_element:
return False
else:
# 如果当前字符是左括号，将其压入栈中
stack.append(char)
# 检查栈是否为空
return not stack
# 示例使用
s = "({[()]})"
result = is_valid(s)
print(f"字符串 {s} 是有效的括号吗？ {result}") # 输出: True
3. 代码解释
- 栈：我们使用列表
stack来模拟栈的行为，处理括号匹配问题。 - 字典：
bracket_map字典用于存储右括号和对应左括号的匹配关系。 - 遍历字符串：对于字符串中的每个字符，判断是左括号还是右括号，并根据栈的情况进行处理。
- 栈顶检查：每次遇到右括号时，检查栈顶是否有对应的左括号。如果有，则弹出栈顶元素；否则，说明括号不匹配。
4. 示例输出
字符串 ({[()]}) 是有效的括号吗？ True
在这个示例中，字符串 ({[()]}) 是有效的括号匹配。所有括号都正确闭合，代码返回 True。如果输入的字符串是 ({[})]，则返回 False，因为括号顺序不正确。
十一、高级数据结构
11.1 字典树（Trie）
字典树（Trie）是一种树形数据结构，主要用于处理字符串的检索操作，尤其适用于自动补全、拼写检查等应用。它的核心思想是利用公共前缀来提高查询效率。
1. 字典树的基本概念
字典树是一个多叉树，通常用于存储一组字符串。每个节点代表一个字符，路径代表从根节点到某一节点的一个字符串。字典树的每个节点除了包含字符信息外，还可以包含以下信息： - 是否为某个单词的结束节点。 - 子节点的指针或引用，表示下一个字符的可能路径。
2. 字典树的基本操作
字典树的基本操作包括插入（Insert）、查询（Search）、和前缀查询（StartsWith）。
3. Python 实现
下面是一个简单的 Python 字典树实现：
class TrieNode:
def __init__(self):
# 每个节点有一个字典，用于存储子节点
self.children = {}
# 是否是某个单词的结尾
self.is_end_of_word = False
class Trie:
def __init__(self):
# 初始化字典树的根节点
self.root = TrieNode()
def insert(self, word):
# 插入单词
node = self.root
for char in word:
# 如果字符不在当前节点的子节点中，则添加新节点
if char not in node.children:
node.children[char] = TrieNode()
# 移动到下一个节点
node = node.children[char]
# 最后一个字符标记为单词的结束
node.is_end_of_word = True
def search(self, word):
# 查询单词是否在字典树中
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
# 查询是否存在以某个前缀开始的单词
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# 示例使用
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # 输出: True
print(trie.search("app")) # 输出: False
print(trie.starts_with("app")) # 输出: True
trie.insert("app")
print(trie.search("app")) # 输出: True
4. 代码解释
-
TrieNode 类：表示字典树中的一个节点。
children是一个字典，键是字符，值是对应的子节点；is_end_of_word表示该节点是否为某个单词的结尾。 -
Trie 类：表示字典树，包括插入、查询、和前缀查询操作。
- insert(word)：将一个单词插入到字典树中。每个字符对应一个节点，如果当前字符不存在于节点的子节点中，则创建新节点。遍历完单词的所有字符后，将最后一个节点标记为单词的结尾。
- search(word)：查询字典树中是否存在某个单词。沿着字符路径遍历，如果某个字符不存在于当前节点的子节点中，返回
False。如果所有字符都匹配，且最后一个节点标记为单词的结尾，返回True。 - starts_with(prefix)：查询字典树中是否存在以某个前缀开始的单词。方法类似于
search，但不要求匹配完整单词，只要前缀存在即可返回True。
5. 示例输出
True
False
True
True
6. 字典树的应用场景
- 自动补全：根据输入的前缀，提供可能的单词补全。
- 拼写检查：快速检索单词表中的合法单词。
- 前缀匹配：用于搜索引擎、文本编辑器等场景下的前缀匹配查询。
字典树由于其结构的特点，可以在处理大量字符串时提供高效的插入和查询操作。
11.2 并查集（Union-Find）
并查集（Union-Find）是一种用于处理动态连通性问题的数据结构，特别适合用于处理图的连通性问题。它支持两种操作： - Union：将两个元素所在的集合合并。 - Find：查找元素所在集合的代表元素（根节点），也称为查找元素的 "父节点"。
并查集的常见优化包括路径压缩和按秩合并，以提高操作效率。
1. 基本思想
- 路径压缩：在查找过程中，使路径上的所有节点直接指向根节点，从而减少树的高度。
- 按秩合并：在合并两个集合时，总是将较小的树合并到较大的树上，防止树变得过高。
2. 并查集的 Python 实现
class UnionFind:
def __init__(self, size):
# 初始化父节点指针和秩
self.parent = [i for i in range(size)]
self.rank = [1] * size
def find(self, p):
# 查找元素 p 的根节点，同时进行路径压缩
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
# 合并两个元素 p 和 q 所在的集合
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
# 按秩合并
if self.rank[rootP] > self.rank[rootQ]:
self.parent[rootQ] = rootP
elif self.rank[rootP] < self.rank[rootQ]:
self.parent[rootP] = rootQ
else:
self.parent[rootQ] = rootP
self.rank[rootP] += 1
def connected(self, p, q):
# 检查两个元素是否在同一集合
return self.find(p) == self.find(q)
# 示例使用
uf = UnionFind(10)
uf.union(1, 2)
uf.union(3, 4)
uf.union(2, 4)
print(uf.connected(1, 3)) # 输出: True
print(uf.connected(1, 5)) # 输出: False
3. 代码解释
- 初始化：
parent列表记录每个节点的父节点。初始时，每个节点的父节点指向自己，表示每个节点是一个独立的集合。-
rank列表用于记录每个节点的秩（即树的高度），初始时每个节点的秩为1。 -
find(p)：
- 查找节点
p的根节点，如果p的父节点不是它自己，则递归查找p的父节点，最终找到根节点。 -
在递归查找的过程中，使用路径压缩，将
p及其祖先的父节点直接指向根节点，以减少树的高度。 -
union(p, q)：
- 合并
p和q所在的两个集合。首先找到它们的根节点rootP和rootQ。 -
使用按秩合并的策略，较小秩的树合并到较大秩的树中。如果秩相同，则合并后将秩加
1。 -
connected(p, q)：
- 判断
p和q是否在同一集合中，即检查它们是否有相同的根节点。
4. 示例输出
True
False
5. 优化和应用场景
- 路径压缩和按秩合并使得并查集操作的时间复杂度接近
O(1)，非常高效。 - 并查集广泛应用于处理动态连通性问题，例如网络中节点的连接、图中的连通分量、并查集在 Kruskal 算法中用于寻找最小生成树等。
这个数据结构在处理需要快速合并和查找操作的问题时非常有用。
11.3 LRU缓存机制
LRU（Least Recently Used）缓存机制是一种缓存淘汰策略，用于在缓存容量有限的情况下，淘汰最久未使用的数据，从而为新的数据腾出空间。
1. LRU 缓存机制的基本思想
LRU 缓存机制维护一个固定大小的缓存，当缓存满时，移除最久未使用的元素。常见的实现方式是使用一个哈希表配合一个双向链表：
- 哈希表（dict）：用于快速查找缓存中的数据。
- 双向链表：用于维护数据的使用顺序，最常用的元素放在链表头部，最不常用的元素放在链表尾部。
2. LRU 缓存的 Python 实现
Python 提供了 collections.OrderedDict，它是一个维护插入顺序的字典，可以用来实现 LRU 缓存。下面是一个简单的实现。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
# 将最近访问的键值对移到最前面
self.cache.move_to_end(key, last=False)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 更新键值对并移到最前面
self.cache.move_to_end(key, last=False)
self.cache[key] = value
if len(self.cache) > self.capacity:
# 弹出最久未使用的键值对（链表尾部元素）
self.cache.popitem(last=True)
# 示例使用
lru_cache = LRUCache(2)
lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1)) # 输出: 1
lru_cache.put(3, 3) # 淘汰键 2
print(lru_cache.get(2)) # 输出: -1 (未找到)
lru_cache.put(4, 4) # 淘汰键 1
print(lru_cache.get(1)) # 输出: -1 (未找到)
print(lru_cache.get(3)) # 输出: 3
print(lru_cache.get(4)) # 输出: 4
3. 代码解释
OrderedDict：OrderedDict是 Python 的一个有序字典，它按照键插入的顺序来维护元素。我们利用它来维护 LRU 缓存，其中键是缓存的元素，值是缓存的内容。move_to_end(key, last=False)：将指定键值对移动到字典的开头（last=False）或结尾（last=True）。在 LRU 缓存中，我们将最近访问的键值对移到字典的开头。-
popitem(last=True)：移除字典中最后一个元素。在 LRU 缓存中，这意味着删除最久未使用的键值对。 -
get(key)：获取缓存中的值。如果键存在，将其移到最前面（表示最近使用），并返回其对应的值；如果键不存在，返回-1。 -
put(key, value)：向缓存中添加一个键值对。如果键已经存在，更新其值并将其移到最前面。如果缓存已满，移除最久未使用的键值对。
4. 示例输出
1
-1
-1
3
4
5. 复杂度分析
- 时间复杂度：
get和put操作的时间复杂度均为O(1)，因为OrderedDict的插入、删除和移动操作都是O(1)的。 - 空间复杂度：空间复杂度为
O(capacity)，其中capacity是缓存的容量。
6. 应用场景
LRU 缓存机制广泛应用于操作系统的内存管理、数据库查询优化、Web 缓存等领域。它在需要管理有限资源并希望高效利用最近使用过的数据时非常有用。