算法🔨

有太多的天才程序员、知名学者、行业大佬，都或多或少写过算法相关的书籍。目前算法已经是每个程序员必备的技能之一，是进入大厂的第一道门槛。

本文面向初学者，由浅入深的给出一些算法题解，帮助你理解算法的基本概念和实现方式。

tip

本篇内容主要参考《算法图解》，后续推荐

• labuladong的算法笔记
• Algorithms

如果你对算法产生了浓厚的兴趣，可以去参加LeetCode竞赛，赢取属于你的Offer和奖品。

学习算法即在锻炼编程思维，是新老程序员都需要掌握的技能。

基础

大O表示法是一种表示算法时间复杂度的方法。它表示算法运行时间与输入规模之间的关系。

O(1) # 常数时间复杂度
O(log n) # 对数时间复杂度
O(n) # 线性时间复杂度
O(n log n) # 线性对数时间复杂度
O(n^2) # 平方时间复杂度

对于大O表示法，我们只需要关注最高次项并忽略系数。例如O(2n + 1)可以简化为O(n)。

请你完成下面的练习并给出其时间复杂度。

冒泡排序

描述

给定一个列表，请你对列表的元素进行排序。

示例：

输入: [13, 22, 6, 99, 11, 0]
输出: [0, 6, 11, 13, 22, 99]

输入: [13, 22, 6, 99, 11, 0]
输出: [0, 6, 11, 13, 22, 99]

题解

list1 = [13, 22, 6, 99, 11, 0]

for a in range(len(list1)):
    for b in range(a,len(list1)):
        if list1[a] < list1[b]:  #如果m大于了n
           list1[a] ,list1[b] =  list1[b],list1[a]#交换位置
print(list1)

二分查找

描述

给定一个有序列表和一个目标值，请你查找目标值在列表中的索引。如果目标值不存在，则返回-1。

arr = [1, 2, 6, 7, 8, 9, 10]
target = 6
输出: 2

arr = [1, 2, 6, 7, 8, 9, 10]
target = 0
输出: -1

题解

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

print(binary_search([1, 2, 6, 7, 8, 9, 10], 0))# -1
print(binary_search([1, 2, 6, 7, 8, 9, 10], 6))# 2

去重

给定一个有序的序列，请你在不创建新的空间的情况下，将序列中的重复元素去除。

输入: [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
输出: [1, 2, 3, 4]

题解

def remove_duplicates(arr):
    """
    通过两个指针将重复元素移到一侧，然后切片
    :param arr: 待去重的序列
    :return: 去重后的序列
    """
    slow = 0 # 指向的永远是最后一个不重复元素的位置
    fast = 1 # 指向当前遍历的元素
    for fast in range(1, len(arr)):
        # 不相等则说明新的不重复元素出现
        if arr[slow] != arr[fast]:
            # 将新的不重复元素赋值给慢指针之后的位置
            slow += 1
            arr[slow] = arr[fast]
    return arr[:slow + 1]

分治

分治法是一种将问题分解为更小的子问题，然后解决子问题，最后合并子问题结果的算法。

快速排序

描述

快速排序（Quicksort）是对冒泡排序的一种改进算法。

该算法的实现基本可分为以下几步：

在数组中选一个基准数（通常为数组第一个）。 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

请你编写它的实现代码。

题解

def quick_sort(arr):
    """
    快速排序
    :param arr: 待排序的List
    :return: 排序后的List
    """
    # 递归结束条件：如果列表长度小于等于1，直接返回
    if len(arr) <= 1:
        return arr
    
    # 创建左右2个空列表
    left = []
    right = []
    
    # 选择一个选中值（pivot），选择第一个元素
    pivot = arr[0]
    
    # 将元素分配到左右列表
    for i in range(1, len(arr)):
        if arr[i] <= pivot:  # 小于等于pivot的元素放入左列表
            left.append(arr[i])
        else:  # 大于pivot的元素放入右列表
            right.append(arr[i])
    
    # 递归排序左右两部分，并合并结果
    return quick_sort(left) + [pivot] + quick_sort(right)

# 测试数据
if __name__ == '__main__':
    arr = [17, 56, 71, 38, 61, 62, 48, 28, 57, 42, 10, 21, 12, 90]  # 长度为14
    sorted_arr = quick_sort(arr)
    print("快速排序结果：", sorted_arr)

密码组合

描述

Python中的string模块包含了许多字符，请根据以下提示设计一个函数：

参数1：密码可用字符的列表 参数2：密码的长度 输出：一个符合要求的所有的密码组合

题解

def set_password(chars, length):
    passwords = []
    def get_password(char, length):
        if len(char) == length:  # 修复：检查当前密码长度，而不是字符集长度
            passwords.append(char)  # 修复：添加当前构建的密码，而不是字符集
            return
        for i in chars:
            get_password(char + i, length)
    get_password("", length)
    return passwords

print(set_password(['a', 'b', 'c'], 2))# ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
print(set_password(['a', 'b', 'c'], 3))# ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

括号组合

描述

给定一个数字n，请你生成所有可能的括号组合

题解

def generate_parenthesis(n):
    def backtrack(s, left, right):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)

    result = []
    backtrack('', 0, 0)
    return result

print(generate_parenthesis(3))# ['((()))', '(()())', '(())()', '()(())', '()()()']  

质数分解

描述

每个数字可以写成多个质数的乘积，给定一个数字，请你分解为多个质数

题解

def fun(num, list=None):
    if list is None:
        list = []
    for i in range(2, num):
        while num % i == 0:
            list.append(i)
            num = int(num / i)
            if num > 1:
                fun(num)
    return list
x = 9*5
print(fun(x))# [3, 3, 5]

图

最少换乘

描述

假设你要从起点去往终点，路上有多个单向站点，怎么设计一个算法，找到最少换乘的路线？

这是一个经典的图论问题，可以用广度优先搜索（BFS）来解决。每条路线可以看作是一条边，换乘次数就是路径的边数。

图数据结构定义：

edges = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['D'],
    'D': [],
}

如下图所示：

思路

1. 找到起点能去的所有节点
2. 检查可去节点是否包含终点
3. 如果不包含则继续前往这些节点的可去节点
4. 使用广度优先搜索（BFS）确保找到的是最少换乘路线
5. 使用队列记录当前层级的节点，逐层扩展直到找到终点

题解

def min_transfers(edges, start, end):
    """
    找到从起点到终点的最少换乘路线
    
    :param edges: 图的邻接表表示，edges[u] = [v1, v2, ...] 表示从u可以到达的站点
    :param start: 起点
    :param end: 终点
    :return: 最少换乘次数和路径，如果无法到达返回-1和None
    """
    if start == end:
        return 0, [start]
    
    # BFS队列，存储(当前站点, 换乘次数, 路径)
    queue = [(start, 0, [start])]
    visited = {start}  # 已访问的站点
    
    # 只要队列不为空，就继续遍历
    while queue:
        # 获取队列中最左侧（最左边是第一个进入队列的元素）元素，并从队列中删除
        # 当前站点, 换乘次数, 路径
        current, transfers, path = queue.pop(0)
        
        # 遍历所有可达的下一个站点(即当前站点可去的站点)
        # 如果当前站点没有下一个站点，则跳过
        # 如果当前站点有下一个站点，则将下一个站点加入队列
        for next_station in edges.get(current, []):
            if next_station == end:
                # 找到终点
                return transfers + 1, path + [end]
            # 如果下一个站点没有被访问过，则将下一个站点加入已访问集合，并加入队列
            # 这一步可以避免重复访问同一个站点，提升算法效率
            if next_station not in visited:
                # 将下一个站点加入已访问集合
                visited.add(next_station)
                # 将下一个站点加入队列
                # 换乘次数加1，路径加上下一个站点
                queue.append((next_station, transfers + 1, path + [next_station]))
    
    # 无法到达终点
    return -1, None

# 测试数据
if __name__ == '__main__':
    # 示例：站点A->B->D, A->C->D, A->D
    edges = {
        'A': ['B', 'C'],
        'B': ['C'],
        'C': ['D'],
        'D': []
    }
    
    transfers, path = min_transfers(edges, 'A', 'D')
    print(f"最少换乘次数: {transfers}")
    print(path)  

最少价格路径

描述

给定一个带权有向图，每条边都有一个价格（权重），请找到从起点到终点的价格总和最小的路径。

这是一个典型的单源最短路径问题，可以使用Dijkstra算法来解决（假设所有边权非负）。

图数据结构定义：

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

如下图所示：

虽然A -> B -> D 或 A -> C -> D 的路径最短，但价格较高。

其中沿着A -> B -> C -> D 的路径，价格总和最小，为1 + 2 + 1 = 4。

思路

1. 初始化起点的距离为0，其他所有节点距离为无穷大
2. 找到起点能去的所有节点，计算到达这些节点的价格
3. 选择价格最小的节点作为下一个访问节点
4. 检查该节点的可去节点，更新到达这些节点的最少价格
5. 重复步骤3-4，直到访问到终点或所有可达节点都访问完毕
6. 使用优先队列（堆）来快速找到价格最小的节点

题解

def dijkstra(graph, start, end):
    """
    使用Dijkstra算法找到从起点到终点的最少价格路径
    
    :param graph: 图的邻接表表示，graph[u] = [(v1, weight1), (v2, weight2), ...]
    :param start: 起点
    :param end: 终点
    :return: 最少价格和路径，如果无法到达返回-1和None
    """
    # 初始化节点信息字典：每个节点包含价格、前驱节点等信息
    nodes = {}
    processed = set()  # 已处理的节点集合
    
    # 获取所有节点
    # 1. 获取所有节点放入 集合，集合具有去重的特点
    all_nodes = set(graph.keys())
    # 2. 获取所有邻居节点
    for neighbors in graph.values():
        for neighbor, _ in neighbors:
            all_nodes.add(neighbor) # 将邻居节点加入所有节点集合
    
    # 步骤1：初始化起点的距离为0，其他所有节点距离为无穷大
    for node in all_nodes:
        nodes[node] = {
            'price': 0 if node == start else float('inf'),
            'previous': None # 前一个节点
        }
    """
    all_nodes = {'A', 'B', 'C', 'D'}

    nodes = {'A': {'price': 0, 'previous': None},
     'D': {'price': inf, 'previous': None}, 
     'C': {'price': inf, 'previous': None}, 
     'B': {'price': inf, 'previous': None}}
    """
    
    def find_lowest_price_node():
        """在所有未处理的节点中，找到价格最小的节点"""
        lowest_price = float('inf')
        lowest_price_node = None
        for node_name, node_info in nodes.items():
            # 依次取出每个节点，并检查其价格是否小于最低价格
            # 初始选择中，除了起点是0，其他都是无穷大，所以一定会选择起点
            if node_name not in processed:  # 只从未处理的节点中查找
                cost = node_info['price']
                if cost < lowest_price:
                    lowest_price = cost
                    lowest_price_node = node_name
        return lowest_price_node
    
    # 步骤3-5：重复选择价格最小的节点，更新其邻居节点的价格
    node = find_lowest_price_node()  # 在所有未处理的节点中，找到价格最小的节点
    
    while node is not None:  # 只要存在未处理的节点，就继续循环

        # 如果到达终点，可以提前结束（可选优化）
        if node == end:
            break
            
        price = nodes[node]['price']  # 当前节点的价格
        
        # 步骤2和4：找到当前节点能去的所有节点，计算到达这些节点的价格
        neighbors = graph.get(node, [])  # 当前节点的邻居（从图的邻接表中获取）
        for neighbor_name, edge_weight in neighbors:  # 遍历当前节点的邻居
            # 计算到达邻居的价格 = 当前节点价格 + 边权重
            new_price = price + edge_weight
            # 如果到达邻居的价格比当前价格更小，则更新邻居的价格
            if new_price < nodes[neighbor_name]['price']:
                nodes[neighbor_name]['price'] = new_price  # 更新邻居的价格
                nodes[neighbor_name]['previous'] = node  # 更新邻居的前一个节点
        
        processed.add(node)  # 将当前节点标记为已处理
        node = find_lowest_price_node()  # 在所有未处理的节点中，找到价格最小的节点
    
    # 检查是否能到达终点
    if nodes[end]['price'] == float('inf'):
        return -1, None
    
    # 重建路径
    def get_path(node_name):
        """根据前驱节点重建路径"""
        path = []
        current = node_name
        while current is not None:
            path.append(current)
            current = nodes[current]['previous']
        path.reverse()
        return path if path else None
    
    path = get_path(end)
    return nodes[end]['price'], path


# 测试数据
if __name__ == '__main__':
    # 示例图：A->B(1), B->C(2),
    #                 B->D(5),
    #       A->C(4),  C->D(1)
    graph = {
        'A': [('B', 1), ('C', 4)],
        'B': [('C', 2), ('D', 5)],
        'C': [('D', 1)],
        'D': []
    }
    
    price, path = dijkstra(graph, 'A', 'D')
    print(f"最少价格: {price}")
    print(f"路径: {' -> '.join(path)}")  # 最少价格: 4, 路径: A -> B -> C -> D

树

树是一种特殊的图，没有环路。其中更特殊的是二叉树。二叉树是一种每个节点最多有两个子节点的树。

其中左子节点及其所有子节点称为左子树，右子节点及其所有子节点称为右子树。

树兼顾了数组与链表的优点，即可以快速访问任意元素，又可以快速插入和删除元素。

BST树满足普通二叉树的条件，同时：左子节点与左子树总是比父节点要小，右子节点与右子树总是比父节点要大。

假设其根节点为：10 ，左节点为5，右节点为20 则表示为：[10, 5, 20]

如果5有左节点为2，右节点为7。20没有左节点，有右节点为25。则表示为：[10, 5, 20, 2, 7, None,25]

如下图所示：

这棵树从根节点出发，到任意子节点，最多只有两条边。所以树的高度为2。

同样的这组数据，也可绘制以25为根节点的树，所有比25小的都在左侧，但是这样树会很高（去往左侧节点需要走很多步）。

如下图所示：

这棵树高度为5，所有节点都形成了一条链，访问最左侧的节点2需要经过5步，效率很低。

AVL树是一种平衡二叉树，它保证树的左右节点尽量平衡，即左右子树的高度差不超过1。

在上面不平衡的树中，你可以把位于中间的节点10或者节点7，这样可以把树大致对折。持续对折所有节点，直到所有节点都高度差不超过1为止。

info

在AVL树中，每个节点存储一个平衡因子，如果仅有左子树或仅有右子树，则平衡因子为1或-1。如果左右子树都有，则平衡因子和为0。

如果左子树还有左子树，没有右子树，则总平衡因子为2，其绝对值大于1。此时需要进行左旋转。

如果右子树还有右子树，没有左子树，则总平衡因子为-2，其绝对值大于1。此时需要进行右旋转。

叶子节点由于没有子节点，所以平衡因子为0。

每当数据被插入，其可以通过O(logn)时间复杂度找到插入位置。

然后对每个父节点更新其平衡因子（父节点数量小于logn）。如果发生不平衡，则最多进行1次旋转操作，即可恢复平衡（常量操作）。

所以插入操作的时间复杂度为：

O(logn) + O(logn) + O(1) = 2O(logn)

大O表示法中，常量可以忽略不计，所以插入操作的时间复杂度为：O(logn)。

tip

另一种是伸展树，其访问性能很高，每次访问后，会将访问节点移动到根节点，从而提高后续访问性能。

其工作原理是：你在伸展树中查找过一次节点后，会将该节点移动到根节点，后续再次访问该节点时，可以一瞬间找到该节点。

所有经常访问的节点，都可以会聚集在根节点附近，从而提高访问性能。代价是无法保持自平衡，偶尔访问很偏远的节点，需要更多的时间。

但在大部分情况下，伸展树的访问性能很高，可以接受。

B树是一种广义的二叉树，其每个节点可以有多个子节点，每个节点可以有多个键值。主要用于数据库索引。

在计算机真实进行数据库检索时，需要移动物理部件到指定位置，这称为寻道。

寻道时间非常长，好比你去超市买东西，假设你从家走到超市买了一个面包，然后从超市走到家，发现也许应该再买一瓶水。往返很耗时。

B树的理念是：既然都去超市了，不如把这个超市的东西都加载到内存里。免得反复寻道。所以B树的子节点更多。

B+树是B树的一种变种和改进，在数据库系统中应用更加广泛。B+树与B树的主要区别在于：

1. 数据存储位置：

   • B树：内部节点既存储键值，也存储实际数据
   • B+树：只有叶子节点存储实际数据，内部节点只存储键值和指向子节点的指针

2. 叶子节点结构：

   • B+树的叶子节点通过指针相互连接，形成有序链表
   • 这使得范围查询和顺序访问非常高效

3. 树的高度：

   • 由于B+树内部节点不存储数据，在相同数据量下，B+树通常比B树更矮
   • 更少的层级意味着更少的磁盘I/O操作

4. 查询性能：

   • 对于精确查询，B树和B+树性能相近
   • 对于范围查询，B+树性能明显优于B树，因为可以通过叶子节点的链表顺序访问

继续用超市的比喻：B+树就像是在超市门口放了一个目录架，目录架上只写了商品类别和对应的货架编号（内部节点存储键值），而实际的商品（数据）都放在货架上（叶子节点）。当你想找某个商品时，先看目录找到货架位置，然后直接去货架拿商品。如果你要买多个同类商品，可以在同一个货架上依次拿取，非常方便。

由于B+树这些优势，大多数现代数据库系统（如MySQL的InnoDB引擎、PostgreSQL等）都采用B+树作为索引结构，特别适合处理大量的范围查询和排序操作。

接下来，请你根据深度优先和广度优先，分别遍历出下面的B树的所有节点。

我们以之前提到的BST树为例：[10, 5, 20, 2, 7, None, 25]

树的结构如下：

        10
       /  \
      5    20
     / \   / \
    2   7 None 25

深度优先(DFS)

深度优先遍历有三种方式：前序遍历、中序遍历、后序遍历。

1. 前序遍历（根-左-右）

访问顺序：先访问根节点，再访问左子树，最后访问右子树。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_traversal(root):
    """前序遍历：根-左-右"""
    result = []
    
    def dfs(node):
        if node is None:
            return
        result.append(node.val)  # 先访问根节点
        dfs(node.left)           # 再访问左子树
        dfs(node.right)          # 最后访问右子树
    
    dfs(root)
    return result

# 构建树：[10, 5, 20, 2, 7, None, 25]
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(20)
root.left.left = TreeNode(2)
root.left.right = TreeNode(7)
root.right.right = TreeNode(25)

print("前序遍历结果:", preorder_traversal(root))
# 输出: [10, 5, 2, 7, 20, 25]

2. 中序遍历（左-根-右）

访问顺序：先访问左子树，再访问根节点，最后访问右子树。对于BST树，中序遍历的结果是有序的。

def inorder_traversal(root):
    """中序遍历：左-根-右"""
    result = []
    
    def dfs(node):
        if node is None:
            return
        dfs(node.left)           # 先访问左子树
        result.append(node.val)  # 再访问根节点
        dfs(node.right)          # 最后访问右子树
    
    dfs(root)
    return result

print("中序遍历结果:", inorder_traversal(root))
# 输出: [2, 5, 7, 10, 20, 25]  (BST树中序遍历是有序的)

3. 后序遍历（左-右-根）

访问顺序：先访问左子树，再访问右子树，最后访问根节点。

def postorder_traversal(root):
    """后序遍历：左-右-根"""
    result = []
    
    def dfs(node):
        if node is None:
            return
        dfs(node.left)           # 先访问左子树
        dfs(node.right)          # 再访问右子树
        result.append(node.val)  # 最后访问根节点
    
    dfs(root)
    return result

print("后序遍历结果:", postorder_traversal(root))
# 输出: [2, 7, 5, 25, 20, 10]

广度优先(BFS)

广度优先遍历（层序遍历）使用队列实现，按照从上到下、从左到右的顺序访问节点。

from collections import deque

def bfs_traversal(root):
    """广度优先遍历（层序遍历）"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        # 将左右子节点加入队列
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

print("广度优先遍历结果:", bfs_traversal(root))
# 输出: [10, 5, 20, 2, 7, 25]

按层输出（每层单独一行）

def level_order_traversal(root):
    """按层输出，每层单独一个列表"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # 当前层的节点数
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

print("按层遍历结果:", level_order_traversal(root))
# 输出: [[10], [5, 20], [2, 7, 25]]

贪心

贪心算法是一种寻找局部最优解的算法。它每次选择当前最优解，直到找到全局最优解。

集合覆盖

每个广播站都覆盖一个或者多个州市，广播站的覆盖范围可能会有重复。如何设计一个算法，找到最少广播站，覆盖所有州市？

这是一个典型的集合覆盖问题，可以使用贪心算法来解决。

贪婪算法寻找局部最优解，可能不是全局最优解（例如背包问题），但通常情况下，贪婪算法的结果已经足够接近最优解。

数据示例：

stations = {
    'kone': {'id', 'nv', 'ut'},
    'ktwo': {'wa', 'id', 'mt'},
    'kthree': {'or', 'nv', 'ca'},
    'kfour': {'nv', 'ut'},
    'kfive': {'ca', 'az'},
}

思路

正确的解可能有多个，你需要遍历所有未选择的广播站，从中选择一个最多未覆盖的广播站。

题解

stations = {
    'kone': {'id', 'nv', 'ut'},
    'ktwo': {'wa', 'id', 'mt'},
    'kthree': {'or', 'nv', 'ca'},
    'kfour': {'nv', 'ut'},
    'kfive': {'ca', 'az'},
}

# 最终选择的广播站
final_stations = set()

# 获取所有州
states_needed = set.union(*stations.values())
print(states_needed)
# {'mt', 'az', 'nv', 'wa', 'id', 'ut', 'ca', 'or'}

# 如果还有未覆盖的州，则继续选择最好的广播站
while states_needed :
    # 当前最好的选择
    best_station = None
    # 当前最好的选择覆盖的州
    states_covered = set()
    for station, states in stations.items():
        # 计算当前广播站与还需覆盖的州的交集
        covered = states & states_needed
        # 如果此交集比 states_covered 大，
        if len(covered) > len(states_covered):
            # 则更新当前最好的选择
            best_station = station
            # 则更新覆盖的州为当前交集
            states_covered = covered
    # 需要覆盖的州减去当前最好的选择的覆盖的州
    states_needed -= states_covered
    # 将当前最好的选择添加到最终选择的广播站中
    print(best_station)
    final_stations.add(best_station)
"""
kone
ktwo
kthree
kfive
"""

动态规划

背包问题

假设你有一个4磅的背包，需要在容量范围内，选择总价值最高的物品放入背包。

items = {
    "音响":{'重量':4, '价值':3000},
    "笔记本电脑":{'重量':3, '价值':2000},
    "吉他":{'重量':1, '价值':1500},
    "iphone":{'重量':1, '价值':2000},
}

暴力求解的复杂度为$2^n$，其中n是物品数量。

思路

这题属于动态规划问题，首先定义一个二维表格。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	A
笔记本电脑	0
吉他	0
iphone	0

• 横向增加说明在当前可选择的物品中，背包容量增加。
• 纵向增加说明在当前背包容量下，可选择的物品增加。
• 由于无物品时再多的空间也没有物品可选，所以最大价值都为0。即第一行都为0。
• 由于空间为0时，有再多的物品可选也放不下，所以最大价值都为0。即第一列都为0。

这个表格的左上角的A格子表示：当只有音响可以选择时，且背包容量为1时，可选的最大价值。所以我们可以从左上角的A格子开始，逐步填充表格。

由于音响的重量为4，所以当背包容量为1 ~ 3时，无法选择音响。最大价值为0。当背包容量为4时，可以选择音响，最大价值为3000。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0
吉他	0
iphone	0

当来到第二行时，可以选择笔记本电脑或音响。其中笔记本电脑重量为3，所以当背包容量为1 ~ 2时，无法选择笔记本电脑。最大价值为0。

当背包容量为3时，可以选择笔记本电脑，最大价值为2000。当背包容量为4时，可以选择笔记本电脑或音响，由于音响的价值更高，所以选择音响，最大价值为3000。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0
iphone	0

当来到第三行时，可以选择吉他、笔记本电脑或音响。

当背包重量为1~2时，选吉他，最大价值为1500。不选则为0。所以应该选择，此时最大价值为1500。

你会发现从上往下，每行都比上一行多一个物品。且对应的最大价值不会变小（只会变大或者与上一行相等）

目前已经更新的表的最后一行，就表示当前容量下，可选物品的最大价值。

且从左向右，每列都比前一格容量更多，所以对应的最大价值也不会变小（只会变大或者与上一行相等）

最终右下角的值，就是整个表最大的值之一（因为可能会有多个相等的最大值）

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	X	Y
iphone	0

当填写 "X" 时，我们向上数一格，发现没有新增当前行的物品可选时，容量为3时，历史最佳价值是2000。

如果选了吉他（1500），剩余空间为2，则无法选择其他物品，所以最大价值为1500。

2000 > 1500，所以填写2000。

当填写 "Y" 时，我们向左看，发现"Y"只比左侧的"X"增加一个空间。向上看，发现之前的最佳选择是3000。

所以我们选了当前行的物品（吉他），剩余空间为3，排除吉他（向上走一行）历史上空间为3的最佳选择是2000。所以最大价值为2000 + 1500 = 3500。

没有新增当前行的物品可选时，容量为3时，历史最佳价值是3000。

所以取两者中的最大值，所以应该填 3500

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	2000	3500
iphone	0

最后一层，我们尝试编写伪代码

每下移一行，我们就会多了一个物品可以选择。所以这一行的每个判断都是围绕着是否选择这个新增物品展开的。

首先判断当前背包空间是否大于等于这个物品的空间。如果是否则直接沿用上一列对应格子的值。

其次判断如果比当前物品大，是否选择：

如果选择这个物品，最大价值 = 当前物品价值 + 表格[前一行][（当前背包空间-物品空间）的值]

如果不选择这个物品，最大价值 = 表格[前一行][当前背包空间的值]

我们来试一下：

当前容量 = 1

当前背包空间是否大于等于这个物品的空间？ 1 >=1 ——> 是

如果选择这个物品：

最大价值 = 当前物品价值（2000） + 表格[前一行][（当前背包空间-物品空间）的值]（0） = 2000

如果不选择这个物品：

最大价值 = 表格[前一行][当前背包空间的值]（1500） = 1500

所以应该选择这个物品，最大价值为2000。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	2000	3500
iphone	0	2000

当前容量 = 2

当前背包空间是否大于等于这个物品的空间？ 2 >=1 ——> 是

如果选择这个物品：

最大价值 = 当前物品价值（2000） + 表格[前一行][（当前背包空间-物品空间）的值]（1500） = 3500

如果不选择这个物品：

最大价值 = 表格[前一行][当前背包空间的值]（1500） = 1500

所以应该选择这个物品，最大价值为3500。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	2000	3500
iphone	0	2000	3500

当前容量 = 3

当前背包空间是否大于等于这个物品的空间？ 3 >=1 ——> 是

如果选择这个物品：

最大价值 = 当前物品价值（2000） + 表格[前一行][（当前背包空间-物品空间）的值]（1500） = 3500

如果不选择这个物品：

最大价值 = 表格[前一行][当前背包空间的值]（2000） = 2000

所以应该选择这个物品，最大价值为3500。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	2000	3500
iphone	0	2000	3500	3500

当前容量 = 4

当前背包空间是否大于等于这个物品的空间？ 4 >=1 ——> 是

如果选择这个物品：

最大价值 = 当前物品价值（2000） + 表格[前一行][（当前背包空间-物品空间）的值]（2000） = 4000

如果不选择这个物品：

最大价值 = 表格[前一行][当前背包空间的值]（3500） = 3500

所以应该选择这个物品，最大价值为4000。

物品名称	0	1	2	3	4
无物品	0	0	0	0	0
音响	0	0	0	0	3000
笔记本电脑	0	0	0	2000	3000
吉他	0	1500	1500	2000	3500
iphone	0	2000	3500	3500	4000

最后的最大值一定在左下角。（可能出现多个相等的最大值）

外层是嵌套循环：先逐行遍历物品，再逐列遍历背包空间。

内层是嵌套判断：空间是否大于等于当前物品的空间，如果大于等于则判断是否选择当前物品。

题解

items = {
    "音响": {'重量': 4, '价值': 3000},
    "笔记本电脑": {'重量': 3, '价值': 2000},
    "吉他": {'重量': 1, '价值': 1500},
    "iphone": {'重量': 1, '价值': 2000},
}
# 背包最大容量
max_weight = 4
# 物品名称
names = list(items.keys())

# 行：物品个数，列：当前背包容量（1~max_weight）
rows = len(names)
cols = max_weight

# dp[i][w] 表示：在前 i 个物品中选择，容量为 w 时的最大价值
dp = [[0] * (cols + 1) for _ in range(rows + 1)]

# 为了让我们使用统一的状态转移方程，我们多生成了一列0和一行0，便于我们使用统一的状态转移方程。
# 表示当没有物品或没有背包空间时，最大价值为0。
# 下图中我用0.0 将其特殊标注出来
# 你从A开始逐行填写，填到Z
"""
[[0.0, 0.0, 0.0, 0.0, 0.0],
 [0.0, A, 0, 0, 0],
 [0.0, 0, 0, 0, 0],
 [0.0, 0, 0, 0, Z]]
"""
for i in range(1, rows + 1):
    name = names[i - 1]
    weight = items[name]['重量']
    value = items[name]['价值']
    # 判断当前行的每一个背包空间是否应该选择这个物品
    for w in range(1, cols + 1):
        # 首先判断当前背包空间是否大于等于这个物品的空间
        if w < weight:
            # 如果否，则直接沿用上一行对应格子的值
            dp[i][w] = dp[i - 1][w]
        else:
            # 如果是，则围绕「是否选择这个新增物品」展开判断
            # 选择这个物品：当前物品价值 + 表格[前一行][当前背包空间-物品空间]
            choose = value + dp[i - 1][w - weight]
            # 不选择这个物品：表格[前一行][当前背包空间]
            not_choose = dp[i - 1][w]
            # 取两者中的最大值
            dp[i][w] = max(choose, not_choose)

# 打印表格，便于和上面的推导对照
header = ["物品名称"] + [str(w) for w in range(1, cols + 1)]
print("\t".join(header))
for i in range(1, rows + 1):
    row_name = names[i - 1]
    values = [str(dp[i][w]) for w in range(1, cols + 1)]
    print(row_name + "\t" + "\t".join(values))

# 最右下角就是最大价值
max_value = dp[rows][cols]
print("最大总价值：", max_value)

最长公共子串

当用户输入"hish"时，下面三个单词哪个更有可能是用户真正输入的单词？

• fish
• vista
• hsih（原单词的反转）

我们希望找到：哪个单词和 hish 之间有“最长的公共子串”（连续、顺序一致的公共部分），这个单词就更有可能是用户真正想输的。

思路

这题是不能用集合取交集判断长度来解决的。

因为用户输入的单词是"hish"，而单词"hsih"是原单词的反转。取集合交集判断虽然最长，但是交集不判断顺序。

最长公共子串要求顺序也一致的公共子字符串。

我们可以用动态规划来解决这个问题。

字符串	h	i	s	h
f	0(左上角)	0	0	0
i	0	0+1=1
s
h

如果两个字母不相同，则标记0 , 由于 f 和 ['h', 'i', 's', 'h'] 每个字母都不相同，所以标记0。

如果两个字母相同，值为右上角的邻居的值 + 1

为了让每个点都有一个左上角，你依然可以在第一行前和第一列前补0

直到填满所有表格。表格最大值为3，说明最多有3个连续相同的字符串。

字符串	h	i	s	h
f	0	0	0	0
i	0	1	0	0
s	0	0	2	0
h	0	0	0	3

接着我们把和hsih的表格也绘制出来。下表说明最多有1个连续相同的字符串。

字符串	h	i	s	h
h	1	0	0	1
s	0	0	1	0
i	0	1	0	0
h	1	0	0	1

接着我们把和vista的表格也绘制出来。下表说明最多有2个连续相同的字符串。

字符串	h	i	s	h
v	0	0	0	0
i	0	1	0	0
s	0	0	2	0
t	0	0	0	0
a	0	0	0	0

题解

# 用户输入的单词
user_word = "hish"

# 备选单词列表
candidates = ["fish", "vista", "hsih"]


def longest_common_substring_length(a, b):
    # 计算字符串 a 和 b 的最长公共子串长度（必须连续、顺序一致）

    # 行：字符串 a 的字符个数，列：字符串 b 的字符个数
    rows = len(a)
    cols = len(b)

    # dp[i][j] 表示：以 a 的第 i 个字符、b 的第 j 个字符结尾时
    # 它们的「最长公共后缀子串」的长度
    # 为了让每个点都有一个左上角，我们在前面额外补一行 0 和一列 0
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]

    # 记录当前遇到的最长公共子串长度
    longest = 0

    # 从第 1 行、第 1 列开始填表（第 0 行和第 0 列是我们人为补上的 0）
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            # 如果两个字符相同，就把左上角的值 + 1
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                # 顺便更新目前为止的最长公共子串长度
                longest = max(longest, dp[i][j])
            else:
                # 如果两个字符不同，根据「最长公共子串」的定义，这个格子只能是 0
                dp[i][j] = 0

    return longest


# 用上面的函数分别计算每个候选单词和用户输入之间的最长公共子串长度
result = {}
for word in candidates:
    # 每个候选单词和 user_word 的最长公共子串长度
    length = longest_common_substring_length(word, user_word)
    result[word] = length

# 找到最长公共子串长度最大的那个单词
best_word = max(result, key=result.get)
print("最有可能是用户真正输入的单词是：", best_word)

至此，你可以总结出动态规划的解题步骤：

• 确定维度？（在背包问题中是物品和背包空间 在最长公共子串问题中是原字符串和待比较字符串）
• 边界条件与初始值？（首行首列前补0）
• 状态转移方程是？（根据题目要求，确定状态转移方程，核心难点）
• 答案在哪？（背包问题中是右下角，最长公共子串问题中是表格最大值）

最长公共子序列

当用户输入"fosh"时，下面哪个更有可能是用户真正输入的单词？

• fort
• fish

思路

按照之前最长公共子串的思路，两个单词的最长公共子串都为2。

我们可以绘制出两个单词的表格：

字符串	f	o	s	h
f	1	0	0	0
o	0	2	0	0
r	0	0	0	0
t	0	0	0	0

字符串	f	o	s	h
f	1	0	0	0
i	0	0	0	0
s	0	0	1	0
h	0	0	0	2

但是fish和fosh的相似度更高，怎么修改状态转移方程，使得fish和fosh的相似度更高？

把状态转移方程改为：

• 如果两个字母不相同，则标记从左上角、上方和左方的值中取最大值^?

• 如果两个字母相同，值为右上角的邻居的值 + 1

字符串	-	f	o	s	h
-	0	0	0	0	0
f	0	1	1	1	1
o	0	1	2	2	2
r	0	1	2	2	2
t	0	1	2	2	2

表格最大值为2，说明最多有2个连续相同的字符串。

字符串	-	f	o	s	h
-	0	0	0	0	0
f	0	1	1	1	1
i	0	1	1	1	1
s	0	1	1	2	2
h	0	1	2	2	3

表格最大值为3，说明最多有3个连续相同的字符串。

题解

# 用户输入的单词
user_word = "fosh"

# 备选单词列表
candidates = ["fort", "fish"]


def longest_common_subsequence_length(a, b):
    # 计算字符串 a 和 b 的最长公共子序列长度（字符顺序一致，但不要求连续）

    # 行：字符串 a 的字符个数，列：字符串 b 的字符个数
    rows = len(a)
    cols = len(b)

    # dp[i][j] 表示：a 的前 i 个字符、b 的前 j 个字符之间
    # 能得到的「最长公共子序列」的长度
    # 为了让每个点都有一个左上角、上方和左方，我们在前面额外补一行 0 和一列 0
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]

    # 从第 1 行、第 1 列开始填表（第 0 行和第 0 列是我们人为补上的 0）
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            if a[i - 1] == b[j - 1]:
                # 如果两个字符相同，值为左上角的邻居的值 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 如果两个字符不同，则从「左上角、上方和左方」三者中取最大值
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

    # 整个表格的右下角，就是最长公共子序列的长度
    return dp[rows][cols]


# 用上面的函数分别计算每个候选单词和用户输入之间的最长公共子序列长度
result = {}
for word in candidates:
    # 每个候选单词和 user_word 的最长公共子序列长度
    length = longest_common_subsequence_length(word, user_word)
    result[word] = length

# 打印每个候选单词的最长公共子序列长度，方便对照
for word, length in result.items():
    print(f"{word} 和 {user_word} 的最长公共子序列长度为: {length}")

# 找到最长公共子序列长度最大的那个单词
best_word = max(result, key=result.get)
print("最有可能是用户真正输入的单词是：", best_word)

分类算法

KNN

这个算法既可以解决分类问题，也可以用于回归问题，但工业上用于分类的情况更多。

KNN 先记录所有已知数据，再利用一个距离函数，

找出已知数据中距离未知事件最近的 K 组数据，

最后按照这 K 组数据里最常见的类别预测该事件。

朴素贝叶斯

这个算法是建立在贝叶斯理论上的分类方法。

它的假设条件是自变量之间相互独立。

简言之，朴素贝叶斯假定某一特征的出现与其它特征无关。即给定类别，特征之间没有相关性。这个假设是“朴素”的来源。

比如说，如果一个水果它是红色的，圆状的，直径大概 7cm 左右，我们可能猜测它为苹果。即使这些特征之间存在一定关系，在朴素贝叶斯算法中我们都认为红色，圆状和直径在判断一个水果是苹果的可能性上是相互独立的。

一个二分类的案例假设:

我今天收到了 100 封邮件，其中有 80 封是垃圾邮件，20 封是正常邮件。

P（垃圾邮件） = 80/100 = 0.8
P（正常邮件） = 20/100 = 0.2

我选定了一些词作为特征，这些词可能出现在邮件中，也可能不出现。这些词有“免费”，“恭喜”，“辛苦”等。

我发现垃圾邮件中有 20 封含有“免费”这个词，50 封含有“恭喜”这个词，0 封含有“辛苦”这个词。

P（免费|垃圾邮件） = 20/80 = 0.25
P（恭喜|垃圾邮件） = 50/80 = 0.625
P（辛苦|垃圾邮件） = 0/80 = 0

正常邮件中有 5 封含有“免费”这个词。6 封含有“恭喜”这个词，2 封含有“辛苦”这个词。

P（免费|正常邮件） = 5/20 = 0.25
P（恭喜|正常邮件） = 6/20 = 0.3
P（辛苦|正常邮件） = 2/20 = 0.1

现在我收到了一封邮件，这封邮件内容为：“恭喜您获得了一次免费的机会”，我想知道这封邮件是垃圾邮件的概率是多少？

P（垃圾邮件|免费，恭喜） = P（免费|垃圾邮件）* P（恭喜|垃圾邮件）* P（垃圾邮件）= 0.25 * 0.625 * 0.8 = 0.125

P（正常邮件|免费，恭喜） = P（免费|正常邮件）* P（恭喜|正常邮件）* P（正常邮件）= 0.25 * 0.3 * 0.2 = 0.015

因为 P（垃圾邮件|免费，恭喜） > P（正常邮件|免费，恭喜），所以这封邮件被判定为垃圾邮件。

如果狡猾的垃圾邮件制造者把邮件内容改为：“恭喜您获得了一次免费的机会，辛苦您动动手指参加我们的免费活动”，那么这封邮件被判定为垃圾邮件的概率就会变成 0，因为“辛苦”这个词在正常邮件中有出现，在垃圾邮件中没有出现。

改进:拉普拉斯平滑法

在每个关键词上人为的增加一个出现的次数，这样就不会出现概率为 0 的情况了。（下面的公式免费的平方表示这个关键词出现 2 次）

P（垃圾邮件|免费，恭喜，辛苦） = P（免费|垃圾邮件）* P（恭喜|垃圾邮件）* P（辛苦|垃圾邮件）* P（垃圾邮件）= (20+1/80)² * (50+1/80) * (0+1/80) * 0.8 = 0.0351421875

P（正常邮件|免费，恭喜，辛苦） = P（免费|正常邮件）* P（恭喜|正常邮件）* P（辛苦|正常邮件）* P（正常邮件）= (5+1/20)² * (6+1/20) * (2+1/20) * 0.2 =0.012885

决策树

决策树是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。

决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-else 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。

聚类算法

聚类算法被广泛应用于数据搜索、样本分类中。想象你要在一个有100万本书的图书馆里，找到与你手中这本书最相似的5本书。如果一本一本地比较，你需要比较100万次。

向量数据库通过多次多层级聚类把相似的数据放在"附近"，建立不同层级，搜索时就像在分区清晰的图书馆中找书，快速到达目标区域。

例如可以把图书聚类为10类,判断当前图书距离哪类的质心最近，然后去该类中搜索。该类中又可以聚类为N类，再次判断当前图书距离哪类的质心最近，然后去该类中搜索。多次迭代指数级缩小搜索范围后，最后遍历对比距离即可。

当然，聚类对于边界模糊的数据效果不佳，例如你想找《明朝哪些年》，它既是小说，又是历史。很可能在某一层级距离计算错误，导致结果不准确。虽然可以通过分层聚类解决，但计算量会大大增加。

此外，聚类结构是基于当前数据快照构建的。当有新数据不断加入或旧数据被删除时，原有的聚类结构可能不再最优甚至失效。增量式更新聚类结构通常比全量重新聚类更复杂且效果可能打折扣。

K-means

这是一种解决聚类问题的非监督式学习算法。这个方法简单地利用了一定数量的集群（假设 K 个集群）对给定数据进行分类。同一集群内的数据点是同类的，不同集群的数据点不同类。

K 均值算法如何划分集群：

1. 随机从每个集群中选取 K 个数据点作为质心（centroids），因此同一组数据多次运行，分组结果可能不同。

2. 将每一个数据点与距离自己最近的质心划分在同一集群，即生成 K 个新集群。

3. 找出新集群的质心，这样就有了新的质心。

4. 重复 2 和 3，直到结果收敛，即不再有新的质心出现。

这样的算法基于距离和质心，天然倾向于发现球状或凸形的簇。对于流形、环形、相互缠绕或具有复杂边界的不规则形状的数据分布，效果往往不佳。可以考虑使用DBSCAN算法。

距离计算公式：

一维坐标系中,设 A(x1),B(x2),则 A,B 之间的距离为

$|AB|=\sqrt{(x1-x2)^2}$

二维坐标系中,设 A(x1,y1),B(x2,y2),则 A,B 之间的距离为

$|AB|=\sqrt{(x1-x2)^2+(y1-y2)^2}$

三维坐标系中,设 A(x1,y1,z1),B(x2,y2,z2),则 A,B 之间的距离为

$|AB|=\sqrt{(x1-x2)^2+(y1-y2)^2+(z1-z2)^2}$

以此类推

动画演示

下面的动画使用10*10的网格模拟图片，通过修改网格颜色表示分类。

通过绿色表示样本分类1，深绿色表示其簇中心点，蓝色表示样本分类2，深蓝色表示其簇中心点。

初始簇中心点1在左上角，簇中心点2在中间。

每次迭代停顿5秒。

点击查看动画

Live Editor

function KMeansAnimation() {
  const gridSize = 10;
  
  const [dataPoints, setDataPoints] = React.useState([]);
  const [centroids, setCentroids] = React.useState([
    { x: 0, y: 0 },
    { x: 5, y: 5 }
  ]);
  const [step, setStep] = React.useState(0);
  const [iteration, setIteration] = React.useState(0);
  const [ready, setReady] = React.useState(false);
  
  React.useEffect(() => {
    const generateAllGridPoints = () => {
      const points = [];
      for (let i = 0; i < gridSize; i++) {
        for (let j = 0; j < gridSize; j++) {
          points.push({
            x: i,
            y: j,
            cluster: null
          });
        }
      }
      return points;
    };
    
    setDataPoints(generateAllGridPoints());
    
    // 初始化后等待5秒再开始第一次迭代
    const initialTimer = setTimeout(() => {
      setReady(true);
    }, 5000);
    
    return () => clearTimeout(initialTimer);
  }, []);
  
  const distance = (point1, point2) => {
    return Math.sqrt(Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2));
  };
  
  React.useEffect(() => {
    if (dataPoints.length === 0 || !ready) return;
    
    const timer = setTimeout(() => {
      if (step === 0) {
        const newDataPoints = dataPoints.map(point => {
          const dist1 = distance(point, centroids[0]);
          const dist2 = distance(point, centroids[1]);
          return {
            ...point,
            cluster: dist1 <= dist2 ? 0 : 1
          };
        });
        setDataPoints(newDataPoints);
        setStep(1);
      } else if (step === 1) {
        const cluster0Points = dataPoints.filter(p => p.cluster === 0);
        const cluster1Points = dataPoints.filter(p => p.cluster === 1);
        
        if (cluster0Points.length > 0 && cluster1Points.length > 0) {
          const newX0 = Math.round(cluster0Points.reduce((sum, p) => sum + p.x, 0) / cluster0Points.length);
          const newY0 = Math.round(cluster0Points.reduce((sum, p) => sum + p.y, 0) / cluster0Points.length);
          
          const newX1 = Math.round(cluster1Points.reduce((sum, p) => sum + p.x, 0) / cluster1Points.length);
          const newY1 = Math.round(cluster1Points.reduce((sum, p) => sum + p.y, 0) / cluster1Points.length);
          
          setCentroids([
            { x: newX0, y: newY0 },
            { x: newX1, y: newY1 }
          ]);
        }
        
        setStep(0);
        setIteration(prev => prev + 1);
        
        // 每次迭代完成后暂停5秒
        setReady(false);
        setTimeout(() => {
          setReady(true);
        }, 5000);
      }
    }, 1000);
    
    return () => clearTimeout(timer);
  }, [step, dataPoints, centroids, ready]);
  
  const renderGrid = () => {
    const grid = [];
    
    for (let y = 0; y < gridSize; y++) {
      for (let x = 0; x < gridSize; x++) {
        const pointAtPosition = dataPoints.find(p => p.x === x && p.y === y);
        
        const isCentroid0 = centroids[0].x === x && centroids[0].y === y;
        const isCentroid1 = centroids[1].x === x && centroids[1].y === y;
        
        let cellStyle = {
          width: '32px',
          height: '32px',
          border: '1px solid #cbd5e0',
          display: 'flex',
          alignItems: 'center',
          justifyContent: 'center'
        };
        
        if (pointAtPosition) {
          if (pointAtPosition.cluster === 0) {
            cellStyle.backgroundColor = '#9ae6b4';
          } else if (pointAtPosition.cluster === 1) {
            cellStyle.backgroundColor = '#90cdf4';
          }
        }
        
        if (isCentroid0) {
          cellStyle.backgroundColor = '#276749';
        } else if (isCentroid1) {
          cellStyle.backgroundColor = '#2b6cb0';
        }
        
        grid.push(
          <div key={`${x}-${y}`} style={cellStyle}></div>
        );
      }
    }
    
    return grid;
  };
  
  return (
    <div style={{display: 'flex', flexDirection: 'column', alignItems: 'center', padding: '16px'}}>
      <h2 style={{fontSize: '1.25rem', fontWeight: 'bold', marginBottom: '16px'}}>K-Means 聚类算法可视化</h2>
      <div style={{marginBottom: '16px'}}>
        迭代次数: {iteration}
        {!ready && <span style={{marginLeft: '10px', color: '#718096'}}>等待中...</span>}
      </div>
      <div style={{
        display: 'grid',
        gridTemplateColumns: 'repeat(10, 1fr)',
        gap: '4px',
        marginBottom: '16px'
      }}>
        {renderGrid()}
      </div>
      <div style={{marginTop: '16px', display: 'flex', gap: '24px'}}>
        <div style={{display: 'flex', alignItems: 'center'}}>
          <div style={{width: '16px', height: '16px', backgroundColor: '#9ae6b4', marginRight: '8px'}}></div>
          <span>簇1数据点</span>
        </div>
        <div style={{display: 'flex', alignItems: 'center'}}>
          <div style={{width: '16px', height: '16px', backgroundColor: '#276749', marginRight: '8px'}}></div>
          <span>簇1中心点</span>
        </div>
        <div style={{display: 'flex', alignItems: 'center'}}>
          <div style={{width: '16px', height: '16px', backgroundColor: '#90cdf4', marginRight: '8px'}}></div>
          <span>簇2数据点</span>
        </div>
        <div style={{display: 'flex', alignItems: 'center'}}>
          <div style={{width: '16px', height: '16px', backgroundColor: '#2b6cb0', marginRight: '8px'}}></div>
          <span>簇2中心点</span>
        </div>
      </div>
    </div>
  );
}

Result

Loading...

DBSCAN

这是一种基于密度的聚类算法，用于解决聚类问题的非监督式学习算法。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）能够自动发现任意形状的簇，并识别噪声点，无需预先指定簇的数量。使用之前确保数据量足够多，否则效果不佳。

DBSCAN算法相比K-means的优势：

• 无需预设簇数量：算法自动确定簇的数量
• 发现任意形状的簇：不局限于球形或凸形，能处理复杂形状的数据分布
• 噪声检测能力：能够识别和标记异常值（噪声点）
• 密度适应性：基于数据点的密度进行聚类，适合密度不均匀的数据集

在理解DBSCAN算法之前，需要先了解几个重要概念：

ε-邻域（Epsilon Neighborhood）：给定点p的ε-邻域是指与p距离不超过ε的所有点的集合，记作N_ε(p)。

核心点（Core Point）：如果点p的ε-邻域内至少包含min_samples个点（包括p本身），则p是核心点。

边界点（Border Point）：不是核心点，但在某个核心点的ε-邻域内的点。

噪声点（Noise Point）：既不是核心点，也不是边界点的点，被标记为异常值。

密度直达（Directly Density-Reachable）：如果点q在点p的ε-邻域内，且p是核心点，则称q从p密度直达。注意：密度直达关系是不对称的。

密度可达（Density-Reachable）：如果存在一个点链p₁, p₂, ..., pₙ，其中p₁=p, pₙ=q，且对于每个i，pᵢ₊₁都从pᵢ密度直达，则称q从p密度可达。

密度相连（Density-Connected）：如果存在一个点o，使得p和q都从o密度可达，则称p和q密度相连。密度相连关系是对称的。

算法步骤

DBSCAN算法如何划分集群：

1. 初始化参数：设定两个关键参数 - eps（邻域半径）和 min_samples（最小样本数）。所有点初始标记为-1（噪声点）。

2. 遍历所有未处理的数据点：

   • 计算当前点的 eps 邻域内的点数
   • 如果邻域内点数 ≥ min_samples，则该点为核心点，进入步骤3
   • 如果邻域内点数 < min_samples，则跳过该点（保持为噪声点状态）

3. 从核心点开始扩展簇：

   • 为当前核心点创建一个新簇（分配新的簇ID）
   • 将当前核心点标记为该簇的成员
   • 将其所有邻域内的点加入待处理队列，进入步骤4

4. 递归扩展簇：

   • 遍历待处理队列中的每个点：
     • 如果该点尚未分类（标记为-1），将其加入当前簇
     • 如果该点也是核心点，将其邻域内的所有未处理点加入待处理队列
   • 继续直到队列为空

5. 重复步骤2-4：直到所有点都被处理完毕

最终结果：

• 核心点和边界点：被分配到对应的簇ID
• 噪声点：保持-1标记，表示不属于任何簇

核心思想：同一个簇中的所有点都是密度相连的，不同簇之间的点不是密度相连的。

回归算法

函数与导数

初等数学的研究对象基本上是不变的量，而高等数学的研究对象是变化的量。高等数学对学习编程具有重要的意义，因为编程涉及到许多与数学密切相关的概念和技能。

本章节内容主要源自《高等数学（第七版）》，仅对语序、相似内容做调整。学习更多高等数学知识请移步其他平台。

本章提到的符号含义如下：

$\{ \}$ 表集合、定义域或值域

• $A = \{1, 2, 3\}$ 表示集合 $A$ 包含元素 $1, 2, 3$
• $f(x) = \{y | y = x^2, x \in R\}$ 表示函数 $f(x)$ 的值域是所有 $x^2$ 的值，其中 $x$ 是实数。

$\to$ 表逻辑关系，

• 如 $a \to b$ 表示 $a$ 推导出 $b$.

• $f:X\to Y$ 表示 $f$ 是从 $X$ 到 $Y$ 的一个映射。

• 不同场景还可表示：变换、趋向、收敛、极限等。

$|$ 表“使得”或“满足”，$R_y = \{y | y \geq 0\}$,表示一个实数集合 $R_y$，其中包含所有满足 $y \geq 0$ 条件的实数 $y$。

$\in$ 表属于，如果 $a$ 是集合 $A$ 的元素，记作 $a \in A$.

$\subseteq$ 表子集，如果 A 是集合 B 的子集(A 与 B 可以相等), 记作 $A \subseteq B$.

$\subset$ 表真子集， 如果 A 是集合 B 的真子集(A 与 B 不相等), 记作 $A \subset B$.

函数

映射的概念

定义：设 $X$ 和 $Y$ 是两个非空集合，

如果存在一个对应关系 $f$，使得对于 $X$ 中的任意一个元素 $x$，在 $Y$ 中都有唯一确定的元素 $y$ 和它对应，

那么就称 $f$ 为从 $X$ 到 $Y$ 的一个映射，记作 $f:X\to Y$，

其中，$y$ 称为 $x$ 在映射 $f$ 下的像，记作 $y=f(x)$。而 $X$ 中的元素 $x$ 称为 $y$ 的原像。

并称 $X$ 为$f$的定义域，记作 $D_f$；

$Y$ 为$f$的值域，记作 $R_f$。

$R_f = f(X)=\{f(x) | x\in D_f\}$

构成一个映射的条件是：

1. 集合 $X$ ，即定义域 $D_f = X$
2. 集合 $Y$ ，即值域 $R_f \subseteq Y$
3. 对应法则$f$，对于 $X$ 中的任意一个元素 $x$，在 $Y$ 中都有唯一确定的元素 $y$ 和它对应

注意：

对每个 $x \in X$，$f(x)$ 必须是确定唯一与之对应的

对于 $y \in Y$，$y$ 可以有多个原像。

例如，$f(x)=x^2$，$y=1$ 的原像可以是 $x=1$ 或 $x=-1$。

值域 $R_f$ 是 $Y$ 的子集,即 $R_f \subseteq Y$，而不一定是 $R_f = Y$

导数

假设有一辆小电动车，装有一根透明的长管。管子的中点代表零，两端分别象征正无穷和负无穷，管内静置着一颗小球。当车辆运动小球也会跟着运动，小球的数值就是导数。

• 平直道路：当车辆在平坦路面上行驶时，小球始终保持在零点位置。（常数的导数）
• 爬坡下坡：上坡时，由于斜度影响，小球逐渐向正无穷移动；下坡时则向负无穷滑动。
• 悬崖处：如果电动车遇到悬崖直接坠落，这代表函数在此处不连续，也就是不可导。
• 起伏道路：当车辆行驶在起伏不断的路面上时，小球的运动轨迹类似波浪。这种变化与三角函数之间的关系异曲同工：例如，sin 的导数变为 cos。

幂函数求导

幂函数求导的通用法则：

$\frac{d}{dx} x^n = nx^{n-1}$

1. “指数向前”： 将指数 $n$ 移到变量 $x$ 的前面作为系数。
2. “并减一”： 将原指数 $n$ 减去1，得到新的指数 $n-1$。

• 基本形式： 求 $x^2$ 的导数。 将指数2移到前面，并将指数2减去1（2-1=1），所以导数是 $2x^1 = 2x$。
  $\frac{d}{dx} x^2 = 2x^{2-1} = 2x$

• 常数乘以幂函数： 求 $5x^3$ 的导数。 常数5保持不变，对 $x^3$ 使用法则。将指数3移到前面，与常数5相乘，并将指数3减去1。
  $\frac{d}{dx} 5x^3 = 5 \cdot 3x^{3-1} = 15x^2$

• 分式形式： 求 $\frac{1}{x^4}$ 的导数。
  首先，将分式转化为指数形式：$\frac{1}{x^4} = x^{-4}$。
  然后使用法则，将指数-4移到前面，并将指数-4减去1（$-4 - 1 = -5$）。
  $\frac{d}{dx} \frac{1}{x^4} = \frac{d}{dx} x^{-4} = -4x^{-4-1} = -4x^{-5} = -\frac{4}{x^5}$

线性回归

线性回归是利用连续性变量来估计实际数值（例如房价，呼叫次数和总销售额等）。

我们通过线性回归算法找出自变量和因变量间的最佳线性关系，图形上可以确定一条最佳直线。

这条最佳直线就是回归线。这个回归关系可以用 $Y=aX+b$ 表示。

多个数据可以用 $Y= β0X0 + β1X1 + β2X2+…… βnXn+ ε$ 表示。

损失函数

如何评估数据的离散程度呢？

平均值：数据相加除以数据个数

平均差：数据与平均值的差的绝对值相加除以数据个数

均方误差：数据与平均值的差的平方相加除以数据个数

数据1	数据2	平均值	平均差	均方误差
0	0	0	0	0
-4	4	0	4	16
7	1	4	4	25

我们预期中，理想效果应该是 0、0 好于 -4、4 好于 7、1。只有均方误差正确的反应了这一点。

在预测出来的值和目标值之间差的部分，我们称之为损失，均方误差常见的用于评估数据离散程度的损失函数，以下是常见的损失函数及其特点

名称	数学表达式	值域	导数表达式	优点	缺点
交叉熵损失（Cross Entropy）	$L = -\sum_{i} y_i \log(\hat{y}_i)$	$[0,+\infty)$	$\frac{\partial L}{\partial \hat{y}_i} = -\frac{y_i}{\hat{y}_i}$	最常用，适合 one-hot 标签，梯度清晰，收敛快	对异常值敏感，需要防止概率为0的情况
均方误差（MSE）	$L = \frac{1}{n} \sum_{i} (y_i - \hat{y}_i)^2$	$[0,+\infty)$	$\frac{\partial L}{\partial \hat{y}_i} = -\frac{2}{n}(y_i - \hat{y}_i)$	简单直观，易于理解	不适合分类任务，梯度在误差较大时过大
平均绝对误差（MAE）	$L = \frac{1}{n} \sum_{i} \vert y_i - \hat{y}_i \vert$	$[0,+\infty)$	$\frac{\partial L}{\partial \hat{y}_i} = -\frac{1}{n}sgn(y_i - \hat{y}_i)$	对异常值不敏感，稳定性好	在零点不可导，优化困难

求导

通过误差的大小，我们可以慢慢修正我们的参数让线性拟合更好，导数可以反应数据变化的趋势，所以我们可以求导来修改参数。

这个过程也叫：求梯度、反向传播（狭义）

误差我们用的是均方误差：求了每个数据与平均值的差的平方，再加和，再求平均

每个数据的误差我们一般叫损失，写作 $loss$，他的值等于数据集中的目标值，减去我们线性公式算出来的预测值。

即：$loss = (y - (wx + b))^2$

这个表达式中，loss 是算出来的，y 是目标值，源自数据集，x 是特征值，源自数据集。

我们调整 w 和 b 的值就可以间接控制 loss 的值变大或变小（这里主要是期望变小）。

我想既更新 w，也更新 b。

所以分 2 次求导，第一次求：$\frac{\partial loss}{\partial w}$

第二次求：$\frac{\partial loss}{\partial b}$。

题解

import numpy as np
from matplotlib import pyplot as plt

class Line:
    def __init__(self, data):
        self.w = 1
        self.b = 0
        self.learning_rate = 0.01
        self.fig, (self.ax1, self.ax2) = plt.subplots(2, 1)
        self.loss_list = []

    def get_data(self, data):
        self.X = np.array(data)[:, 0]
        self.y = np.array(data)[:, 1]

    def predict(self, x):
        return self.w * x + self.b
    
    def train(self, epoch_times):
        for epoch in range(epoch_times):
            total_loss = 0
            for x, y in zip(self.X, self.y):
                y_pred = self.predict(x)
                # Calculate gradients
                gradient_w = -2 * x * (y - y_pred)
                gradient_b = -2 * (y - y_pred)
                # Update weights
                self.w -= self.learning_rate * gradient_w
                self.b -= self.learning_rate * gradient_b
                # Calculate loss
                loss = (y - y_pred) ** 2
                total_loss += loss
            epoch_loss = total_loss / len(self.X)
            self.loss_list.append(epoch_loss)
            if epoch % 10 == 0:
                print(f"loss: {epoch_loss}")
                self.plot()
        plt.ioff()
        plt.show()

    def plot(self):
        plt.ion()  # Enable interactive mode
        self.ax2.clear()
        self.ax1.clear()
        x = np.linspace(0, 10, 100)
        self.ax1.scatter(self.X, self.y, c="g")
        self.ax1.plot(x, self.predict(x), c="b")
        self.ax2.plot(list(range(len(self.loss_list))), self.loss_list)
        plt.show()
        plt.pause(0.1)

if __name__ == "__main__":  
    # Input data
    data = [(1, 1), (1.8, 2), (2.5, 3), (4.2, 4), (5, 5), (6, 6), (7, 7)]
    s = Line(data)
    s.get_data(data)
    s.train(100)

逻辑回归

有时候，数据并不是一种线性状态，例如：蝌蚪前期体型很小，变态之后体型忽然增大。

这过程更接近一个Sigmoid函数，因此逻辑回归使用Sigmoid函数作为激活函数。

# 绘制逻辑回归的不同回归系数的sigmoid函数

import matplotlib.pyplot as plt
import numpy as np

def sigmoid(x,p=1):
    # 直接返回sigmoid函数
    return 1. / (1. + np.exp(-p*x))

def plot_sigmoid(p=1):
    # param:起点，终点，间距
    x = np.arange(-8, 8, 0.2)
    y = sigmoid(x,p)
    plt.plot(x, y)
    plt.show()

if __name__ == '__main__':
    plot_sigmoid()
    plot_sigmoid(20)
    plot_sigmoid(0.5)

逻辑回归是一种统计模型，它使用数学中的逻辑函数或 logit 函数作为 x 和 y 之间的方程式。Logit 函数将 y 映射为 x 的 sigmoid 函数。

$f(x) = \frac{1}{1 + e^{-x}}$

多个解释变量会影响因变量的值。要对此类输入数据集建模，逻辑回归公式假设不同自变量之间存在线性关系。您可以修改 sigmoid 函数并按如下公式计算最终输出变量

$y = f(β0 + β1x1 + β2x2+… βnxn)$

符号 β 表示回归系数。当您给它一个其中包含因变量和自变量的已知值的足够大的实验数据集时，logit 模型可以反向计算这些系数值。

除了 sigmoid 还有其他常见的激活函数，以下是 Sigmoid、ReLU、Softmax、Tanh 的多维对比表，包含定义、值域、优缺点、导数等内容：

名称	数学表达式	值域	导数表达式	优点	缺点
Sigmoid	$\sigma(x) = \frac{1}{1 + e^{-x}}$	$(0, 1)$	$\sigma'(x) = \sigma(x)(1 - \sigma(x))$	平滑，有概率解释	梯度消失、输出非0均值
ReLU	$\text{ReLU}(x) = \max(0, x)$	$[0, +\infty)$	$\text{ReLU}'(x) = \begin{cases} 1, & x > 0 \\ 0, & x \le 0 \end{cases}$	计算简单，收敛快	不可导于0，死神经元问题
Tanh	$\tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$	$(-1, 1)$	$\tanh'(x) = 1 - \tanh^2(x)$	平滑，输出均值为0	梯度消失
Softmax	$\text{softmax}(x_i) = \frac{e^{x_i}}{\sum_j e^{x_j}}$	$(0,1)$ 且 $\sum=1$	$\frac{\partial y_i}{\partial x_j} = y_i(\delta_{ij} - y_j)$	多分类概率输出，归一化	对大值敏感，数值不稳定

对于不同的交叉熵、均方误差和这些激活函数的导数不同，你可以使用复合求导简化这个过程。

题解

import numpy as np
from matplotlib import pyplot as plt

class Sline:
    def __init__(self, data):
        self.w = 0
        self.b = 0
        self.learning_rate = 0.1
        self.fig, (self.ax1, self.ax2) = plt.subplots(2, 1)
        self.loss_list = []


    def get_data(self, data):
        self.X = np.array(data)[:, 0]
        self.y = np.array(data)[:, 1]

    def sigmoid(self, x):
        return 1 / (1 + np.exp(-(self.w * x + self.b)))

    def train(self, epoch_times):
        for epoch in range(epoch_times):
            total_loss = 0
            for x, y in zip(self.X, self.y):
                y_pred = self.sigmoid(x)
                # w新 = w旧 - 学习率 * 梯度
                grad = -2 * (y - y_pred) * (1 - y_pred) * y_pred * x
                self.w = self.w - self.learning_rate * grad * x
                # b新 = b旧 - 学习率 * 梯度
                self.b = self.b - self.learning_rate * grad
                loss = (y - y_pred) ** 2
                total_loss += loss
            epoch_loss = total_loss / len(self.X)
            self.loss_list.append(epoch_loss)
            if epoch % 10 == 0:
                print(f"loss: {epoch_loss}")
                self.plot()
        plt.ioff()
        plt.show()

    def plot(self):
        plt.ion()  # 启用交互模式
        self.ax2.clear()
        self.ax1.clear()
        x = np.linspace(0, 10, 100)
        self.ax1.scatter(self.X, self.y, c="g")
        self.ax1.plot(x, self.sigmoid(x), c="b")
        self.ax2.plot(list(range(len(self.loss_list))), self.loss_list)
        plt.show()
        plt.pause(0.1)

if __name__ == "__main__":  
    # 散点输入
    data = [(1, 0), (1.8, 0), (2.5, 0), (4.2, 1), (5, 1), (6, 1), (7, 1)]
    s = Sline(data)
    s.get_data(data)
    s.train(1000)