1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def bubble_sort(arr):
    """
    冒泡排序：两两比较，大的往后走
    时间复杂度：O(n²) — 稳如老狗，但慢如蜗牛
    空间复杂度：O(1) — 不占额外空间，环保！
    """
    n = len(arr)
    for i in range(n):
        # 标志位：如果某一轮没有发生交换，说明已经有序，可以提前结束
        swapped = False
        for j in range(0, n - i - 1):
            # 两两比较
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 交换位置
                swapped = True
        print(f"第 {i + 1} 轮排序后: {arr}")  # 打印每轮结果
        # 没有交换？说明已经排好了，收工！
        if not swapped:
            break
    return arr


# 测试一下！
data = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", data)
# 原始数组: [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print("排序后:", data)
# 排序后: [11, 12, 22, 25, 34, 64, 90]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def selection_sort(arr):
    """
    选择排序：每一轮选个"最能打的"，放到正确位置
    时间复杂度：O(n²) — 无论数据长什么样，都要慢慢挑
    空间复杂度：O(1) — 原地操作，空间占用极少
    """
    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
        # 把找到的最小值换到第 i 个位置
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        print(f"第 {i + 1} 轮选择后: {arr}")
    return arr


data = [64, 25, 12, 22, 11]
print("原始数组:", data)
# 原始数组: [64, 25, 12, 22, 11]
selection_sort(data)
print("排序后:", data)
# 排序后: [11, 12, 22, 25, 64]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def insertion_sort(arr):
    """
    插入排序：摸牌插牌，边摸边理
    时间复杂度：O(n²)（最坏），O(n)（最好，即已排序）
    空间复杂度：O(1)
    """
    for i in range(1, len(arr)):
        # 当前要插入的"新牌"
        key = arr[i]
        # 已在左手（已排序区）的元素从右往左比较
        j = i - 1
        print(f"摸到新牌: {key}，开始寻找插入位置，当前左手: {arr[:i]}")
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 元素往后挪，空出位置
            j -= 1
        # j+1 就是新牌的归宿
        arr[j + 1] = key
        print(f"插入完成: {arr[:i+1]}")
    return arr


data = [12, 11, 13, 5, 6]
print("原始数组:", data)
# 原始数组: [12, 11, 13, 5, 6]
insertion_sort(data)
print("排序后:", data)
# 排序后: [5, 6, 11, 12, 13]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def merge_sort(arr):
    """
    归并排序：分而治之，各个击破
    时间复杂度：O(n log n) — 稳定高效
    空间复杂度：O(n) — 需要额外空间合并
    """
    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

    print(f"    合并: left={left}, right={right}")

    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:])
    print(f"    合并结果: {result}")
    return result


# 测试
data = [38, 27, 43, 3, 9, 82, 10]
print("原始数组:", data)
# 原始数组: [38, 27, 43, 3, 9, 82, 10]
sorted_data = merge_sort(data)
print("排序后:", sorted_data)
# 排序后: [3, 9, 10, 27, 38, 43, 82]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def quick_sort(arr):
    """
    快速排序：选基准，分左右，递归排序
    时间复杂度：O(n log n)（平均），O(n²)（最坏）
    空间复杂度：O(log n)（递归栈）
    """
    if len(arr) <= 1:
        return arr

    # 选择基准（这里选中间的元素）
    pivot = arr[len(arr) // 2]
    print(f"基准值: {pivot}, 待排序: {arr}")

    # 分成三部分：小于基准、等于基准、大于基准
    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]

    print(f"  左边: {left}, 中间: {middle}, 右边: {right}")

    # 递归排序左右，然后拼接
    return quick_sort(left) + middle + quick_sort(right)


# 测试
data = [10, 7, 8, 9, 1, 5]
print("原始数组:", data)
# 原始数组: [10, 7, 8, 9, 1, 5]
sorted_data = quick_sort(data)
print("排序后:", sorted_data)
# 排序后: [1, 5, 7, 8, 9, 10]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

import heapq  # Python自带堆模块，但手写更能理解原理


def heap_sort(arr):
    """
    堆排序：利用堆的性质进行排序
    时间复杂度：O(n log n) — 稳定高效
    空间复杂度：O(1) — 原地排序
    """
    n = len(arr)

    # 第一步：构建最大堆（从最后一个非叶子节点往前调整）
    # 叶子节点不需要调整，所以从 (n//2 - 1) 开始
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    print(f"构建好的最大堆: {arr}")

    # 第二步：逐个提取元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 把堆顶（最大值）移到末尾
        print(f"交换后 [堆顶 {arr[i]} 到位]: {arr}")
        heapify(arr, i, 0)  # 重新调整剩余的堆

    return arr


def heapify(arr, heap_size, root_index):
    """
    堆化：从上往下调整，保持最大堆性质
    父节点 index -> i
    左孩子 -> 2*i + 1
    右孩子 -> 2*i + 2
    """
    largest = root_index
    left = 2 * root_index + 1
    right = 2 * root_index + 2

    # 如果左孩子比根大
    if left < heap_size and arr[left] > arr[largest]:
        largest = left

    # 如果右孩子更大
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    # 如果最大的不是根，需要调整
    if largest != root_index:
        arr[root_index], arr[largest] = arr[largest], arr[root_index]
        # 递归往下调整
        heapify(arr, heap_size, largest)


# 测试
data = [12, 11, 13, 5, 6, 7]
print("原始数组:", data)
# 原始数组: [12, 11, 13, 5, 6, 7]
heap_sort(data)
print("排序后:", data)
# 排序后: [5, 6, 7, 11, 12, 13]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def sequential_search(arr, target):
    """
    顺序查找：老实人策略，一个一个找
    时间复杂度：O(n) — 最坏情况要查遍全数组
    空间复杂度：O(1)
    """
    for i, num in enumerate(arr):
        print(f"正在检查第 {i + 1} 个元素: {num}...")
        if num == target:
            print(f"找到了！目标 {target} 在索引 {i} 处！🎉")
            return i
    print(f"遗憾！目标 {target} 不在这个数组里...")
    return -1


# 测试
data = ['苹果', '香蕉', '橙子', '葡萄', '西瓜']
print("=" * 40)
result = sequential_search(data, '橙子')
# 正在检查第 3 个元素: 橙子...
# 找到了！目标 橙子 在索引 2 处！🎉

print("=" * 40)
result = sequential_search(data, '桃子')
# 遍历完所有元素
# 遗憾！目标 桃子 不在这个数组里...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def binary_search(arr, target):
    """
    二分查找：每次砍一半，快到飞起
    时间复杂度：O(log n) — 10亿数据最多只要查30次！
    空间复杂度：O(1)
    前提：数组必须有序！
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # 中间位置
        print(f"搜索范围: [{left}, {right}], 中间位置: {mid}, 中间值: {arr[mid]}")

        if arr[mid] == target:
            print(f"🎯 找到了！目标 {target} 在索引 {mid} 处！")
            return mid
        elif arr[mid] < target:
            print(f"  {arr[mid]} < {target}，目标在右半边，继续！")
            left = mid + 1
        else:
            print(f"  {arr[mid]} > {target}，目标在左半边，继续！")
            right = mid - 1

    print(f"遗憾！目标 {target} 不在数组中...")
    return -1


# 测试
data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
print("有序数组:", data)
print("=" * 50)
result = binary_search(data, 13)
# 搜索范围: [0, 10], 中间位置: 5, 中间值: 11
#   11 < 13，目标在右半边，继续！
# 搜索范围: [6, 10], 中间位置: 8, 中间值: 17
#   17 > 13，目标在左半边，继续！
# 搜索范围: [6, 7], 中间位置: 6, 中间值: 13
# 🎯 找到了！目标 13 在索引 6 处！

print("=" * 50)
result = binary_search(data, 6)
# 搜索范围: [0, 10], 中间位置: 5, 中间值: 11
# ...
# 遗憾！目标 6 不在数组中...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# 二分查找的递归版本
def binary_search_recursive(arr, target, left, right):
    """递归版本的二分查找"""
    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 递归三要素示例：计算阶乘
def factorial(n):
    """
    递归三要素：
    1. 【基准情形】最小问题，直接返回答案
    2. 【递归调用】大问题变小问题，调用自身
    3. 【递归返回】子问题的答案组合成大问题的答案
    """

    # 要素1：基准情形 — 0! = 1，这是递归的终点
    if n == 0 or n == 1:
        return 1

    # 要素2：递归调用 — n! = n * (n-1)!
    result = n * factorial(n - 1)

    # 要素3：返回结果 — 子问题答案组合成当前问题的答案
    return result


# 测试
print(f"5! = {factorial(5)}")  # 5! = 120
print(f"0! = {factorial(0)}")  # 0! = 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

def hanoi(n, source, target, auxiliary):
    """
    汉诺塔问题：经典的递归问题
    目标：把 n 个盘子从 source 柱子，借助 auxiliary 柱子，移到 target 柱子

    核心思想：
    1. 把上面的 n-1 个盘子从 source 移到 auxiliary（借助 target）
    2. 把最大的盘子从 source 移到 target
    3. 把 n-1 个盘子从 auxiliary 移到 target（借助 source）
    """
    if n == 1:
        # 基准情形：只有一个盘子，直接搬
        print(f"把第 1 个盘子从 {source} 移到 {target}")
        return

    # 步骤1：把上面 n-1 个盘子从 source 移到 auxiliary（target 当跳板）
    hanoi(n - 1, source, auxiliary, target)

    # 步骤2：把最大的盘子（第 n 个）从 source 移到 target
    print(f"把第 {n} 个盘子从 {source} 移到 {target}")

    # 步骤3：把 n-1 个盘子从 auxiliary 移到 target（source 当跳板）
    hanoi(n - 1, auxiliary, target, source)


# 测试：3个盘子的汉诺塔
print("=" * 50)
print("【汉诺塔 - 3个盘子】")
print("=" * 50)
hanoi(3, 'A', 'C', 'B')
# 把第 1 个盘子从 A 移到 C
# 把第 2 个盘子从 A 移到 B
# 把第 1 个盘子从 C 移到 B
# 把第 3 个盘子从 A 移到 C
# 把第 1 个盘子从 B 移到 A
# 把第 2 个盘子从 B 移到 C
# 把第 1 个盘子从 A 移到 C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 计算n个盘子的移动步数
def hanoi_steps(n):
    return 2 ** n - 1


for i in range(1, 11):
    print(f"{i} 个盘子需要 {hanoi_steps(i)} 步")
# 1 个盘子需要 1 步
# 2 个盘子需要 3 步
# 3 个盘子需要 7 步
# ...
# 10 个盘子需要 1023 步

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

def merge_sort_verbose(arr, depth=0):
    """
    带日志的归并排序，看清楚递归的每一步
    """
    indent = "  " * depth
    print(f"{indent}[递归深度 {depth}] 开始排序: {arr}")

    # 基准情形：只有一个或零个元素，本身就是有序的
    if len(arr) <= 1:
        print(f"{indent}[基准情形] 元素 {arr} 已就绪，无需排序")
        return arr

    # 递归情形：分而治之
    mid = len(arr) // 2
    print(f"{indent}[分割] 左半边: {arr[:mid]}, 右半边: {arr[mid:]}")

    left = merge_sort_verbose(arr[:mid], depth + 1)
    right = merge_sort_verbose(arr[mid:], depth + 1)

    # 合并两个有序数组
    merged = merge_two_arrays(left, right)
    print(f"{indent}[合并] {left} + {right} = {merged}")

    return merged


def merge_two_arrays(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


# 测试
data = [38, 27, 43, 3, 9, 82, 10]
print("原始数组:", data)
print("=" * 60)
sorted_data = merge_sort_verbose(data)
print("=" * 60)
print("排序后:", sorted_data)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# 方法1：纯递归（不看不知道，一看吓一跳）
def fib_recursive(n):
    """纯递归：简单直接，但时间复杂度爆炸"""
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)


# 方法2：记忆化递归（DP的递归版本）
def fib_memoized(n, memo=None):
    """记忆化递归：用字典存储已计算的结果，避免重复计算"""
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]


# 方法3：DP表格法（DP的迭代版本）
def fib_dp_table(n):
    """自底向上：用表格存储每个子问题的答案"""
    if n <= 1:
        return n

    # dp[i] 表示第 i 个斐波那契数
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 方法4：空间优化（只保留前两个数）
def fib_optimized(n):
    """空间复杂度 O(1) 的版本"""
    if n <= 1:
        return n

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr

    return curr


# 测试
n = 10
print(f"斐波那契数列前 {n + 1} 项:")
for i in range(n + 1):
    print(f"F({i}) = {fib_dp_table(i)}")
# F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3,
# F(5) = 5, F(6) = 8, F(7) = 13, F(8) = 21, F(9) = 34, F(10) = 55

print(f"\n第 10 项: {fib_dp_table(10)}")  # 55
print(f"第 100 项: {fib_optimized(100)}")  # 354224848179261915075

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def knapsack(weights, values, capacity):
    """
    0-1 背包问题：经典的动态规划问题
    weights: 各物品的重量列表
    values: 各物品的价值列表
    capacity: 背包容量

    时间复杂度：O(n * capacity)
    空间复杂度：O(n * capacity)
    """
    n = len(weights)

    # dp[i][w] 表示：只考虑前 i 个物品，背包容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    print("开始动态规划...")
    for i in range(1, n + 1):
        print(f"\n考虑第 {i} 件物品 (重量={weights[i-1]}, 价值={values[i-1]}):")
        for w in range(capacity + 1):
            # 不选第 i 件物品
            dp[i][w] = dp[i - 1][w]

            # 选第 i 件物品（前提：背包能装下）
            if weights[i - 1] <= w:
                candidate = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                if candidate > dp[i][w]:
                    dp[i][w] = candidate

            if w == capacity:
                print(f"  容量 {w}: {dp[i][w]}")
            else:
                print(f"  容量 {w}: {dp[i][w]}", end=" | ")
        print()

    return dp[n][capacity]


# 测试
weights = [2, 3, 4, 5]   # 物品重量
values = [3, 4, 5, 6]    # 物品价值
capacity = 5             # 背包容量

print("=" * 60)
max_value = knapsack(weights, values, capacity)
print("=" * 60)
print(f"\n背包能装的最大价值: {max_value}")
# 最大价值为 7（选重量2价值3 + 重量3价值4，或者选重量5价值6）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def lcs(str1, str2):
    """
    最长公共子序列问题
    时间复杂度：O(m * n)
    空间复杂度：O(m * n)

    dp[i][j] 表示：str1[0..i-1] 和 str2[0..j-1] 的最长公共子序列长度
    """
    m, n = len(str1), len(str2)

    # dp表初始化
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    print(f"字符串1: '{str1}' (长度 {m})")
    print(f"字符串2: '{str2}' (长度 {n})")
    print()

    # 填表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                # 字符匹配，LCS长度 +1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 字符不匹配，取前面计算的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 打印dp表
    print("DP表格:")
    print("    ", end=" ")
    for j in range(n + 1):
        if j == 0:
            print("  ε", end=" ")
        else:
            print(f" {str2[j-1]}", end=" ")
    print()
    for i in range(m + 1):
        if i == 0:
            print("  ε", end=" ")
        else:
            print(f"{str1[i-1]} ", end=" ")
        for j in range(n + 1):
            print(f" {dp[i][j]}", end=" ")
        print()

    return dp[m][n]


# 测试
str1 = "ABCDGH"
str2 = "AEDFHR"
print("=" * 50)
result = lcs(str1, str2)
print("=" * 50)
print(f"\n最长公共子序列长度: {result}")  # 3 ("ADH")

print("\n" + "=" * 50 + "\n")

str1 = "AGGTAB"
str2 = "GXTXAYB"
result = lcs(str1, str2)
print(f"最长公共子序列长度: {result}")  # 4 ("GTAB")

1
2
3
4
5
6
7
8
9

# 用邻接表表示一个无向图
graph = {
    'A': ['B', 'C'],      # A 连接 B 和 C
    'B': ['A', 'D', 'E'], # B 连接 A、D、E
    'C': ['A', 'F'],      # C 连接 A 和 F
    'D': ['B'],           # D 连接 B
    'E': ['B', 'F'],      # E 连接 B 和 F
    'F': ['C', 'E']       # F 连接 C 和 E
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

from collections import deque


def bfs(graph, start):
    """
    广度优先搜索（BFS）
    适用场景：找最短路径、层次遍历、社交网络中"n度好友"查询

    时间复杂度：O(V + E)，V是顶点数，E是边数
    空间复杂度：O(V)
    """
    visited = set()  # 记录已访问的节点
    queue = deque([start])  # 队列初始化，放入起点
    visited.add(start)

    traversal_order = []  # 记录访问顺序

    print(f"BFS 从 '{start}' 开始:")
    step = 0

    while queue:
        step += 1
        node = queue.popleft()  # 从队列头部取出
        traversal_order.append(node)
        print(f"  第 {step} 步: 访问节点 '{node}'")

        # 遍历所有邻居
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                print(f"    → 发现未访问邻居 '{neighbor}'，加入队列")

    print(f"\n访问顺序: {' → '.join(traversal_order)}")
    return traversal_order


# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("=" * 50)
bfs(graph, 'A')
# BFS 从 'A' 开始:
#   第 1 步: 访问节点 'A'
#     → 发现未访问邻居 'B'，加入队列
#     → 发现未访问邻居 'C'，加入队列
#   第 2 步: 访问节点 'B'
#     → 发现未访问邻居 'D'，加入队列
#     → 发现未访问邻居 'E'，加入队列
#   第 3 步: 访问节点 'C'
#     → 发现未访问邻居 'F'，加入队列
#   第 4 步: 访问节点 'D'
#   第 5 步: 访问节点 'E'
#   第 6 步: 访问节点 'F'
#
# 访问顺序: A → B → C → D → E → F

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

def dfs_recursive(graph, node, visited=None):
    """
    深度优先搜索（DFS）- 递归版本
    时间复杂度：O(V + E)
    空间复杂度：O(V)（递归栈）
    """
    if visited is None:
        visited = set()

    visited.add(node)
    print(f"  访问节点: '{node}'")

    # 深度优先：递归访问所有未访问的邻居
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited


def dfs_iterative(graph, start):
    """
    深度优先搜索（DFS）- 迭代版本（用栈）
    """
    visited = set()
    stack = [start]
    traversal_order = []

    print(f"DFS 从 '{start}' 开始（迭代版本）:")
    step = 0

    while stack:
        node = stack.pop()  # 从栈顶取出
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            step += 1
            print(f"  第 {step} 步: 访问节点 '{node}'")

            # 注意：这里是逆序加入，因为栈是LIFO
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    print(f"\n访问顺序: {' → '.join(traversal_order)}")
    return traversal_order


# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("=" * 50)
print("【DFS 递归版本】")
print("=" * 50)
dfs_recursive(graph, 'A')

print("\n" + "=" * 50)
print("【DFS 迭代版本】")
print("=" * 50)
dfs_iterative(graph, 'A')

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import heapq


def dijkstra(graph, start):
    """
    Dijkstra最短路径算法
    适用于：带权图，边权非负
    时间复杂度：O((V + E) log V) — 使用优先队列优化

    graph: 邻接表形式的带权图
    返回: {节点: 到起点的最短距离}
    """
    # 到各节点的最短距离，初始为无穷大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 优先队列：(距离, 节点)
    pq = [(0, start)]
    # 记录已确认最短距离的节点
    visited = set()

    print(f"Dijkstra 从 '{start}' 开始:")
    step = 0

    while pq:
        step += 1
        current_dist, current_node = heapq.heappop(pq)

        # 如果已经处理过，跳过
        if current_node in visited:
            continue

        visited.add(current_node)
        print(f"  第 {step} 步: 处理节点 '{current_node}', 当前距离: {current_dist}")

        # 松弛当前节点的所有邻居
        for neighbor, weight in graph.get(current_node, []):
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
                    print(f"    → 更新 '{neighbor}' 距离: {new_dist}")

    return distances


# 测试 - 带权图
#       A ---2--- B
#       |       / \
#       1     3   1
#       |   /       \
#       C---4------- D
#        \         /
#         2-----1

graph_weighted = {
    'A': [('B', 2), ('C', 1)],
    'B': [('A', 2), ('C', 3), ('D', 1)],
    'C': [('A', 1), ('B', 3), ('D', 4), ('E', 2)],
    'D': [('B', 1), ('C', 4), ('E', 1)],
    'E': [('C', 2), ('D', 1)]
}

print("=" * 60)
distances = dijkstra(graph_weighted, 'A')
print("=" * 60)
print("\n从 A 出发的最短距离:")
for node, dist in distances.items():
    print(f"  A → {node}: {dist}")
# A → A: 0
# A → B: 2
# A → C: 1
# A → D: 3 (A→B→D: 2+1=3 或 A→C→D: 1+4=5，取小的3)
# A → E: 3 (A→C→E: 1+2=3 或 A→D→E: 3+1=4，取小的3)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# 贪心算法示例1：找零钱问题（假设货币系统合理）
def make_change(amount):
    """
    用最少硬币找零 — 假设有面值为 1, 5, 10, 20, 100 的硬币
    """
    coins = [100, 20, 10, 5, 1]  # 按从大到小排序
    result = {}

    for coin in coins:
        if amount >= coin:
            count = amount // coin
            result[coin] = count
            amount -= coin * count

    print(f"找零方案: {result}")
    return result


print("【找零问题】")
make_change(68)  # 应该得到：3个20, 1个5, 3个1
# 找零方案: {100: 0, 20: 3, 10: 0, 5: 1, 1: 3}


# 贪心算法示例2：活动选择问题
def activity_selection(activities):
    """
    活动选择问题：给定一组活动，每个活动有开始和结束时间，
    选择最多不重叠的活动

    贪心策略：每次选择结束时间最早的活动（这样能为后面的活动留更多时间）
    """
    # 按结束时间排序
    sorted_activities = sorted(activities, key=lambda x: x[1])

    selected = []
    current_end = 0  # 当前已选择活动的结束时间

    print("活动列表（按结束时间排序）:")
    for i, (name, start, end) in enumerate(sorted_activities):
        print(f"  {name}: {start}~{end}")

    print("\n选择过程:")
    for i, (name, start, end) in enumerate(sorted_activities):
        if start >= current_end:
            selected.append(name)
            current_end = end
            print(f"  ✓ 选择 '{name}' (开始={start}, 结束={end})")

    print(f"\n选择的最多活动: {selected}")
    return selected


print("\n【活动选择问题】")
activities = [
    ('A', 0, 6),
    ('B', 3, 4),
    ('C', 1, 2),
    ('D', 5, 9),
    ('E', 5, 7),
    ('F', 8, 10),
]
activity_selection(activities)
# 选择: C, B, E, F（或其他最多组合）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 贪心失效的例子
def coin_change_greedy_fail(amount):
    """贪心在某些货币系统下会失败"""
    # 如果只有 [1, 3, 4] 面值的硬币
    coins = [4, 3, 1]  # 按贪心策略从大到小排

    count = 0
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            result.append(coin)

    print(f"贪心结果: {result}，用了 {count} 个硬币")
    return count


print("\n【贪心可能翻车的例子】")
print("amount = 6, coins = [1, 3, 4]")
print("贪心策略: ", end="")
coin_change_greedy_fail(6)
# 贪心: 4 + 1 + 1 = 6，用了 3 个硬币
# 但最优解: 3 + 3 = 6，只用 2 个硬币！


def coin_change_dp(amount):
    """动态规划得到最优解"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in [1, 3, 4]:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount]


print(f"DP最优解: {coin_change_dp(6)} 个硬币")
# DP最优解: 2 个硬币

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# 贪心算法示例3：霍夫曼编码（数据压缩的基础）
def huffman_coding(frequencies):
    """
    霍夫曼编码：用贪心思想构造最优前缀码
    频率高的字符用短码，频率低的字符用长码，实现数据压缩

    这也是为什么 ZIP 压缩能工作的核心技术！
    """
    import heapq

    # 把所有字符放入优先队列（频率小的优先）
    heap = [[freq, [char, ""]] for char, freq in frequencies.items()]
    heapq.heapify(heap)

    print("霍夫曼编码过程:")
    while len(heap) > 1:
        # 取出频率最小的两个节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # 给它们的码字加前缀
        left[1][1] = "0" + left[1][1]
        right[1][1] = "1" + right[1][1]

        # 合并（频率相加），重新放回队列
        merged = [left[0] + right[0], [left[1], right[1]]]
        heapq.heappush(heap, merged)
        print(f"  合并节点: 频率={merged[0]}")

    # 返回构建好的霍夫曼树（优先队列中唯一的元素）
    return heap[0]


def flatten_codes(node, prefix=""):
    """把霍夫曼树展平为字典"""
    if isinstance(node[1], str):
        return {node[1]: prefix or "0"}
    codes = {}
    codes.update(flatten_codes(node[1][0], prefix + "0"))
    codes.update(flatten_codes(node[1][1], prefix + "1"))
    return codes


print("\n【霍夫曼编码】")
frequencies = {'A': 45, 'B': 13, 'C': 12, 'D': 16, 'E': 9, 'F': 5}
huffman_tree = huffman_coding(frequencies)
codes_dict = flatten_codes(huffman_tree)
print("\n编码结果:")
for char, code in sorted(codes_dict.items()):
    print(f"  {char}: {code} (频率: {frequencies[char]}%)")
# A: 0 (45%)
# F: 1000 (5%)
# ...
# 霍夫曼编码保证了：高频字符短码，低频字符长码，总编码长度最短！