分类目录归档：算法基础
一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。
优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。https://www.cnblogs.com/cpselvis/p/6265825.html https://blog.csdn.net/tianyaleix
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致
结果是全剧最好或最优的算法
贪心算法与动态规划的不同在于他对每个字问题的解决方案都做出选择，不能回退。动态规划则会
保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
贪心算法可以解决工程中一些最优化问题， 如: 求图中的最小生成树、求哈夫曼编码等。然而对于 工程和生活中的问题，贪心法一般不能得到我们所要求的答案
一旦一个问题可以通过贪心法来解决。那么贪心法一般是解决这个问题的最好办法。 由于贪心法的搞笑性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者
def divide_conquer(problem, param1, param2, ...):
# recursion terminator
if problem is None:
print_result
return
# prepare data
data = prepare_data(problem)
subproblems = split_problem(problem, data)
# conquer subproblems
subresult1 = self.divide_conquer(subproblems[0], 启发式函数: h(n)，它用来评价哪些结点最有希望的是一个我们要找的结 点，h(n) 会返回一个非负实数,也可以认为是从结点n的目标结点路径的估 计成本。 启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测 哪个邻居结点会导向一个目标。
https://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/
def AstartSearch(graph, start, end):
pq = visited = set()
def dfs(node, visited):
# 1. terminator
if node in visited:
return
visited.add(node)
# process_current_logic
...
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
def dfs(self, root):
if not ro并查集(union & find) 是一种树形结构，用于处理一些不交集(Disjoint Sets) 的合并及查询问题
Find: 确定元素属于哪一个子集。他可以被用来确定两个元素是否属于同一个子集。
Union: 将两个子集合合并成同一个集合
字典树，即 Trie 树，又称单词 查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。 它的优点是:最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie 树的核心思想是空间换时间。 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
static用数组存储
二三树
AVL
红黑树
B 树
B+
⭐️slpay 伸展树
⭐️treap树的面试题一般都是递归的，这是为什么？
看是否有环，有环为图
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
二叉搜索树，也称为二叉搜索排序树、有序二叉树(Ordered Binary Tree)、排序二叉树(Sorted Binary Tree), 是指一棵空
去的过程叫“递”，回来的过程叫“归”
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤
递归与循环没有明显的边界，它是通过函数体来进行的循环
终止条件 递推公式
递归会利用栈保存临时变量，如果
from functools import lru_cache
@lru_cache(None)
def add(x, y):
return x+yhttps://www.jianshu.com/p/b1ab4a170c3c
Understanding the Meltdown exploit
缓存文件置换机制
缓存文件置换机制 中文