今日事项-2024年7月9日

事项一 学习三个实用算法

贪心算法（Greedy Algorithm）

产生原因与背景：

想象你在一家超市里，想要用有限的钱买到尽可能多的糖果。你会一直挑选单价最低的糖果，直到钱用完。贪心算法就是这样，它在每一步选择中都采取当前看起来最好的选择，以期望获得全局最优解。

算法思路：

贪心算法就像是一位精明的购物者，在购物时总是选择性价比最高的商品，希望通过这些局部最优的选择来获得最大的整体收益。

代码案列：

def min_coin_change(coins, amount):
    # 贪心选择：按照硬币面额从大到小排列
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        # 计算当前硬币面额可以兑换的个数
        while amount >= coin:
            amount -= coin
            count += 1
    return count

# 使用示例
coins = [1, 2, 5]  # 硬币面额
amount = 11  # 总金额
print("Minimum number of coins to make change for", amount, ":", min_coin_change(coins, amount))

算法优缺点：

优点：贪心算法在很多问题上都能给出一个足够好的解决方案，且实现简单。
缺点：贪心算法并不保证总是能得到全局最优解，因为它只关注当前的最优选择。

解决缺点的方法：

在需要全局最优解的情况下，可以使用动态规划或其他全局最优算法。

算法的3个实际应用案例：

• 背包问题：如何将价值最大化的物品装入有限容量的背包。
• 任务调度：在多个任务中选择当前优先级最高的任务执行。
• 网络流问题：在网络中选择最短的路径传输数据包。

布隆过滤器（Bloom Filter）

产生原因与背景：

想象你管理着一个巨大的图书馆，需要快速判断一本书是否在馆内，而不必真的去书架上查找。布隆过滤器是一种空间效率很高的数据结构，用于测试元素是否是一个集合的成员。

算法思路：

布隆过滤器就像是一位图书管理员使用的一种快速检查系统，他通过多个不同的标签系统来快速定位书籍，如果所有标签都指向某个位置，那么这本书很可能就在那里。

代码案列：

略（布隆过滤器的实现较为复杂，通常涉及位数组和哈希函数）

算法优缺点：

优点：布隆过滤器在空间和时间效率上都很高效，特别是对于大规模数据集的快速查找。
缺点：布隆过滤器存在误判的可能性，即可能会告诉你一个元素存在，而实际上它并不存在。

解决缺点的方法：

通过增加位数组的大小或哈希函数的数量来降低误判率。

算法的3个实际应用案例：

• 缓存系统：快速判断一个元素是否在缓存中。
• 数据库索引：减少数据库查询中的误判，提高查询效率。
• 信息检索：在大规模文档集合中快速排除不相关的文档。

编辑距离（Levenshtein Distance）

产生原因与背景：

想象你在比较两个版本的软件代码，需要知道它们之间的差异有多大。编辑距离算法用于计算两个字符串之间，通过最少的插入、删除或替换操作，从一个字符串转换成另一个字符串的距离。

算法思路：

编辑距离算法就像是一位编辑在比较两份文稿，他需要找出最少的修改次数，以使两份文稿内容一致。

代码案列：

def levenshtein_distance(s1, s2):
    len_s1, len_s2 = len(s1), len(s2)
    # 初始化二维数组存储编辑距离
    dp = [[0] * (len_s2 + 1) for _ in range(len_s1 + 1)]

    # 边界条件：空字符串到另一个字符串的距离是另一个字符串的长度
    for i in range(len_s1 + 1):
        dp[i][0] = i
    for j in range(len_s2 + 1):
        dp[0][j] = j

    # 计算编辑距离
    for i in range(1, len_s1 + 1):
        for j in range(1, len_s2 + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同，不需要操作
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],    # 删除s1的一个字符
                    dp[i][j - 1],    # 在s2中插入一个字符
                    dp[i - 1][j - 1] # 替换一个字符
                )
    return dp[len_s1][len_s2]

# 使用示例
s1 = "kitten"
s2 = "sitting"
print("Levenshtein distance:", levenshtein_distance(s1, s2))

算法优缺点：

优点：编辑距离算法能够提供两个字符串之间差异的量化度量，对于字符串比较非常有用。
缺点：编辑距离算法的时间复杂度为O(m * n)，其中m和n是两个字符串的长度，对于长字符串效率较低。

解决缺点的方法：

对于长字符串，可以使用更高效的算法或启发式方法来近似计算编辑距离。

算法的3个实际应用案例：

• 拼写检查器：检测和建议更正拼写错误。
• 生物信息学：比较DNA序列或蛋白质序列的相似度。
• 软件本地化：比较不同语言版本的软件字符串，以发现翻译不一致之处。